构造哈希表的基本方法

1、除留余数法

例如 Hash(Key) = Key%P

值得注意的是, P 必须为质数。若 P 中含有质因子,则所有含同一个质因子的 Key 均会被映射到该地址。

冲突处理

当两个 Key 的 Hash() 值相同时,即视作冲突。遇到冲突时通常有以下几种应对方法。

1、开放定址法

若令 Hashᵢ = (Hash(Key)+dᵢ)%M,i = (1,2,3,…,M-1) ,其中 Hash(Key) 为哈希函数,M为哈希表长,dᵢ为增量序列。

  • 若取 dᵢ = (1,2,3,…,m-1),则称为线性探测再散列;
  • 若取 dᵢ = (1²,-1²,2²,-2²,…,±k²),则称为二次探测再散列。二次探测再散列在内存中左右探测,更加灵活。
  • 若取 dᵢ 为伪随机数序列,则称为伪随机探测再散列。

在读取哈希表时,若遇到读取的地址存储的Key和欲读取的Key不同,则按照相应的探测方法寻找下一个地址。

2、链地址法

将所有按给定的哈希函数求得的哈希地址相同的关键字存储在同一线性链表中,且使链表按关键字有序。

哈希表示意图
哈希表示意图

由链地址法存储的哈希表可以视为一个数组+多个链表的结构。

在读取哈希表时,如果定位到的数组位置不含链表,那么仅需一次寻址。否则遍历链表逐一查找。

3、公共溢出区法

将所有发生冲突的项放入公共溢出区中。

若查找时 Key 不相等,则遍历公共溢出区。

3 个评论

  1. Java的链表实现里有个Entry类,当Entry的Netx==Null的时候即代表读取到的位置莫得冲突,否则就可以根据Key遍历

    static class Entry implements Map.Entry {
    final K key;
    V value;
    Entry next;
    int hash;

    /**
    * Creates new entry.
    */
    Entry(int h, K k, V v, Entry n) {
    value = v;
    next = n;
    key = k;
    hash = h;
    }

发表评论

邮箱地址不会被公开。 必填项已用*标注