Hashing

introduction

在正常情况下,set 中查找的时间复杂度为 O(n),而在 hashset 中查找的时间复杂度为 O(1).

其中的原理就是:

首先,将 set 中的元素通过 hash 函数映射到一个有限的空间中,得到一个索引值.
然后,通过索引值,在 hashset 中查找元素.

就相当于,不需要遍历,你就知道数据存储在哪个位置

hashing

hash这个单词在计算机科学中被广泛使用

定义: 一个函数,它接受一个输入,并返回一个固定大小的输出值,该输出值被称为hash value或hash code
特点:
- 一致性: 对于相同的输入,得到的输出值必须相同
- 高效性: 计算 hash 值的时间复杂度应该尽可能低
- 均匀性: 对于不同的输入,得到的输出值应该尽可能均匀分布

常见的方法有取绝对值

可是这样做会有一个问题

这个问题就是碰撞: 不同的输入得到相同的输出值

处理方法:

探测: 当碰撞发生时,通过另一个函数来计算下一个索引值,直到找到一个空的位置

但是我十分不认同这个方法

如果这样的话,你的程序随着数据越来越多,就会原来越慢,组件的趋向于 O(n)

分离链接法: 在这里数组的每一个索引处,并非存储单一的值而是存储了一个链表

c++

struct HsahNode {
    int data;
    HashNode* next;
}

这个方法的好处就在于,你永远不会用完空间

rehashing

当 hashset 中的元素越来越多时,hashset 的性能会下降,这时就需要进行rehashing操作

rehashing的过程就是,将原来的 hashset 中的元素重新 hash 到新的 hashset 中

扩容: 原来的 hashset 的大小变为原来的两倍,并重新 hash
收缩: 原来的 hashset 的大小变为原来的一半,并重新 hash

以下是伪代码:

rehashing(hashset):
    if size > 2 * capacity:
        new_capacity = 2 * capacity
    else:
        new_capacity = capacity
    new_hashset = create_hashset(new_capacity)
    for i in range(capacity):
        if hashset[i]!= NULL:
            for j in hashset[i]:
                insert(new_hashset, j)
    return new_hashset

Hashing ​

introduction ​

hashing ​

rehashing ​

Hashing

introduction

hashing

rehashing