当前位置：首页 > article >正文

哈希表(功能不太全，只能查找）

article 2025/1/21 18:49:33

哈喽哈喽，垂柳杨风唱明月，这里就是小橙豆，今天我自己写了个结构体数组版的哈希表。代码如下：

#ifndef obsour_PyicX_HashTable_h
#define obsour_PyicX_HashTable_h 0
unsigned int Stdkey_=7;
int Obsour_HashTable_Abs(int Val)
{
	return (Val < 0) ? -Val : Val;
}

//int Obsour_PyicX_Hash_Function(int Value, int key)
//{
//	// Ensure key is not zero to avoid division by zero  
//	if (key == 0) {
//		return -1; // or some error code  
//	}
//
//	// Use a prime number for better distribution  
//	const int prime = 31;
//
//	// Calculate hash without using bitwise or logical operators  
//	int absValue = Obsour_HashTable_Abs(Value);
//	int absKey = Obsour_HashTable_Abs(key);
//
//	return (absValue + absKey + (absValue * prime) % (absKey + 1)) % (absKey + 1);
//}
int Obsour_PyicX_Hash_Function(int Value, int key)
{
	return Obsour_HashTable_Abs(Value % key) + (key % Value) + Value % /*5*/Stdkey_;
}
int Nand(int numa,int numb)
{
	return !(numa && numb);
}

//
//const char* Encrypt(const char* Val) {
//	
//}

typedef struct Pyic_x
{
	int value;
	int mapping;
}HashTable_mait;
void Init(Pyic_x table[], int length)
{
	int i = 0;
	while (i < length)
	{
		table[i].value=-1;
		table[i].mapping=-1;
		++i;
	}
}
void Insert(Pyic_x Table[],int number,int value)
{
	Table[number].value= value;
	int Cdr = Obsour_PyicX_Hash_Function(value, Stdkey_);
	Table[Cdr].mapping = number;
	return;
}
int find(Pyic_x Table[], int value)
{
	int Mp = Obsour_PyicX_Hash_Function(value, Stdkey_);
	return Table[Mp].mapping;
}
void remove_val(Pyic_x Table[], int value)
{
	int Index = Obsour_PyicX_Hash_Function(value,Stdkey_);
	int Inde=Table[Index].mapping;
	Table[Index].mapping = -1;
	Table[Inde].value = -1;
}
//void remove_hash(Pyic_x Table[],int index)
//{
//	int Inde = Table[index].value;
//	Table[index].value = -1;
//	
//}
//#if (obsour_PyicX_HashTable_h==1)
//
//#endif /**/

#endif /*obsour_PyicX_HashTable_h*/

哈希函数都是自己写的，安全系数不高，但它至少是不可逆的，难定位。

这里使用的是结构体数组，大小可变。免去了大小固定（多了浪费内存，少了又无法完成项目）的缺点。接下来是时间复杂度盘点：

Init(初始化):O(n)

Insert(插入):O(1)

Find(查找前提：没有出现碰撞）:O(1)

------------不懂的看讲解，懂的就散吧-------------

1，数据结构

typedef struct Pyic_x {  
    int value;  
    int mapping;  
} HashTable_mait;

该结构体用于存储哈希表的单个条目。每个条目包含两个整型字段：

value：存储实际值。

mapping：存储值在哈希表中的索引位置。

2,初始化函数

void Init(Pyic_x table[], int length) {  
    int i = 0;  
    while (i < length) {  
        table[i].value = -1;  
        table[i].mapping = -1;  
        ++i;  
    }  
}

Init函数用于初始化哈希表。它将哈希表的每个条目的value和mapping字段都设为-1(代表空值)，表示这些位置当前没有有效数据。这样做可以在后续的插入操作中检查该位置是否已被占用。

3，哈希函数

int Obsour_PyicX_Hash_Function(int Value, int key) {  
    return Obsour_HashTable_Abs(Value % key) + (key % Value) + Value % Stdkey_;  
}

Obsour_PyicX_Hash_Function是哈希表的关键函数。它根据输入的Value和key计算一个哈希值。具体的哈希值计算过程如下：

使用Obsour_HashTable_Abs函数来确保值为非负。

结果为输入Value对key取模的值，加上key对Value取模的值，最后加上Value对Stdkey_（默认为7）取模的结果。此函数的设计意图是利用输入数据和配置的key提供一个相对均匀的哈希分布。

4，插入数据

void Insert(Pyic_x Table[], int number, int value) {  
    Table[number].value = value;  
    int Cdr = Obsour_PyicX_Hash_Function(value, Stdkey_);  
    Table[Cdr].mapping = number;  
    return;  
}

Insert函数用于将新值插入到哈希表中。首先，它将传入的值存入指定的number索引位置。然后，利用哈希函数计算出该值的哈希位置（Cdr）。最后，将number值映射到哈希表的哈希位置。

5，查找数据

int find(Pyic_x Table[], int value) {  
    int Mp = Obsour_PyicX_Hash_Function(value, Stdkey_);  
    return Table[Mp].mapping;  
}

find函数根据给定的value查找对应的映射值。它使用哈希函数计算出哈希位置，并返回该位置的mapping值。

6，删除数据（已注释但其实有用）

void remove_val(Pyic_x Table[], int value) {  
    int Index = Obsour_PyicX_Hash_Function(value, Stdkey_);  
    int Inde = Table[Index].mapping;  
    Table[Index].mapping = -1;  
    Table[Inde].value = -1;  
}

remove_val函数用于删除哈希表中的一个值。首先计算出值的哈希位置，然后将该位置的mapping设置为-1，并将对应条目的value也设为-1，表示此项已被删除。

看懂了吗？没想到你这么有毅力，能看到这里来，既然我们这么有缘，就点个赞叭！

查看全文

http://www.kler.cn/a/300377.html