用数组加强哈希表（ArrayHashMap）

1. 开场白

长话短说：

• 上方绿色方框代表了 map (key -> 索引)
• 中间的蓝色方框代表了 arr （存储了(索引， Node<K, V>)）
• 箭头展示了 map 中的 key 如何定位到 arr 里的元素。

这样一来：

• 可以先从 map 根据 key ,找到对应的索引，根据该索引找到 arr 中的值。
• 删除时，能够快速找到并进行交换，时间复杂度能够达到 O(1)

2. 代码示例

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

public class ArrayHashMap<K, V> {
    private static class Node<K, V> {
        K key;
        V val;
        
        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    } 
    // 申请一个哈希表（key, 索引）
    private final HashMap<K, Integer> map = new HashMap<>();
    // 申请一个数组（索引，Node<K, V>）
    private final ArrayList<Node<K, V>> array = new ArrayList<>();
    // 生成随机数
    private final Random r = new Random;
    // get 方法
    public V get(K key) {
        if (!map.containsKey(key)) {
            return null;
        }
        int index = map.get(key);
        return array.get(index).val;
    }
    // put 方法
    public void put(K key, V val) {
        // 已存在，进行修改
        if (map.containsKey(key)) {
            int index = map.get(key);
            array.get(index).val = val;
            return;
        }
        // 不存在，new 一个 Node<K, V>
        // 先从 array 中 new 一个新的节点
        array.get(new Node<>(key, val));
        map.put(key, array.size() - 1); // size 代表了数组中的有效元素个数
    }
    // remove 方法
    public void remove(K key) {
        // 校验
        if (!map.containsKey(key)) {
            return;
        }
        // 获得该 key 在数组中的 Node<K, V>
        int index = map.get(key);
        Node<K, V> node = array.get(index);
        // 最后一个元素 e 和 index 个元素 node 进行交换
        Node<K, V> e = array.get(array.size() - 1);
        array.set(index, e);
        array.set(array.size() - 1, node);
        // 当前 e 节点虽然走到了 index 位置，但是 map 的索引，还是指向了 node 这个节点，所以得修改指向
        // 修改 map 中 e.key 的值
        map.put(e.key, index);
        // 在数组中删除最后一个元素
        array.remove(array.size() - 1);
        // map 中的索引还没有删掉，防止内存泄漏，将 node.key 指向进行删除
        // 在 map 中删除 node.key
        map.remove(node.key);
    }
    // 随机弹出一个键
    public K randomKey() {
        int n = arr.size();
        int randomIndex = r.nextInt(n);
        return arr.get(randomIndex).key;
    }

    public boolean containsKey(K key) {
        return map.containsKey(key);
    }

    public int size() {
        return map.size();
    }

    public static void main(String[] args) {
        MyArrayHashMap<Integer, Integer> map = new MyArrayHashMap<>();
        map.put(1, 1);
        map.put(2, 2);
        map.put(3, 3);
        map.put(4, 4);
        map.put(5, 5);

        System.out.println(map.get(1)); // 1
        System.out.println(map.randomKey());

        map.remove(4);
        System.out.println(map.randomKey());
        System.out.println(map.randomKey());
    }
}