哈希表的概念与哈希冲的突解决方法

1 哈希表的概念

哈希表 (Hash Table),也称为散列表,是一种实现关联数组的抽象数据结构,该结构基于散列函数将键 (Key) 映射到存储值 (Value) 的位置,从而快速查找和访问数据。

在哈希表中,存在一个称为“哈希表数组”的数据结构,该数组是一个固定大小的存储桶 (Bucket) 数组。每个存储桶可以容纳一个或多个键值对。当需要插入、查找或删除一个键值对时,通过散列函数计算键的哈希码,找到对应的存储桶,然后在该存储桶中进行操作。因此,哈希表的性能主要取决于散列函数的选择和处理冲突的方法。

哈希表的概念图

2 哈希冲突解决

由于哈希表的哈希函数可能将不同的键映射到相同的哈希码(称为冲突),因此需要解决冲突的问题。常用的解决冲突的方法有以下几种。

2.1 链地址法 (Separate Chaining)

链地址法即在每个存储桶中使用链表或其他数据结构(例如红黑树)保存具有相同哈希码的键值对。

链地址法

链地址法是一种相对简单、易于理解和实现的解决哈希表冲突的方法。它在处理冲突时表现出色,尤其是在负载因子较低的情况下,插入和删除操作性能通常较好。链地址法的优势在于它能够以链表的形式有效地处理相同哈希码的键值对,避免了线性探测或其他复杂的冲突解决方法。

此外,链地址法还具有动态性,允许在运行时动态调整哈希表的大小。由于每个桶(链表头节点)可以根据需要增长或缩减,哈希表能够适应数据量的变化,从而在不浪费过多内存的情况下,保持较好的性能。

然而,链地址法也存在一些缺点需要考虑:

  • 首先,为了存储链表节点或其他数据结构,额外的存储空间是必须的。这可能导致在哈希表存储的键值对数量较少时出现较大的空间开销。对于资源受限的系统或需要高效使用内存的应用场景,这种额外空间开销可能会成为一个问题。
  • 其次,由于链表节点在内存中是分散存储的,这可能导致缓存的不命中率增加,从而降低访问速度。在处理大量数据时,缓存效率的下降可能会显著影响性能。
  • 另外,删除操作可能需要遍历链表来找到目标节点。特别是当链表较长时,删除效率可能较低,因为需要花费更多的时间来定位和删除目标节点。

2.2 开放地址法 (Open Addressing)

开放地址法即在发生哈希冲突时,线性地探测下一个可用的存储桶,直到找到空闲位置为止,或者通过二次探测等方法找到下一个位置。

开放地址法

开放地址法是一种高效的解决哈希表冲突的方法,它不需要额外的存储空间来存储链表节点或其他数据结构,因此在内存使用上更加紧凑。这对于存储大量键值对的哈希表来说,能够减少额外的空间开销。同时,键值对在哈希表中是连续存储的,这也有助于提高缓存的命中率,从而进一步加快数据的访问速度。另外,由于开放地址法不涉及链表的连接和节点的动态分配,删除操作相对简单和高效。

然而,开放地址法也存在一些缺陷需要考虑:

  • 首先,解决冲突的过程相对复杂,特别是在哈希表的负载因子较高时,可能需要更多的探测步骤,增加操作的时间复杂度。
  • 其次,开放地址法可能导致聚集问题,即一些位置会出现连续的冲突,从而影响哈希表的性能。
  • 最后,使用开放地址法实现哈希表时,通常需要预先分配较大的数组来存储键值对。随着键值对数量的增加,可能需要重新调整哈希表的大小(扩容),这会带来一定的额外开销。

3 哈希表开放地址法实现

JDK 中的 HashMap 通过链地址法实现了哈希表,这里不再赘述。本文我们重点关注使用开放地址法实现哈希表。

