Advanced Hashing

rehashing

我们为什么要进行 rehashing？

• 解决碰撞问题
• 扩大 hash table 的大小
• 我们希望的是让链表尽量变小,仅仅包含几个元素

实现:

void rehash()
{
    int oldCapacity = capacity;
    HashNode** oldTable = hashTable;
    capacity *= 2;
    hashTable = new HashNode*[capacity]();
    for (int i = 0; i < oldCapacity; i++)
    {
        HashNode* curr = oldTable[i];
        while (curr!= nullptr)
        {
            HashNode* next = curr->next;
            int hash = hashCode(curr->data);
            curr->next = hashTable[hash];
            hashTable[hash] = curr;
            curr = next;
        }
    }
    delete[] oldTable;
}

1. 首先，我们将原来的 hash table 的大小扩大为原来的两倍。
2. 然后，我们创建一个新的 hash table，大小为原来的两倍。
3. 我们遍历原来的 hash table，将每个元素重新插入到新的 hash table 中。
4. 最后，我们删除原来的 hash table。

hashCode and equality

一个 hashCode 函数应该具有以下特点:

• 输入同一个 date,返回的值一定要是一样的

• 输出不同的 date,返回的值一定是不一样的

一个 good hashcode 函数应该具有以下特点:

• 简单

• 均匀分布

• 避免碰撞

• 快速

---

hash string

对于字符的 hashing,稍微复杂一点,对于二十六个字母,出现的频次并不相同

我们加入加权会显得更好一点

就像这样:

int hashCode(string str)
{
    int hash = 5381;
    for (int i = 0; i < str.length(); i++)
    {
        hash = 31 * hash + (int)str[i];
    }
    return hash;
}

这是其实就是 java 中的 hashing string

这明显减少了碰撞的发生

但是其中也是有代价的:计算量大,时间复杂度高

Another use

不仅在计算机界 hashing 的作用很大,在密码学届 hashing 的作用也很大

1. 加密: 加密算法的目的就是为了防止信息被窃取,所以加密算法的 hash 函数的设计就需要考虑到安全性
2. 密码学: 密码学的 hash 函数的设计就需要考虑到安全性,因为密码学的应用场景就是保密性

拓展:cuckoo hashing(布谷鸟哈希)

这是一种高效的哈希表实现方法，旨在减少哈希冲突并提高查找、插入和删除操作的效率。布谷鸟哈希的核心思想来源于布谷鸟在筑巢时的行为，即如果一个位置被占用，布谷鸟会将那个位置的原有鸟蛋移走，然后在移走的鸟蛋的位置继续寻找空位或再次移走现有的鸟蛋。这种机制被用来管理哈希表中的冲突。