跳至主要內容

 

labuladong原创约 1944 字大约 6 分钟

前文 哈希表核心原理 中我介绍了哈希表的核心原理和几个关键概念,其中提到了解决哈希冲突的方法主要有两种,分别是拉链法和开放寻址法(也常叫做线性探查法):

本文就来具体介绍一下拉链法的实现原理和代码。

首先,我会结合 可视化面板 用拉链法实现一个简化版的哈希表,带大家直观地理解拉链法是如何实现增删查改的 API 并解决哈希冲突的,最后再给出一个比较完善的 Java 代码实现

拉链法的简化版实现

哈希表核心原理 已经介绍过哈希函数和 key 的类型的关系,其中 hash 函数的作用是在 O(1) 的时间把 key 转化成数组的索引,而 key 可以是任意不可变的类型。

但是这里为了方便诸位理解,我先做如下简化:

1、我们实现的哈希表只支持 key 类型为 intvalue 类型为 int 的情况,如果 key 不存在,就返回 -1

2、我们实现的 hash 函数就是简单地取模,即 hash(key) = key % table.length。这样也方便模拟出哈希冲突的情况,比如当 table.length = 10 时,hash(1)hash(11) 的值都是 1。

3、底层的 table 数组的大小在创建哈希表时就固定,不考虑负载因子和动态扩缩容的问题。

这些简化能够帮助我们聚焦增删查改的核心逻辑,并且可以借助 可视化面板 辅助大家学习理解。

简化版代码

这里直接给出简化版的代码实现,你可以先看看,后面将通过可视化面板展示增删查改的过程:

java 🟢
import java.util.LinkedList;

// 用拉链法解决哈希冲突的简化实现
public class ExampleChainingHashMap {

    // 链表节点,存储 key-value 对儿
    // 注意这里必须存储同时存储 key 和 value
    // 因为要通过 key 找到对应的 value
    static class KVNode {
        int key;
        int value;

        // 为了简化,我这里直接用标准库的 LinkedList 链表
        // 所以这里就不添加 next 指针了
        // 你当然可以给 KVNode 添加 next 指针,自己实现链表操作
        public KVNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }


    // 底层 table 数组中的每个元素是一个链表
    private LinkedList<KVNode>[] table;

    public ExampleChainingHashMap(int capacity) {
        table = new LinkedList[capacity];
    }

    private int hash(int key) {
        return key % table.length;
    }

    // 查
    public int get(int key) {
        int index = hash(key);

        if (table[index] == null) {
            // 链表为空,说明 key 不存在
            return -1;
        }

        LinkedList<KVNode> list = table[index];
        // 遍历链表,尝试查找目标 key,返回对应的 value
        for (KVNode node : list) {
            if (node.key == key) {
                return node.value;
            }
        }

        // 链表中没有目标 key
        return -1;
    }

    // 增/改
    public void put(int key, int value) {
        int index = hash(key);

        if (table[index] == null) {
            // 链表为空,新建一个链表,插入 key-value
            table[index] = new LinkedList<>();
            table[index].add(new KVNode(key, value));
            return;
        }

        // 链表不为空,要遍历一遍看看 key 是否已经存在
        // 如果存在,更新 value
        // 如果不存在,插入新节点
        LinkedList<KVNode> list = table[index];
        for (KVNode node : list) {
            if (node.key == key) {
                // key 已经存在,更新 value
                node.value = value;
                return;
            }
        }

        // 链表中没有目标 key,添加新节点
        // 这里使用 addFirst 添加到链表头部或者 addLast 添加到链表尾部都可以
        // 因为 Java LinkedList 的底层实现是双链表,头尾操作都是 O(1) 的
        // https://labuladong.online/algo/data-structure-basic/linkedlist-implement/
        list.addLast(new KVNode(key, value));
    }

    // 删
    public void remove(int key) {
        LinkedList<KVNode> list = table[hash(key)];
        if (list == null) {
            return;
        }

        // 如果 key 存在,则删除
        // 这个 removeIf 方法是 Java LinkedList 的方法,可以删除满足条件的元素,时间复杂度 O(N)
        list.removeIf(node -> node.key == key);
    }
}

可视化面板展示增删查改过程

提示

我用可视化面板内置的单链表节点类 ListNode 类来存储键值对。由于 ListNode 类只有一个 val 字段,所以我把键和值组装成 key:value 这样的字符串存储在 val 字段中,方便可视化展示。

直接点击代码就可以跳转执行到对应位置。直接点击 map.put(...) 这些方法调用,就可以直观地看到每个方法调用的效果;点击上一步 < 和下一步 > 按钮可以逐步查看增删查改的具体过程。

你也可以点击「编辑」按钮修改代码,尝试不同的输入。

完整代码实现

