数据结构学习笔记|哈希表
原创
数据结构学习笔记|哈希表
1. 哈希表的概念
在实现LRU缓存管理的时候发现，由于利用了链表，导致find操作十分耗费时间。如果能有一个地方，存储了数据在LRU链表里的地址，那就完美了。
最简单实现方法就是引入一个数组，下标是缓存数据的id，数据保存在数组里。在《数据结构与编程之美》这本书里提了一个运动员的例子，如张三是19号，那么数组player19="张三"。
那么用19来寻找信息的时间复杂度就是O(1)。此时管19这种能够标识一个选手的数叫做key，把参赛人员编号转化为数组下标的函数叫做hash函数。
上面这个例子可以用一个公式来表示：
f(key) = key;如果代入19，那么结果是19，表示19号保存在数组player19里。
业内著名的哈希函数有MD5，CRC这类，但是有个问题，就是hash函数无法绝对避免重复。至于数组下标这种办法，也不可能将数组无限放大，内存毕竟也是有限的。
这就引出了哈希冲突的问题。为了解决这一问题，人们发明了开放寻址法和链表法两种。
2. 链表法解决哈希冲突
Hash(key)的计算结果可能出现重复，比如Hash(5)=11，而Hash(9)也等于11。此时如果想将这俩塞进一个数组位置，那就是不可能了。
但是格局打开，数组还是那个数组，只是数组里不要存具体的值了，而是存链表的头节点地址。把hash值一样的结点放在链表里不就好了么？
下图里那些链表里存的key，其hash值都一样。这样在寻找的时候，理论上时间复杂度就不是O(1)了，而是由链表的长度k决定。
这里定义几个变量：
- n：哈希表中的数据个数
- m：哈希表中槽的个数
这样就能看出来，k=n/m。如果k不是很大，那么其实find的时间复杂度并不会太高。这个k就叫做load factor，翻译做装载因子。
对于一个设计的比较好的hash函数来说，也不会出现有的slot的链表超长而有的slot完全没有链表的情况。
再看看装载因子的公式k=n/m，可以直观的发现，n实际是随着缓存的数据增长越来越大，那么k也就越来越大，这样查询时间复杂度也就越来越高。
为了解决这个问题，在数学上来看，就是增加m的大小，也就是对槽数组扩容。这个问题留待以后慢慢说。
3. 实现简单的哈希表
为了说明哈希表的实现，上面那个图还需要进一步的改进：
hash链表的实现，就是一个简单的双向链表，其实可以用单向链表：
struct hashNode {
int key; // 简单起见，都用int
char value;
hash_node_t next;
hash_node_t prev;
};
typedef struct hashNode *hash_node_t, HashNode;然后是hash表的实现，主要有三个元素：
- bucket：即slot，就是槽的编号，比如我申请一个size=4的哈希表，哈希函数是mod(x, 4)的话，那么每个slot的编号就是0-3的任意值；
- hashfunc：哈希函数，比如刚才说的mod(x, n)；
- hash_node_t*：指向链表头结点的指针（指向指针的指针），C的好处就是数组可以用指针的形式声明。
初始化hash表的逻辑就是申请一段内存空间，给定初始值：
// 定义一个函数类型
typedef unsigned int (*hashfunc_t)(unsigned int, int);
// hash函数
unsigned int hashfunc(unsigned int buckets, int key) {
return key % buckets;
}
hash_t initHashTable(unsigned int buckets, hashfunc_t hashfunc) {
hash_t head = (hash_t) malloc(sizeof (HashTable));
head->hashfunc = hashfunc;
head->buckets = buckets;
// 槽数组的声明，size有bucket个足矣
head->hash_node = (hash_node_t*) malloc(buckets);
return head;
}接下来就是add的定义，其函数定义大概也不会离开这个形式：void add(hash_t hash_table, int key, char value)，而其逻辑应该是：
- 根据key计算hash值，用hash值寻找到对应的slot；
- 如果slot指向为空，则将该数据插入此slot中（作为头结点）；
- 若果slot指向不为空，则用头插法将数据插入此slot指向的链表的头部
hash_node_t* get(int key, hash_t hash_table) {
//1. 计算hash值
unsigned int bucket = hash_table->hashfunc(hash_table->buckets, key);
//2. 从hash表中取链表的头结点
return &(hash_table->hash_node[bucket]);
}
void add(hash_t hashTable, int key, int value) {
//1. 构建链表结点
auto node = (hash_node_t) malloc(sizeof(HashNode));
node->key = key;
node->value = value;
//2. 计算hash值，找头结点，如果没有头结点则此node作为头结点，找到则用头插法
hash_node_t* hashNode = get(key, hashTable);
unsigned int bucket = hashTable->hashfunc(hashTable->buckets, key);
if (*hashNode == nullptr) {
hashTable->hash_node[bucket] = node;
} else {
node->next = *hashNode;
(*hashNode)->prev = node;
(*hashNode) = node;
}
}hash表主要想解决的问题就是查找，查找主要的逻辑和上面的get函数一样，只是后面还有一个步骤，即找到了链表则遍历链表直到找到指定的节点：
hash_node_t get_node(hash_t hash_table, int value, int key) {
// 寻找key所在的slot指向的链表
hash_node_t * hash_node = get(key, hash_table);
// 链表指向为空，即没有缓存过
if (hash_node == nullptr) {
printf("未找到！\n");
return nullptr;
}
//头指针指向链表头部
hash_node_t p = *hash_node;
//开始遍历链表
while (p != nullptr) {
if (p->value == value) {
return p;
}
if (p->next == nullptr && p->value != value) {
printf("未找到！\n");
}
p = p->next;
}
return nullptr;
}由此可以看出，哈希表的核心就是数组。这里实现的hash表用的hash函数是取模这种简单的形式，每个slot指向的链表长度最终会相等。
再来审视一下我这个实现，如果初始化时的capacity=4，那么就是m=4，套到公式里，如果我写入8个数据，k=8/4=2。
4. hash表的扩容
之前说过哈希表的load factor随着数据的增加而越来越大，hash表的查询效率也会越来越低。必要的时候就要对hash表进行扩容。
回到上面的例子，原本的hash表如果初始申请size=4，那么扩容的时候最好采用double的形式直接翻倍。比如key=5的，原本会被分配到slot1里，key=9的也会分配到slot1，扩容后只用搬迁key=5的到slot5，key=9则不用动。
这样只有一半的元素会被搬迁，代价会小一些。
在背诵面试八股文的时候，对Java的HashMap总会提到这么几个概念：
- HashMap默认大小是16；
- HashMap默认load factor是0.75，当HashMap元素数量超过0.75*capacity时，HashMap会翻倍扩容；
- JDK8之后，如果链表长度大于8，则会使用红黑树来解决hash冲突问题。
那么HashMap的扩容就会发生在第12次put之后。
不过我看到这里之后有一点迷惑：load factor每到0.75就会触发扩容，那么链表的长度完全没机会达到8。
后来想了想，我是被之前自己的例子搞迷惑了，不可能所有的hash函数都抱着数据均匀分布的，在一些极端场景下，hash表就干脆退化成了一个链表（slot的数量为n，但是hash计算出的值集中在其中一个slot上）。
回到HashMap，极端情况下，12个元素都在一个slot上，此时的load factor也就堪堪够到0.75而已。
查阅了一些资料，普遍提到load factor是一个介于0到1之间的数字。不过从我的测试来看，我自己之前实现的load factor在写入8个key的时候就已经达到2了，但是此时的查询时间复杂度也不过就是O(2)，也不高，甚至load factor到10也不过就是遍历一个length=10的链表罢了，并不算太严重的问题。
所以说，使用链地址法解决hash冲突的时候是有很大的优势的。而如果用开放寻址法则要注意保持load factor小于1。
当然，这也在《数据结构与算法之美》这本书里有提到：
基于开放寻址法解决冲突的哈希表，装载因子不能太大，必须小于 1，而基于链表法解决冲突的哈希表，装载因子可以大于 1。
5. 用hash表优化LRU链表
之前提到过链表最大的痛就是他的find方法的时间复杂度是O(n)，从而导致remove的时间复杂度也很高。
那么优化的办法之前也提到过就是用一个hash表来保存 LRU 链表的结点位置，这样可以做到 O(1)级别的操作，只是需要一些额外的空间，如果是缓存这种重要的链表，那么这点空间还是值得去消耗的。
其实的逻辑大概是：
- 用hash函数计算出 key 的哈希值bucket；
- 遍历对应 bucket 的链表，直到找到需要的node
用代码表示：
hash_node_t get_node(hash_t hash_table, int value, int key) {
// 寻找key所在的slot指向的链表
hash_node_t * hash_node = get(key, hash_table);
// 链表指向为空，即没有缓存过
if (hash_node == nullptr) {
printf("未找到！\n");
return nullptr;
}
//头指针指向链表头部
hash_node_t p = *hash_node;
//开始遍历链表
while (p != nullptr) {
if (p->value == value) {
return p;
}
if (p->next == nullptr && p->value != value) {
printf("未找到！\n");
}
p = p->next;
}
return nullptr;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。