首页 > 代码库 > 散列表
散列表
散列表是一种ADT。散列表的实现常常叫做散列(hashing),它是一种用于以常数平均时间执行插入、删除、查找的技术。需要元素间任何排序信息的操作将不会得到有效的支持。例如FindMax、FindMax、按序输出等。
散列表的关键是确定散列函数,《数据结构与算法分析》中提到了几种散列函数,但都不是完美的。能解决冲突但有可能散列表占用率不高。字符串中的字符不是随机出现,这也影响到了散列表的利用率。散列函数需要满足的要求:
- 尽量把键值均匀分布
- 散列函数必须容易计算
书中提到了一个好的散列函数,剩下的问题就是对冲突的消除,两种简单的方法:
- 分离链接法(开散列):将散列到同一个值的所有元素保留到一个链表中。
- 开放定址法(闭散列):如果发生冲突,选择另外的单元,直到找出空单元。
分离链接法:
插入操作时,一般将新元素插入到对应表的前端,不仅因为方便,而且还因为新近插入的元素最有可能最先被访问。下面是代码:
#include <stdio.h> typedef int ElementType; typedef struct ListNode *Position; struct ListNode { ElementType Element; Position Next; }; typedef struct HashTbl *HashTable; struct HashTbl { int TableSize; Position *TheLists; // 指针数组 }; HashTable InitializeTable(int TableSize) { HashTable ht; int i; ht = malloc(sizeof(struct HashTbl)); if (ht == NULL) return -1; ht->TableSize = TableSize; ht->TheLists = calloc(TableSize, sizeof(Position)); if (ht->TheLists == NULL) return -1; return ht; } // 散列函数 int Hash(ElementType Key, int TableSize) { return Key % TableSize; } Position Find(HashTable H, ElementType Key) { Position p; p = H->TheLists[Hash(Key, H->TableSize)]; while (p != NULL && p->Element != Key) // 这里只能对数值型key进行比较 p = p->Next; return p; } // 键值不允许重复 void Insert(HashTable H, ElementType Key) { Position *p; // 如果不使用这个双重指针,那么需要计算多次散列函数 Position tmp; if (Find(H, Key) == NULL) // 元素不存在 { // 插入链表头部 p = &(H->TheLists[Hash(Key, H->TableSize)]); tmp = malloc(sizeof(struct ListNode)); tmp->Element = Key; tmp->Next = *p; *p = tmp; } } int main(void) { HashTable table; Position p; table = InitializeTable(100); Insert(table, 21); Insert(table, 24); Insert(table, 43); Insert(table, 35); p = Find(table, 43); if (p != NULL) printf("Find it!\n"); else printf("Not found!\n"); return 0; }
这个程序改了我半天,其中有个很隐蔽的问题,就是在插入节点时指针的修改。书中给每个链表都添加了一个头节点,使得插入变得方便,这里我把头节点去掉以节省空间,但为了能够正确插入,我引入了一个双重指针Position *p。
分离链接法的缺陷在于使用了指针,以及需要动态分配空间,造成了速度上的减慢。
开放定址法:
- 线性探测法:发生冲突,顺序查找空闲地址,容易发生一次聚集。
- 平方探测法:排除一次聚集,但散列到同一个位置上的元素将探测相同的备选单元,这称为二次聚集。
- 双散列:用另一个散列函数解决冲突,但计算需要花费代价。
平方探测代码:
#include <stdio.h> typedef int ElementType; typedef int Position; enum KindOfEntry { Legitimate, Empty, Deleted }; struct HashEntry { ElementType Element; enum KindOfEntry Info; }; typedef struct HashTbl *HashTable; struct HashTbl { int TableSize; struct HashEntry *array; }; HashTable InitializeTable(int TableSize) { HashTable H; int i; H = malloc(sizeof(struct HashTbl)); if (H == NULL) return -1; H->TableSize = TableSize; H->array = malloc(TableSize * sizeof(struct HashEntry)); if (H->array == NULL) return -1; for (i = 0; i < TableSize; i++) H->array[i].Info = Empty; return H; } Position Hash(ElementType Key, int TableSize) { return Key % TableSize; } Position Find(HashTable H, ElementType Key) { Position p; int num = 0; p = Hash(Key, H->TableSize); while (H->array[p].Info != Empty && H->array[p].Element != Key) { p += ++num * 2 -1; // 平方操作可以优化 if (p >= H->TableSize) p -= H->TableSize; // 绕回去 } return p; // 返回找到的索引或一个正确的插入位置 } void Insert(HashTable H, ElementType Key) { Position p; p = Find(H, Key); if (H->array[p].Info != Legitimate) // 如果找到的位置未被占用,则插入 { H->array[p].Element = Key; H->array[p].Info = Legitimate; } } void Delete(HashTable H, ElementType Key) // 删除操作采用慵懒删除 { Position p; p = Find(H, Key); if (H->array[p].Info == Legitimate) H->array[p].Info = Deleted; } int main(void) { HashTable table; Position p; table = InitializeTable(20); Insert(table, 3); Insert(table, 1); Insert(table, 23); Insert(table, 34); Insert(table, 8); p = Find(table, 34); if (table->array[p].Info == Legitimate) printf("%d", table->array[p].Element); return 0; }
这里可以使用一个技巧省略平方操作:
p += ++num * 2 -1;
要求的值是基于前面的结果,避免了重复计算。乘以2相当于移位操作,效率很高。每一个节点HashEntry都保存有实际存储元素和当前状态Info,方便插入和删除操作。
参考:
《数据结构与算法分析》 P111.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。