有了上面的铺垫,我们现在来看一个比较完善的 Java 代码实现,主要新增了以下几个功能:

1、使用了泛型,可以存储任意类型的 keyvalue

2、底层的 table 数组会根据负载因子动态扩缩容。

3、使用了 哈希表基础 中提到的 hash 函数,利用 keyhashCode() 方法和 table.length 来计算哈希值。

4、实现了 keys() 方法,可以返回哈希表中所有的 key

为了方便,我直接使用 Java 标准库的 LinkedList 作为链表,这样就不用自己手动处理增删链表节点的操作了。当然如果你愿意的话,可以参照前文 单/双链表代码实现 自己编写操作 KVNode 的逻辑。

具体需要注意的细节我都写在了代码注释中,直接看代码吧:

import java.util.LinkedList;

public class MyChainingHashMap<K, V> {

    // 拉链法使用的单链表节点,存储 key-value 对
    private static class KVNode<K, V> {
        K key;
        V value;
        // 因为我们使用了内置的 LinkedList 类,所以不用 next 指针
        // 不用我们自己实现链表的逻辑

        KVNode(K key, V val) {
            this.key = key;
            this.value = val;
        }
    }

    // 哈希表的底层数组,每个数组元素是一个链表,链表中每个节点是 KVNode 存储键值对
    private LinkedList<KVNode<K, V>>[] table;

    // 哈希表中存入的键值对个数
    private int size;
    // 底层数组的初始容量
    private static final int INIT_CAP = 4;

    public MyChainingHashMap() {
        this(INIT_CAP);
    }

    public MyChainingHashMap(int initCapacity) {
        size = 0;
        // 初始化哈希表
        table = (LinkedList<KVNode<K, V>>[]) new LinkedList[initCapacity];
        for (int i = 0; i < table.length; i++) {
            table[i] = new LinkedList<>();
        }
    }

    /***** 增/改 *****/

    // 添加 key -> val 键值对
    // 如果键 key 已存在,则将值修改为 val
    public void put(K key, V val) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        LinkedList<KVNode<K, V>> list = table[hash(key)];
        // 如果 key 之前存在,则修改对应的 val
        for (KVNode<K, V> node : list) {
            if (node.key.equals(key)) {
                node.value = val;
                return;
            }
        }
        // 如果 key 之前不存在,则插入,size 增加
        list.add(new KVNode<>(key, val));
        size++;

        // 如果元素数量超过了负载因子,进行扩容
        if (size >= table.length * 0.75) {
            resize(table.length * 2);
        }
    }

    /***** 删 *****/

    // 删除 key 和对应的 val
    public void remove(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        LinkedList<KVNode<K, V>> list = table[hash(key)];
        // 如果 key 存在,则删除,size 减少
        for (KVNode<K, V> node : list) {
            if (node.key.equals(key)) {
                list.remove(node);
                size--;

                // 缩容,当负载因子小于 0.125 时,缩容
                if (size <= table.length / 8) {
                    resize(table.length / 4);
                }
                return;
            }
        }
    }

    /***** 查 *****/

    // 返回 key 对应的 val,如果 key 不存在,则返回 null
    public V get(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        LinkedList<KVNode<K, V>> list = table[hash(key)];
        for (KVNode<K, V> node : list) {
            if (node.key.equals(key)) {
                return node.value;
            }
        }
        return null;
    }

    // 返回所有 key
    public List<K> keys() {
        List<K> keys = new LinkedList<>();
        for (LinkedList<KVNode<K, V>> list : table) {
            for (KVNode<K, V> node : list) {
                keys.add(node.key);
            }
        }
        return keys;
    }

    /***** 其他工具函数 *****/

    public int size() {
        return size;
    }

    // 哈希函数,将键映射到 table 的索引
    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % table.length;
    }

    private void resize(int newCap) {
        // 构造一个更大容量的 HashMap
        MyChainingHashMap<K, V> newMap = new MyChainingHashMap<>(newCap);
        // 穷举当前 HashMap 中的所有键值对
        for (LinkedList<KVNode<K, V>> list : table) {
            for (KVNode<K, V> node : list) {
                // 将键值对转移到新的 HashMap 中
                newMap.put(node.key, node.value);
            }
        }
        // 将当前 HashMap 的底层 table 换掉
        this.table = newMap.table;
    }

    public static void main(String[] args) {
        MyChainingHashMap<Integer, Integer> map = new MyChainingHashMap<>();
        map.put(1, 1);
        map.put(2, 2);
        map.put(3, 3);
        System.out.println(map.get(1)); // 1
        System.out.println(map.get(2)); // 2

        map.put(1, 100);
        System.out.println(map.get(1)); // 100

        map.remove(2);
        System.out.println(map.get(2)); // null

        System.out.println(map.keys()); // [1, 3](顺序可能不同)
    }
}
上次编辑于: