首页 > 代码库 > 哈希表简易入门

哈希表简易入门

2024-07-16 08:48:00   225人阅读

什么是哈希表

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。哈希表作为一种高效的数据结构，有着广泛的应用。如果哈希函数设计合理，理想情况下每次查询的时间花费仅仅为 O(h/r)，即和哈希表容量与剩余容量的比值成正比。只要哈希表容量达到实际使用量的大约 1.5 倍以上，查询花费的时间基本就可以认为恒为 O(1)。

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名x到首字母F(x)的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”F()是这个例子中的哈希函数，存放首字母的表对应哈希表。关键字和哈希函数可以任意选择。在竞赛中的哈希函数一般是直接把关键字对一个素数取模（简单粗暴）。

 

与平衡二叉树的类比

Map是STL的一个关联容器，它提供一对一的数据处理能力（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）。它的内部实现是一个红黑树（红黑树是平衡二叉树的一种），平衡二叉树中的部所有的数据都是有序的，并且可以通过O(logn)的复杂度查找、插入或删除一个关键字。而在理想情况下，哈希表可以用O(1)的复杂度查找、插入一个关键字。

 

处理碰撞

对不同的关键字可能得到同一散列地址，即k_1 != k_2，而f(k_1)=f(k_2)，这种现象称碰撞（Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。

处理碰撞的方法有很多，在竞赛中一般采用单独链表法：将哈希到同一个存储位置的所有元素保存在一个链表中。在实现中一般用一个数组来代替链表。

 

算法实现

我们通过山寨一个STL Map来加深对哈希表的理解。

map常用操作有两种：

  1. 查询map中是否含有给定关键字Key；
  2. 将(Key,Value)插入到map中。如果map中已经存在Key，那么就用新的Value覆盖旧的值。

 

 1 typedef long long LL; 2 typedef LL KT;// Key的类型 3 typedef LL VT;// Value的类型 4 class Hash_Map { 5 private: 6     static const int SEED = 29989;// 一个比实际容量稍大的素数 7     static const int MAXN = 30000;// 哈希表最大的元素个数 8     struct ELEM {// 定义链表的数据类型 9         KT key;// 元素的关键字10         VT value;// 元素的值11         int next;// 指向链表的下一个位置12     }elems[MAXN];// 链表所使用的数组13     int head[SEED], cur;// 表头与元素个数14     int hash(KT key){// 哈希函数15         return key % SEED;16     }17 public:18     Hash_Map() {// 构造函数19         clear();20     }21     void clear() {// 初始化哈希表22         cur = 0;23         memset(head,-1,sizeof(head));24     }25     void insert(KT key, VT value) {// 插入一个关键字26         int h = hash(key);// 用哈希函数计算关键字在哈希表中的地址27         for (int i=head[h]; i!=-1; i=elems[i].next) {// 遍历哈希值为h的链表中的所有元素28             if (key==elems[i].key) {// 如果key已经存在29                 elems[i].value = http://www.mamicode.com/value;// 覆盖旧的value30                 return;31             }32         }33         // key不存在，则将其插入链表34         elems[cur].value =http://www.mamicode.com/ value;35         elems[cur].key = key;36         elems[cur].next = head[h];37         head[h] = cur++;38     }39     VT find(KT key) {40         int h = hash(key);41         for (int i=head[h]; i!=-1; i=elems[i].next) {42             if (key==elems[i].key) {43                 return elems[i].value;44             }45         }46         return -1;47     }48 }hs;

 


联系
我们