哈希拉链法（哈希桶）
昨天写了哈希的开放定址法的博客，今天我们要说的是拉链法，还有一个名字叫哈希桶。哈希桶要做的就是，之前我们用的开放定址法，通过将数据映射到数组中来实现哈希。这里每个数组的位置只能存放一个数据，如果冲突的话会继续往下找找到空的位置然后放进去，但是其实大家都能感觉出来上一个代码很简单，也很扯，感觉实现起来完全不行，不要说海量数据了， 有点数据感觉就不行了，虽然可以扩容但是也是一件很复杂的事情。这里我们要实现的是将以前的数组变成一个指针数组，这里每个数据存放的都是一个指针，这样发生冲突的话，就不必要再去找下一个位置，每发生一次冲突就在当前位置的最后一个数据后边挂上另一个数据。
typedef int KeyType;
typedef int ValueType;
typedef struct HashNode
{
KeyType _key;
ValueType _value;
struct HashNode* _next;
}HashNode;
typedef struct HashTable
{
HashNode** _tables;
size_t _size;
size_t _N;
}HashTable;
size_t HashFunc(KeyType key, size_t N)
{
return key%N;
}具体来说，在每个位置都放置了一个结构体。每个结构体中存储了两组数据：一组用于存储数据本身（即存放的数据），另一组用于指向下一个元素的位置（即next指针）。整个设计的目的在于方便快速定位后续的元素节点。
HashNode** _tables;该变量定义为一个指向数组的指针，在内存中占据多个连续的空间位置，并且其中每个元素都指向另一个数据块的位置信息
HashNode* BuyHashNode(KeyType key, ValueType value)
{
HashNode *NewNode = NULL;
NewNode = (HashNode*)malloc(sizeof(HashNode));
NewNode->_key = key;
NewNode->_value = value;
NewNode->_next = NULL;
return NewNode;
}分配空间的时候只是多了一个next指针的初始化。
void HashTableInit(HashTable* ht)
{
assert(ht);
ht->_N = GetNextPrimeNum(0);
ht->_tables = (HashNode**)malloc(sizeof(HashNode*)*ht->_N);
ht->_size = 0;
for (int i = 0; i < 53; i++)
{
ht->_tables[i] = NULL;
}
return;
}初始化中这里不再是将每个位置置为0而是将每个位置变成NULL。
int HashTableInsert(HashTable* ht, KeyType key, ValueType value)
{
assert(ht);
HashNode *cur = NULL;
HashNode *next = NULL;
int Index = 0;
Index = HashFunc(key, ht->_N);
cur = ht->_tables[Index];
if (cur == NULL)
{
ht->_tables[Index] = BuyHashNode(key, value);
return 1;
}
else
{
while (cur)
{
if (cur->_key == key)
{
return 0;
}
cur = cur->_next;
}
next = ht->_tables[Index]->_next;
ht->_tables[Index] = BuyHashNode(key, value);
ht->_tables[Index]->_next = next;
}
ht->_size++;
return 1;
}当执行插入操作时，首先使用映射函数确定目标位置。接着检查该位置是否为空：如果是空的，则直接将新元素放置于该位置；否则，请检查当前位置及其后续所有元素中是否存在目标元素。如果遍历完成后未发现目标元素，则采用头插法将新元素插入到列表头部。
HashNode* HashTableFind(HashTable* ht, KeyType key)
{
assert(ht);
int Index = HashFunc( key, ht->_N);
HashNode *cur = ht->_tables[Index];
while (cur)
{
if (cur->_key == key)
return cur;
cur = cur->_next;
}
return NULL;
}查找函数，这些都是对链表的基本操作也不需要过多的介绍。
int HashTableRemove(HashTable* ht, KeyType key)
{
assert(ht);
int Index = HashFunc(key, ht->_N);
HashNode *cur = NULL;
HashNode *prev = NULL;
cur = ht->_tables[Index];
while (cur)
{
if (cur->_key == key)
{
if (prev == NULL)//第一个位置
{
ht->_tables[Index] = cur->_next;
}
else//不是第一个
{
prev->_next = cur->_next;
}
free(cur);
ht->_size--;
return 0;
}
prev = cur;
cur = cur->_next;
}
return -1;
}删除元素时也要判定是否是第一个位置，并对两种情形分别处理
size_t GetNextPrimeNum(size_t cur)
{
int i = 0;
static const unsigned long _PrimeList[28] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul,
786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul,
25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul,
805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
for (i = 0; i < 28; i++)
{
if (_PrimeList[i]>cur)
return _PrimeList[i];
}
}这个函数本来应该在上次就完成了,然而这次才将其编写完成,它是一个用于生成素数列表的函数.也就是说,在每次扩展数组时,数组大小已经被预先确定好了,这些元素就是当前数组中的元素.那么为什么要选择使用素数这一点也很容易理解.因为素数除了它本身和1不能被任何一个大于1的自然数整除之外,而且我们的映射方法正是基于余数值法进行操作,因此采用素数的方式能够在一定程度上缓解哈希冲突的问题.
int HashTableRemove(HashTable* ht, KeyType key)
{
assert(ht);
int Index = HashFunc(key, ht->_N);
HashNode *cur = NULL;
HashNode *prev = NULL;
cur = ht->_tables[Index];
while (cur)
{
if (cur->_key == key)
{
if (prev == NULL)//第一个位置
{
ht->_tables[Index] = cur->_next;
}
else//不是第一个
{
prev->_next = cur->_next;
}
free(cur);
ht->_size--;
return 0;
}
prev = cur;
cur = cur->_next;
}
return -1;
}删除也是对链表的基本操作。
void HashTableDestory(HashTable* ht)
{
int i = 0;
HashNode *cur = NULL;
HashNode *next = NULL;
for (; i < ht->_N; i++)
{
cur = ht->_tables[i];
while (cur)
{
next = cur->_next;
free(cur);
cur = next;
}
}
free(ht->_tables);
ht->_N = 0;
ht->_size = 0;
}
HashTable *Check(HashTable* ht)
{
if (ht->_N*0.7 < ht->_size)
{
HashTable NewHt;
HashTableInit(&NewHt);
HashNode *cur = NULL;
int i = 0;
for (; i < ht->_N; i++)
{
cur = ht->_tables[i];
while (cur)
{
HashTableInsert(&NewHt, cur->_key, cur->_value);
}
}
HashTableDestory(ht);
return &NewHt;
}
else
{
return NULL;
}
}在这一部分中，扩容函数的思路与上一次类似，并且仍然会依次读取数据并进行插入操作。但有一个相对简便的方法，并没有被实现出来：在这一特定情况下，并非使用传统的数组结构来管理内存空间；相反，在链表结构中，并不需要为每个新节点重新分配内存空间（即无需为每个新元素单独开辟存储区域）。当进行扩容操作时，并不是简单地将当前链表直接连接到原有数据之后；相反，在这种设计下可以直接将当前链表连接到现有的数据结构之后（即无需为每个新节点重新分配内存空间）。然而，在实际实现过程中发现：当你尝试通过复制现有数组的方式来扩展内存时（即试图将现有数组的数据直接复制到新的数组中），这种方式并不完全可行：因为当你增加数组大小时，在旧索引位置上的元素会被映射到新的索引位置上（这会导致数据偏移），因此这种方法并不适用
哈希算法的核心思想在于通过优化查找时间使其接近于常数阶的时间复杂度O(1)，然而在实际应用中难以完全实现这一理想状态。在哈希开放定址法中我们通常会引入负载因子的概念，默认情况下负载因子设定为0.7即当数据量达到数组容量的70%时就需要进行动态扩增数组长度以避免冲突情况的发生适当提高负载因子至1.0可以使算法在高密度访问场景下依然保持较好的性能表现