跳至主要內容

 

labuladong原创约 2669 字大约 9 分钟

前文 哈希表核心原理 中我介绍了哈希表的核心原理和几个关键概念,拉链法原理和实现 中介绍了拉链法的实现,线性探查法的两个难点 介绍了线性探查法实现哈希表的难点所在,并给出了两种方法解决删除元素时的空洞问题,本文会同时给出这两种方法的参考代码实现。

本文会先结合可视化面板给出简化的实现,方便大家理解增删查改的过程,最后给完整实现。

简化实现中,具体简化的地方如下:

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

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

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

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

简化版代码

搬移数据的线性探查法

这种方法在 remove 操作时,会将删除的元素后面的元素重新插入哈希表,以此保持元素的连续性。

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

java 🟢
// 用线性探查法解决哈希冲突的简化实现(rehash 版)
public class ExampleLinearProbingHashMap1 {

    private static class Node {
        int key;
        int val;

        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    // 哈希表的底层数组,每个索引存储一个键值对
    private final Node[] table;

    public ExampleLinearProbingHashMap1(int cap) {
        table = new Node[cap];
    }

    // 增/改
    public void put(int key, int value) {
        int index = findKeyIndex(key);
        table[index] = new Node(key, value);
    }

    // 查,找不到就返回 -1
    public int get(int key) {
        int index = findKeyIndex(key);
        return table[index] == null ? -1 : table[index].val;
    }

    // 删
    public void remove(int key) {
        int index = findKeyIndex(key);
        if (table[index] == null) {
            return;
        }
        table[index] = null;
        // 保持元素连续性,搬移数据(这个过程称为 rehash)
        index = (index + 1) % table.length;
        while (table[index] != null) {
            Node entry = table[index];
            table[index] = null;
            // 这个操作是关键,利用 put 方法,将键值对重新插入
            // 这样就能把它们移动到正确的 table 索引位置
            put(entry.key, entry.val);
            index = (index + 1) % table.length;
        }
    }


    // 线性探测法查找 key 在 table 中的索引
    // 如果找不到,返回的就是下一个为 null 的索引,可用于插入
    private int findKeyIndex(int key) {
        int index = hash(key);

        while (table[index] != null) {
            if (table[index].key == key) {
                return index;
            }
            // 注意环形数组特性
            index = (index + 1) % table.length;
        }

        return index;
    }

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

    public static void main(String[] args) {
        ExampleLinearProbingHashMap1 map = new ExampleLinearProbingHashMap1(10);
        map.put(1, 1);
        map.put(2, 2);
        map.put(10, 10);
        map.put(20, 20);
        map.put(30, 30);
        map.put(3, 3);
        System.out.println(map.get(1)); // 1
        System.out.println(map.get(2)); // 2
        System.out.println(map.get(20)); // 20

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

        map.remove(20);
        System.out.println(map.get(20)); // -1
        System.out.println(map.get(30)); // 30
    }
}

特殊占位符的线性探查法

这种方法通过一个 DELETED 特殊值作为占位符,标记被删除的元素。

这个方法与上面的方法最大的区别在于 findKeyIndex 方法的实现,同时需要对 DELETED 特殊处理。直接看代码吧,后面会通过可视化面板展示增删查改的过程:

java 🟢
// 用线性探查法解决哈希冲突的简化实现(特殊占位符版)
public class ExampleLinearProbingHashMap2 {

    private static class KVNode {
        int key;
        int val;

        public KVNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    // 用于标记被删元素的占位符
    // 里面的值可以随意存储,因为只会使用 == 判断指针相等,不用比较里面的值
    private final KVNode DELETED = new KVNode(-2, -2);

    // 真正存储键值对的数组
    private final KVNode[] table;


    public ExampleLinearProbingHashMap2(int initCapacity) {
        table = new KVNode[initCapacity];
    }

    // 增/改
    public void put(int key, int val) {
        int index = findKeyIndex(key);
        if (index != -1) {
            // key 已存在,修改对应的 val
            KVNode node = table[index];
            if (node != null) {
                node.val = val;
                return;
            }
        }

        // key 不存在
        KVNode node = new KVNode(key, val);
        // 在 table 中找一个空位或者占位符进行插入
        index = hash(key);
        while (table[index] != null && table[index] != DELETED) {
            index = (index + 1) % table.length;
        }
        table[index] = node;
    }

    // 删
    public void remove(int key) {
        int index = findKeyIndex(key);
        if (index == -1) {
            // key 不存在,不需要 remove
            return;
        }
        // 直接用占位符表示删除
        table[index] = DELETED;
    }

    // 查,返回 key 对应的 val,如果 key 不存在,则返回 -1
    public int get(int key) {
        int index = findKeyIndex(key);
        if (index == -1) {
            return -1;
        }

        return table[index].val;
    }

    // 线性探测法查找 key 在 table 中的索引
    // 如果找不到,返回 -1
    private int findKeyIndex(int key) {
        // 因为删除元素时只是标记为 DELETED,并不是真的删除
        // 所以 table 可能会被填满,导致死循环
        // step 用来记录查找的步数,防止死循环
        int step = 0;
        // 注意环形数组特性
        for (int i = hash(key); table[i] != null; i = (i + 1) % table.length) {
            if (table[i] == DELETED) {
                // 遇到占位符直接跳过
                continue;
            }
            if (table[i].key == key) {
                return i;
            }
            step++;
            // 防止死循环
            if (step == table.length) {
                return -1;
            }
        }

        return -1;
    }

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

    public static void main(String[] args) {
        ExampleLinearProbingHashMap2 map = new ExampleLinearProbingHashMap2(10);
        map.put(1, 1);
        map.put(2, 2);
        map.put(10, 10);
        map.put(20, 20);
        map.put(30, 30);
        map.put(3, 3);
        System.out.println(map.get(1)); // 1
        System.out.println(map.get(2)); // 2
        System.out.println(map.get(20)); // 20

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

        map.remove(20);
        System.out.println(map.get(20)); // -1
        System.out.println(map.get(30)); // 30
    }
}

完整版代码

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

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

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

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

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

下面我会分别给出 rehash 版本和特殊值标记版本的实现,具体细节可以参考代码注释。

rehash 版本

import java.util.LinkedList;
import java.util.List;

// rehash 方式实现的线性探查哈希表
public class MyLinearProbingHashMap1<K, V> {

    private static class KVNode<K, V> {
        K key;
        V val;

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

    // 真正存储键值对的数组
    private KVNode<K, V>[] table;
    // HashMap 中的键值对个数
    private int size;
    // 默认的初始化容量
    private static final int INIT_CAP = 4;

    public MyLinearProbingHashMap1() {
        this(INIT_CAP);
    }

    public MyLinearProbingHashMap1(int initCapacity) {
        size = 0;
        table = (KVNode<K, V>[]) new KVNode[initCapacity];
    }

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

    public void put(K key, V val) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        // 我们把负载因子默认设为 0.75,超过则扩容
        if (size >= table.length * 0.75) {
            resize(table.length * 2);
        }

        int index = getKeyIndex(key);
        // key 已存在,修改对应的 val
        if (table[index] != null) {
            table[index].val = val;
            return;
        }

        // key 不存在,在空位插入
        table[index] = new KVNode<>(key, val);
        size++;
    }

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

    // 删除 key 和对应的 val
    public void remove(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }

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

        int index = getKeyIndex(key);

        if (table[index] == null) {
            // key 不存在,不需要 remove
            return;
        }

        // 开始 remove
        table[index] = null;
        size--;
        // 保持元素连续性,进行 rehash
        index = (index + 1) % table.length;
        for (; table[index] != null; index = (index + 1) % table.length) {
            KVNode<K, V> entry = table[index];
            table[index] = null;
            // 这里减一,因为 put 里面又会加一
            size--;
            put(entry.key, entry.val);

        }
    }

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

    // 返回 key 对应的 val,如果 key 不存在,则返回 null
    public V get(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        int index = getKeyIndex(key);
        if (table[index] == null) {
            return null;
        }
        return table[index].val;
    }

    // 返回所有 key(顺序不固定)
    public List<K> keys() {
        LinkedList<K> keys = new LinkedList<>();
        for (KVNode<K, V> entry : table) {
            if (entry != null) {
                keys.addLast(entry.key);
            }
        }
        return keys;
    }

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

    public int size() {
        return size;
    }

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

