[Java数据结构与算法] 哈希表（Hash Table）

木井巳

发布于 2025-12-16 09:51:43

970

一、概念与原理

在顺序结构和平衡树中，元素关键码和其存储位置没有对应关系。

这导致查找元素时，需要进行多次关键码之间的比较，搜索的效率取决于搜索过程中的比较次数。

有没有一种方法，能够避免对关键码进行比较，以此提高效率呢？

我们期望：不经过任何比较，直接从表中获取到要搜索的元素。

哈希表（散列表）是一种通过哈希函数（散列函数）进行元素的增删查改操作构造出来的数据结构。

当向哈希表中插入新元素时，会根据该元素的关键码，通过哈希函数计算出该元素的存储位置并存放
当要查找某个元素时，根据关键码通过哈希函数计算出存储位置并把其中所存元素的关键码与要查找元素的关键码进行核对，若相同则查找成功

这种方法称为哈希（散列）方法。

例如，数据｛12，5，3，8，0，6｝

哈希函数设置为：Hash(key) = key % capacity，capacity是存储元素的底层的总空间大小（如数组）

capacity = 10

Hash(12) = 12 % 10 = 2，即元素12要放到下标为2的位置

其余元素也是一样：

Hash(5) = 5 % 10 = 5，Hash(3) = 3 % 10 = 3，Hash(8) = 8 % 10 = 8，Hash(0) = 0 % 10 = 0，Hash(6) = 6 % 10 = 6。

使用哈希方法进行搜索不用多次进行关键码的比较，直接取得存储位置，因此效率较快。

在我们使用 HashMap 时，新建的哈希表的默认长度是 1 * 2⁴ = 16。

但是，当两个元素通过哈希函数计算得到的结果是相同的，那该怎么办呢？

二、哈希冲突

不同的关键字通过相同的哈希函数得到相同的哈希地址，此现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

避免哈希冲突

由于哈希表底层的空间大小往往是小于所要存储的数据的容量大小的，因此，哈希冲突的发生是必然的。我们要做的是降低冲突率。

1. 哈希函数设计原则

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

常见哈希函数：

直接定制法
除留余数法
平方取中法
折叠法
随机数法
数学分析法

一般来说，我们不需要上手设计哈希函数，使用时直接用Java内置的原生哈希函数即可。

2. 调节负载因子（重点）

散列表的荷载因子定义：α = 填入散列表的元素个数 / 散列表的长度

解决哈希冲突

1. 闭散列（开放地址法）

当发生哈希冲突时，若哈希表未被装满，说明表中还有空位，此时就可以把元素存放空位中去。

寻找空位的方式有两种：

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。（缺点：会把冲突的数据聚集在一起）
二次探测：找下一个空位置的方法为： Hᵢ = ( H₀ + i² ) % m, 或者：Hᵢ = ( H₀ - i² ) % m。其中：i = 1,2,3…，H₀是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置， m是表的大小，i是冲突的次数。

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。

在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

2. 开散列 / 哈希桶（链地址法）（重点）

首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

开散列可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

哈希桶的实现

public class MyHashBuck<K,V> {
    public static class Node<K,V> {
        public K key;
        public V val;
        public Node<K,V> next;

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

    public Node<K,V>[] arr;
    public int usedSize;
    public static final double DEFAULT_LOAD_FACTOR = 0.75f;

    public void push (K key, V val) {
        // 先查找链表中是否有该key，若有，就更新val
        // 引用类型先获取哈希码再哈希求位置
        int hashCode = key.hashCode();
        int index = hashCode % arr.length;
        Node<K,V> cur = arr[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }

        // 当前链表中没有该key，插入结点(头插法)
        Node<K,V> node = new Node<>(key,val);

        node.next = arr[index];
        arr[index] = node;

        usedSize++;
    }

    public V getVal (K key) {
        int hashCode = key.hashCode();
        int index = hashCode % arr.length;
        Node<K,V> cur = arr[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}