哈希表 (Hash table, 也叫散列表), 是根据关键码值(Key value) 而直接进行访问的数据结构也就是说, 它通过把关键码值映射到表中一个位置来访问记录, 以加快查找的速度这个映射函数叫做散列函数, 存放记录的数组叫做散列表
顺序搜索以及二叉树搜索树中, 元素存储位置和元素各关键码之间没有对应的关系, 因此在查找一个元素时, 必须要经过关键码的多次比较搜索的效率取决于搜索过程中元素的比较次数
理想的搜索方法: 可以不经过任何比较, 一次直接从表中得到要搜索的元素
如果构造一种存储结构, 通过某种函数 (hashFunc) 使元素的存储位置与它的关键码之间能够建立一一映射的关系, 那么在查找时通过该函数可以很快找到该元素
当向该结构中:
插入元素时: 根据待插入元素的关键码, 以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素时: 对元素的关键码进行同样的计算, 把求得的函数值当做元素的存储位置, 在结构中按此位置取元素比较, 若关键码相等, 则搜索成功
该方式即为哈希 (散列) 方法, 哈希方法中使用的转换函数称为哈希 (散列) 函数, 构造出来的结构称为哈希表(Hash Table)(或者
称散列表)
例如: 数据集合{180,750,600,430,541,900,460}
用该方法进行搜索不必进行多次关键码的比较, 因此搜索的速度比较快
问题: 按照上述哈希方式, 向集合中插入元素 443, 会出现什么问题?
这回就要引出一个概念叫哈希冲突: 对于两个数据元素的关键字 和 (i !=j), 有 != , 但有: HashFun(Ki) == HashFun(Kj)即不同关键字通过相同哈希哈数计算出相同的哈希地址, 该种现象称为哈希冲突或哈希碰撞把具有不同关键码而具有相同哈希地址的数据元素称为同义词
解决哈希冲突两种常见的方法是: 闭散列和开散列
闭散列:
闭散列: 也叫开放地址法, 当发生哈希冲突时, 如果哈希表未被装满, 说明在哈希表中必然还有空位置, 那么可以把 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). 如果该位置中没有元素则直接插入新元素; 如果该位置中有元素且和待插入元素相同, 则不用插入; 如果该位置中有元素但不是待插入元素则发生哈希冲突, 使用线性探测找到下一个空位置, 插入新元素;
采用线性探测, 实现起来非常简单, 缺陷是:
一旦发生哈希冲突, 所有的冲突连在一起, 容易产生数据堆积, 即: 不同关键码占据了可利用的空位置, 使得寻找某关键码的位置需要许多次比较, 导致搜索效率降低 如何缓解呢? 引入新概念负载因子 (负载因子的应用在下一篇博文) 和二次探测
二次探测
发生哈希冲突时, 二次探查法在表中寻找下一个空位置的公式为:
Hi= (Ho + i^2) % m,Hi = (Ho -i^2 ) % m, i = 1,2,3,(m-1)/Ho. 是通过散列函数 Hash(x)对元素的关键码 key 进行计算得到的位置, m 是表的大小假设数组的关键码为 37, 25, 14, 36, 49, 68, 57, 11, 取 m = 19, 这样可设定为 HT[19], 采用散列函数 Hash(x) = x % 19, 则:
- Hash(37)=18
- Hash(25)=6
- Hash(14)=14
- Hash(36)=17
- Hash(49)=11
- Hash(68)=11
- Hash(57)=0
- Hash(11)=11
采用二次探测处理哈希冲突:
研究表明: 当表的长度为质数且表装载因子 a 不超过 0.5 时, 新的表项一定能够插入, 而且任何一个位置都不会被探查两次因此只要表中有一半的空位置, 就不会存在表满的问题在搜索时可以不考虑表装满的情况, 但在插入时必须确保表的装载因子 a 不超过 0.5; 如果超出必须考虑增容
开散列法又叫链地址法(开链法)(将在下一篇博文中写出)
开散列法: 首先对关键码集合用散列函数计算散列地址, 具有相同地址的关键码归于同一子集合, 每一个子集合称为一个桶, 各个桶中的元素通过一个单链表链接起来, 各链表的头结点存储在哈希表中
设元素的关键码为 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
使用哈希函数计算出每个元素所在的桶号, 同一个桶的链表中存放哈希冲突的元素
通常, 每个桶对应的链表结点都很少, 将 n 个关键码通过某一个散列函数, 存放到散列表中的 m 个桶中, 那么每一个桶中链表的平均长度为以搜索平均长度为的链表代替了搜索长度为 n 的顺序表, 搜索效率快的多
应用链地址法处理溢出, 需要增设链接指针, 似乎增加了存储开销事实上:
由于开地址法必须保持大量的空闲空间以确保搜索效率, 如二次探查法要求装载因子 a <= 0.7, 而表项所占空间又比指针大的多, 所以使用链地址法反而比开地址法节省存储空间
引起哈希冲突的一个原因可能是: 哈希函数设计不够合理
哈希函数设计原则:
. 哈希函数的定义域必须包括需要存储的全部关键码, 而如果散列表允许有 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");
- }
- 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);
- }
来源: http://www.bubuko.com/infodetail-2510694.html