    // 对 key 进行线性探查,返回一个索引
    // 如果 key 不存在,返回的就是下一个为 null 的索引,可用于插入
    private int getKeyIndex(K key) {
        int index;
        for (index = hash(key); table[index] != null; index = (index + 1) % table.length) {
            if (table[index].key.equals(key))
                return index;
        }
        return index;
    }

    private void resize(int newCap) {
        MyLinearProbingHashMap1<K, V> newMap = new MyLinearProbingHashMap1<>(newCap);
        for (KVNode<K, V> entry : table) {
            if (entry != null) {
                newMap.put(entry.key, entry.val);
            }
        }
        this.table = newMap.table;
    }

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

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

        map.remove(20);
        System.out.println(map.get(20)); // null
        System.out.println(map.get(30)); // 30
    }
}

特殊值标记版本

import java.util.LinkedList;
import java.util.List;

public class MyLinearProbingHashMap2<K, V> {

    private static class KVNode<K, V> {
        K key;
        V val;

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

    // 被删除的 KVNode 的占位符
    private final KVNode<K, V> DUMMY = new KVNode<>(null, null);

    // 真正存储键值对的 table 数组
    private KVNode<K, V>[] table;
    // HashMap 中的键值对个数
    private int size;
    // 默认的初始化容量
    private static final int INIT_CAP = 4;

    public MyLinearProbingHashMap2() {
        this(INIT_CAP);
    }

    public MyLinearProbingHashMap2(int cap) {
        size = 0;
        table = (KVNode<K, V>[]) new KVNode[cap];
    }

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

    // 添加 key -> val 键值对
    // 如果键 key 已存在,则将值修改为 val
    public void put(K key, V val) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }

        // 负载因子默认设为 0.75,超过则扩容
        if (size >= table.length * 0.75) {
            resize(table.length * 2);
        }

        int index = getKeyIndex(key);
        if (index != -1) {
            // key 已存在,修改对应的 val
            table[index].val = val;
            return;
        }

        // key 不存在
        KVNode<K, V> x = new KVNode<>(key, val);
        // 在 table 中找一个空位或者占位符,插入
        index = hash(key);
        while (table[index] != null && table[index] != DUMMY) {
            index = (index + 1) % table.length;
        }
        table[index] = x;
        size++;
    }

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

    // 删除 key 和对应的 val,并返回 val
    // 若 key 不存在,则返回 null
    public void remove(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }

        // 缩容
        if (size < table.length / 8) {
            resize(table.length / 2);
        }

        int index = getKeyIndex(key);
        if (index == -1) {
            // key 不存在,不需要 remove
            return;
        }

        // 开始 remove
        // 直接用占位符表示删除
        table[index] = DUMMY;
        size--;
    }

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

    // 返回 key 对应的 val
    // 如果 key 不存在,则返回 null
    public V get(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }

        int index = getKeyIndex(key);
        if (index == -1) {
            return null;
        }

        return table[index].val;
    }

    public List<K> keys() {
        LinkedList<K> keys = new LinkedList<>();
        for (KVNode<K, V> entry : table) {
            if (entry != null) {
                keys.addLast(entry.key);
            }
        }
        return keys;
    }

    public int size() {
        return size;
    }

    // 对 key 进行线性探查,返回一个索引
    // 根据 keys[i] 是否为 null 判断是否找到对应的 key
    private int getKeyIndex(K key) {
        int step = 0;
        for (int i = hash(key); table[i] != null; i = (i + 1) % table.length) {
            KVNode<K, V> entry = table[i];
            // 遇到占位符直接跳过
            if (entry == DUMMY) {
                continue;
            }
            if (entry.key.equals(key)) {
                return i;
            }
            step++;
            // 防止死循环
            if (step == table.length) {
                // 这里可以触发一次 resize,把标记为删除的占位符清理掉
                resize(table.length);
                return -1;
            }
        }
        return -1;
    }

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

    private void resize(int cap) {
        MyLinearProbingHashMap2<K, V> newMap = new MyLinearProbingHashMap2<>(cap);
        for (KVNode<K, V> entry : table) {
            if (entry != null && entry != DUMMY) {
                newMap.put(entry.key, entry.val);
            }
        }
        this.table = newMap.table;
    }

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

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

        map.remove(20);
        System.out.println(map.get(20)); // null
        System.out.println(map.get(30)); // 30
    }
}
上次编辑于: