数据结构与算法 / 系统课时

链地址法

链地址法

链地址法把发生哈希冲突的键保存在同一个桶的链表中。本课将从桶结构、装载因子和复杂度出发,实现一个支持插入、更新、查找与删除的整数键哈希表,并通过可重复的冲突数据验证链表如何化解冲突。

学习目标

  • 理解桶数组与链表协同解决冲突的过程。
  • 能够实现链地址哈希表的核心操作。
  • 能够用装载因子分析平均操作成本和扩容时机。

问题定义与核心思路

哈希函数会把大量可能的键映射到有限个桶,因此不同键得到同一桶下标是正常现象。链地址法让每个桶保存一条链表:桶下标负责快速定位候选集合,链表负责区分落入同一桶的键。

查找键 key 时,先计算桶下标,再沿链表比较键。插入时若链表中已有相同键,则更新值;否则创建新节点。删除时区分桶头与其他位置。后一分支也适用于尾节点,此时前驱的 next 变为 null。

链地址法中多个键落入同一桶并形成链表

装载因子与复杂度

设元素数量为 nn,桶数量为 mm,装载因子为 α=n/m\alpha=n/m。链地址法允许 α\alpha 大于 1,因为一个桶可以容纳多个节点。把所有桶(包括空桶)的链长取算术平均,恰好是 α\alpha。但查询会访问哪个桶取决于键的分布。下表的期望成本假设哈希分布足够均匀且单次键比较为常数。

操作 平均时间复杂度 最坏时间复杂度
查找 O(1+α)O(1+\alpha) O(n)O(n)
插入或更新 O(1+α)O(1+\alpha) O(n)O(n)
删除 O(1+α)O(1+\alpha) O(n)O(n)

空间复杂度为 O(m+n)O(m+n)。当装载因子持续升高时,链表变长,常数级定位的优势会减弱。扩容可以降低平均装载率,但集中冲突还要检查散列质量。本例仅取模,若大量键相差容量的倍数,即使装载率很低也可能集中到一条链。

完整实现与验证

下面的 Java 17 示例使用固定容量和非空值。get 与 remove 用 null 表示未命中,因此 put 先拒绝空值,containsKey 才能通过 get 判定。键 1、6、11 在容量为 5 时都会进入桶 1。

java
import java.util.Arrays;
import java.util.Locale;
import java.util.Objects;

public class ChainHashTableDemo {

    private static final class Node {
        private final int key;
        private String value;
        private Node next;

        private Node(int key, String value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private static final class ChainHashTable {
        private final Node[] buckets;
        private int size;

        private ChainHashTable(int capacity) {
            if (capacity <= 0) {
                throw new IllegalArgumentException("capacity must be positive");
            }
            this.buckets = new Node[capacity];
        }

        public void put(int key, String value) {
            Objects.requireNonNull(value, "value must be non-null");
            int index = bucketIndex(key);
            Node current = buckets[index];

            while (current != null) {
                if (current.key == key) {
                    current.value = value;
                    return;
                }
                current = current.next;
            }

            // 新节点放到链表头部,插入本身只需要常数次指针修改。
            buckets[index] = new Node(key, value, buckets[index]);
            size++;
        }

        public String get(int key) {
            Node current = buckets[bucketIndex(key)];
            while (current != null) {
                if (current.key == key) {
                    return current.value;
                }
                current = current.next;
            }
            return null;
        }

        public String remove(int key) {
            int index = bucketIndex(key);
            Node current = buckets[index];
            Node previous = null;

            while (current != null) {
                if (current.key == key) {
                    if (previous == null) {
                        buckets[index] = current.next;
                    } else {
                        previous.next = current.next;
                    }
                    size--;
                    return current.value;
                }
                previous = current;
                current = current.next;
            }
            return null;
        }

        public boolean containsKey(int key) {
            return get(key) != null;
        }

        public int size() {
            return size;
        }

        public double loadFactor() {
            return (double) size / buckets.length;
        }

        public int[] bucketSizes() {
            int[] result = new int[buckets.length];
            for (int i = 0; i < buckets.length; i++) {
                Node current = buckets[i];
                while (current != null) {
                    result[i]++;
                    current = current.next;
                }
            }
            return result;
        }

        private int bucketIndex(int key) {
            return Math.floorMod(key, buckets.length);
        }
    }

    public static void main(String[] args) {
        ChainHashTable table = new ChainHashTable(5);

        table.put(1, "A");
        table.put(6, "B");
        table.put(11, "C");
        table.put(2, "D");
        table.put(6, "B2");

        System.out.println("bucket sizes = " + Arrays.toString(table.bucketSizes()));
        System.out.println("get(11) = " + table.get(11));
        System.out.println("get(6) = " + table.get(6));
        System.out.println("remove(1) = " + table.remove(1));
        System.out.println("containsKey(1) = " + table.containsKey(1));
        System.out.println("size = " + table.size());
        System.out.printf(Locale.ROOT, "load factor = %.2f%n", table.loadFactor());
    }
}

将代码保存为 ChainHashTableDemo.java,然后编译并运行:

bash
javac -encoding UTF-8 ChainHashTableDemo.java
java ChainHashTableDemo

预期输出

text
bucket sizes = [0, 3, 1, 0, 0]
get(11) = C
get(6) = B2
remove(1) = A
containsKey(1) = false
size = 3
load factor = 0.60

常见错误与实践建议

删除桶头节点时,必须修改 buckets[index];只修改局部变量 current 不会改变桶中的链表。更新已有键时不要增加 size,否则装载因子会被重复键污染。

哈希下标不要直接使用 key % capacity,因为负键可能产生负数下标。示例使用 Math.floorMod(key, buckets.length),对正容量能得到 0 到 capacity−1 的结果,包括 Integer.MIN_VALUE。

固定容量适合教学验证,但长期运行的哈希表应在装载因子超过阈值后扩容。扩容时必须重新计算所有键的桶下标,因为桶数量变化会改变哈希映射结果。

本课练习

  1. 为示例增加 clear() 方法,要求释放所有桶链表并把 size 重置为 0,验收条件是清空后所有桶长度为 0。
  2. 增加自动扩容:当装载因子大于 0.75 时把桶数量扩大为原来的两倍,并重新散列已有节点,验收条件是扩容前后的键值查询结果一致。

本课总结

  • 链地址法用桶数组缩小查找范围,用链表保存同桶冲突元素。
  • 平均操作成本与装载因子 α\alpha 相关,分布均匀时约为 O(1+α)O(1+\alpha)。
  • 删除、重复键更新、负键下标和扩容重散列是实现中的关键边界。

下一课预告

下一课将学习“开放寻址法”,把冲突元素直接存入桶数组,并比较线性探测、二次探测和双重哈希的探测路径。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

链地址法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通