这是一个创建于 2484 天前的主题，其中的信息可能已经有所发展或是发生改变。
哈希表（ Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
顺序搜索以及二叉树搜索树中，元素存储位置和元素各关键码之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
插入元素时：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素时：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者
称散列表)
例如：数据集合{180，750，600，430，541，900，460}
解决哈希冲突两种常见的方法是：闭散列和开散列
闭散列：
闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到表中“下一个” 空位中去
那如何寻找下一个空余位置？ 这里就要用到两种方法：线性探测和二次探测
线性探测
设关键码集合为{37, 25, 14, 36, 49, 68, 57, 11}，散列表为 HT[12]，表的大小 m = 12，假设哈希函数为：Hash(x) = x %p （ p = 11，是最接近 m 的质数），就有：
Hash(37) = 4
Hash(25) = 3
Hash(14) = 3
Hash(36) = 3
Hash(49) = 5
Hash(68) = 2
Hash(57) = 2
Hash(11) = 0
其中 25，14，36 以及 68，57 发生哈希冲突，一旦冲突必须要找出下一个空余位置
线性探测找的处理为：从发生冲突的位置开始，依次继续向后探测，直到找到空位置为止
[插入]
1 ）. 使用哈希函数找到待插入元素在哈希表中的位置
2 ）. 如果该位置中没有元素则直接插入新元素；如果该位置中有元素且和待插入元素相同，则不用插入；如果该位置中有元素但不是待插入元素则发生哈希冲突，使用线性探测找到下一个空位置，插入新元素；
采用线性探测，实现起来非常简单，缺陷是：
一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。 如何缓解呢？ 引入新概念负载因子（负载因子的应用在下一篇博文）和二次探测
开散列法又叫链地址法(开链法)。（将在下一篇博文中写出） 开散列法：首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
设元素的关键码为 37, 25, 14, 36, 49, 68, 57, 11, 散列表为 HT[12]，表的大小为 12，散列函数为 Hash(x) = x % 11
Hash(37)=4
Hash(25)=3
Hash(14)=3
Hash(36)=3
Hash(49)=5
Hash(68)=2
Hash(57)=2
Hash(11)=0
使用哈希函数计算出每个元素所在的桶号，同一个桶的链表中存放哈希冲突的元素。
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。 哈希函数设计原则： **.**哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间 **.**哈希函数计算出来的地址能均匀分布在整个空间中 **.**哈希函数应该比较简单 下面简单介绍了一些哈希函数： 1.直接定址法 取关键字的某个线性函数为散列地址：Hash （ Key ）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 适合查找比较小且连续的情况 2.除留余数法 设散列表中允许的地址数为 m，取一个不大于 m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址 3.平方取中法 假设关键字为 1234，对它平方就是 1522756，抽取中间的 3 位 227 作为哈希地址； 再比如关键字为 4321，对它平方就是 18671041，抽取中间的 3 位 671(或 710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况 4.折叠法 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况 5.随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key) = random(key),其中 random 为随机数函数通常应用于关键字长度不等时采用此法 6.数学分析法 设有 n 个 d 位数，每一位可能有 r 种不同的符号，这 r 种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。 例如：假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前 7 位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如 1234 改成 4321)、右环位移(如 1234 改成 4123)、左环移位、前两数与后两数叠加(如 1234 改成 12+34=46)等方法 说了这么多概念，来看看代码。 哈希表的结构定义：
typedef int KeyType;
typedef int ValueType;
typedef enum Status
{
EMPTY,
EXIST,
DELETE,
}Status;
typedef struct HashNode
{
KeyType _key;
ValueType _value;
Status _status;
}HashNode;
typedef struct HashTable
{
HashNode *_table;
size_t _size;
size_t _N;
}HashTable;
哈希表的初始化：
void HashTableInit(HashTable* ht) //初始化
{
size_t i = 0;
assert(ht);
ht->_size = 0;
ht->_N = HashTablePrime(0);
ht->_table = (HashNode *)malloc(sizeof(HashNode)*ht->_N);
assert(ht->_table);
for (i=0; i<ht->_N; i++)
ht->_table[i]._status = EMPTY;
}
哈希函数：
KeyType HashFunc(KeyType key,size_t n)
{
return key%n;
}
看看哈希表的插入：（这里处理哈希冲突时采用线性探测，二次探测将在下一次博客中写出） 扩容时要特别注意，不能简单的用 malloc 和 realloc 开出空间后直接付给哈希表，一定记得扩容之后需要重新映射原表的所有值。
int HashTableInsert(HashTable* ht, KeyType key, ValueType value) //插入
{
KeyType index = key;
assert(ht);
**if (ht->_N == ht->_size) //扩容
{
KeyType index;
size_t newN = HashTablePrime(ht->_N);
HashNode *tmp = (HashNode *)malloc(sizeof(HashNode)*newN);
size_t i = 0;
assert(tmp);
//HashTablePrint(ht); //扩容调试使用
for (i=0; i<newN; i++)
tmp[i]._status = EMPTY;
for (i=0; i<ht->_N; i++) //扩容之后把以前的表中元素重新映射
{
if (ht->_table[i]._status == EXIST) //原表存在时
{
index = HashFunc(ht->_table[i]._key,newN);
if (tmp[index]._status == EXIST) //发生哈希冲突时
{
while (1)
{
index +=1;
if ((size_t)index > newN)
index %= newN;
if (tmp[index]._status != EXIST)
break;
}
}
tmp[index]._key = ht->_table[i]._key;
tmp[index]._value = ht->_table[i]._value;
tmp[index]._status = EXIST;
}
else
tmp[i]._status = ht->_table[i]._status;
}
ht->_table = tmp;
ht->_N = newN;
}**
index = HashFunc(key,ht->_N);
if (ht->_table[index]._status == EXIST) //发生哈希冲突
{
size_t i = 0;
for (i=0; i<ht->_N;i++ )
{
if (ht->_table[index]._key == key)
return -1;
index +=i;
if ((size_t)index >ht->_N)
index %= ht->_N;
if (ht->_table[index]._status != EXIST)
break;
}
}
ht->_table[index]._key = key;
ht->_table[index]._value = value;
ht->_table[index]._status = EXIST;
ht->_size++;
return 0;
}
哈希表的查找：
HashNode* HashTableFind(HashTable* ht, KeyType key) //查找
{
size_t i = 0;
KeyType index = key;
assert(ht);
index = HashFunc(key,ht->_N);
if (ht->_table[index]._key == key)
return &(ht->_table[index]);
else
{
for (i=0; i<ht->_N; i++)
{
index += i;
if (ht->_table[index]._key == key)
return &(ht->_table[index]);
if (ht->_table[index]._status == EMPTY)
return NULL;
}
}
return NULL;
}
哈希表的删除：
int HashTableRemove(HashTable* ht, KeyType key) //删除
{
assert(ht);
if(HashTableFind(ht,key))
{
HashTableFind(ht,key)->_status = DELETE;
return 0;
}
else
return -1;
}
哈希表的销毁：（使用了 malloc 开辟空间必须手动销毁）
void HashTableDestory(HashTable* ht)//销毁
{
free(ht->_table);
ht->_table = NULL;
ht->_size = 0;
ht->_N = 0;
}
哈希表的打印：
void HashTablePrint(HashTable *ht) //打印 hash 表
{
size_t i = 0;
assert(ht);
for (i=0; i<ht->_N; i++)
{
if (ht->_table[i]._status == EXIST)
printf("[%d]%d ",i,ht->_table[i]._key);
else if (ht->_table[i]._status == EMPTY)
printf("[%d]E ",i);
else
printf("[%d]D ",i);
}
printf("\n\n");
}
哈希表整个在插入这块会比较ran，要仔细理解，特别是扩容那块。
测试案例：
void TestHashTable()
{
HashTable ht;
HashTableInit(&ht);
HashTableInsert(&ht,53,0);
HashTableInsert(&ht,54,0);
HashTableInsert(&ht,55,0);
HashTableInsert(&ht,106,0);
HashTableInsert(&ht,1,0);
HashTableInsert(&ht,15,0);
HashTableInsert(&ht,10,0);
HashTablePrint(&ht);
printf("%d ",HashTableFind(&ht,53)->_key);
printf("%d ",HashTableFind(&ht,54)->_key);
printf("%d ",HashTableFind(&ht,10)->_key);
printf("%d ",HashTableFind(&ht,15)->_key);
printf("%p ",HashTableFind(&ht,3));
printf("\n\n");
HashTableRemove(&ht,53);
HashTableRemove(&ht,54);
HashTableRemove(&ht,106);
HashTableRemove(&ht,10);
HashTableRemove(&ht,5);
HashTablePrint(&ht);
HashTableInsert(&ht,53,0);
HashTableInsert(&ht,54,0);
HashTableInsert(&ht,106,0);
HashTablePrint(&ht);
HashTableDestory(&ht);
HashTablePrint(&ht);
}
测试结果：
更多内容请关注本文博客：请戳关注链接 如需转载和翻译请联系本人。
Select Language