数据结构学习笔记|哈希表

数据结构学习笔记|哈希表

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)，而其逻辑应该是：

1. 根据key计算hash值，用hash值寻找到对应的slot；
2. 如果slot指向为空，则将该数据插入此slot中（作为头结点）；
3. 若果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)级别的操作，只是需要一些额外的空间，如果是缓存这种重要的链表，那么这点空间还是值得去消耗的。

其实的逻辑大概是：

1. 用hash函数计算出 key 的哈希值bucket；
2. 遍历对应 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;
}