3.1 常规开放地址法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class HashMapByOpenAddressing<K, V>{

    // Bucket 数组
    @SuppressWarnings({"unchecked"})
    private final Node<K, V>[] table = (Node<K, V>[]) new Node[8];

    // 插入元素
    public void put(K key, V value) {
        int index = key.hashCode() & (table.length - 1);
        if (table[index] == null) {
            // 索引处就是空位,直接放入即可
            table[index] = new Node<K, V>(key, value);
        } else {
            // 从 hash 索引开始,线性向后查找空位
            for (int i = index; i < table.length; i++) {
                if (table[i] == null) {
                    table[i] = new Node<K, V>(key, value);
                    break;
                } else if (i == table.length - 1) {
                    // 扩容
                }
            }
        }
    }

    // 获取元素
    public V get(K key) {
        int index = key.hashCode() & (table.length - 1);
        // 从 index 开始,线性向后查找
        for (int i = index; i < table.length; i++) {
            if (table[index] != null
                    && (table[index].key == key || table[index].key.equals(key))) {
                return table[index].value;
            }
        }
        return null;
    }

    // 节点类
    static class Node<K, V> {
        final K key;
        V value;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

3.2 合并散列 (Coalesced Hashing)

合并散列是一种混合哈希冲突解决方法,结合了开放地址和单独链接两种技术。当发生哈希冲突时,新的元素仍然以开放地址的形式向后移动,但会与原始元素形成链式结构。

合并散列

这种算法适用于固定分配内存的哈希桶,因为它通过存放元素时识别哈希桶上的最大空槽位来解决冲突。当哈希桶的空间不足以存储所有发生冲突的元素时,新元素会被放置在空槽位上,而不会生成新的链表节点,从而有效地利用了有限的内存空间。具体实现如下:

  1. 节点类:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    
    static class Node<K, V> {
        final K key;
        V value;
        // 用于串联碰撞节点
        int indexOfNext;
    
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            // 默认情况下,需要指向非法位置
            indexOfNext = -1;
        }
    }
  2. 插入方法:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    
    public void put(K key, V value) {
        int index = key.hashCode() & (table.length - 1);
        if (table[index] == null) {
            // 索引处就是空位,直接放入即可
            table[index] = new Node<K, V>(key, value);
            return;
        }
        // 碰撞后,从后往前寻找空位
        int cursor = table.length - 1;
        while (table[cursor] != null
                && table[cursor].key != key && !table[cursor].key.equals(key)) {
            --cursor;
        }
        table[cursor] = new Node<K, V>(key, value);
    
        // 将新节点加入碰撞节点链
        while (table[index].indexOfNext != -1) {
            index = table[index].indexOfNext;
        }
        table[index].indexOfNext = cursor;
    
    }
  3. 查询方法:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    
    public V get(K key) {
        int index = key.hashCode() & (table.length - 1);
        // 索引位置为空
        if (table[index] == null) {
            return null;
        }
        // 根据 idxOfNext 指针迭代查询
        while (table[index].key != key && !table[index].key.equals(key)) {
            // 顺着链表找到头依旧没找到
            if (table[index].idxOfNext == -1) {
                return null;
            }
            index = table[index].idxOfNext;
        }
        return table[index].value;
    }

3.3 罗宾汉哈希 (Robin-Hood Hashing)

罗宾汉哈希是开放地址法的变种,可以避免常规开放地址法中可能出现的在连续区域里频繁后移的操作。

新插入元素的初始 offset(偏移量,即“元素的实际索引”到“哈希算法计算得到的原始索引”之间的差值)为 0,当发生哈希碰撞时,该算法会比较相互冲突的这两个元素的 offset,偏移量较大的元素留下,而较小的元素则继续向后移动。

罗宾汉哈希

具体实现如下:

  • 成员变量与节点类:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    
    public class HashMapByRobinHoodHashing<K, V>{
    
        private int size;
        private final double loadFactor = 0.5;
        // Bucket 数组
        @SuppressWarnings({"unchecked"})
        private Node<K, V>[] table = (Node<K, V>[]) new Node[8];
    
        // 节点类
        static class Node<K, V> {
            final K key;
            V value;
            int offset ;
    
            public Node(K key, V value) {
                this.key = key;
                this.value = value;
                offset  = 0;
            }
        }
    }
  • 插入方法:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    
    public void put(K key, V value) {
        Node<K, V> n = new Node<K, V>(key, value);
        int index = key.hashCode() & (table.length - 1);
        // 碰撞检测
        while (table[index] != null) {
            if (n.offset > table[index].offset) {
                // 需要移动的节点 n 的偏移量更大,则将 n 留下
                Node<K, V> garbage = table[index];
                table[index] = n;
                n = garbage; // 被比下来的节点接着向后移动
                n.offset++;
                // index 后移,接着向后对比
                index = (++index == table.length) ? 0 : index;
            } else if (n.offset == table[index].offset) {
                // 找到了 key 值相同的,覆盖即可
                if (table[index].key.equals(key)) {
                    table[index].value = value;
                    return;
                } else {
                    // 否则继续移动 n
                    index = (++index == table.length) ? 0 : index;
                    n.offset++;
                }
            } else {
                // 如果 n 节点的偏移量更小,继续移动 n
                index = (++index == table.length) ? 0 : index;
                n.offset++;
            }
        }
        // 如果未碰撞,或找到了空位
        table[index] = n;
        // 超过负载因子,则扩容
        if (++size >= loadFactor * table.length) {
            rehash(table.length * 2);
        }
    }
  • rehash 方法

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    
    @SuppressWarnings("unchecked")
    private void rehash(int newCap) {
        Node<K, V>[] oldTable = table;
        table = (Node<K, V>[]) Array.newInstance(Node.class, newCap);
        size = 0;
        for (Node<K, V> e : oldTable) {
            // skip nulls
            if (e != null) {
                this.put(e.key, e.value);
            }
        }
    }
  • 查询方法:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    
    public V get(K key) {
        int offset = 0;
        int index = key.hashCode() & (table.length - 1);
        while (table[index] != null) {
            if (offset > table[index].offset) {
                return null;
            } else if (offset == table[index].offset) {
                // 找到了 key 值相同的,覆盖即可
                if (table[index].key.equals(key)) {
                    return table[index].value;
                } else {
                    // 否则继续移动 n
                    index = (++index == table.length) ? 0 : index;
                    offset++;
                }
            } else {
                index = (++index == table.length) ? 0 : index;
                offset++;
            }
        }
        return null;
    }