图灵二面：手撕HashMap

面试官：既然你刚刚提到HashMap底层原理，想必你一定了解HashMap的结构。那你就手写一份自己的HashMap吧。
我：？？？
先来看看我当时写的依托答辩：

/**
 * @author Aromatic
 * @date 2025/6/18 下午3:21
 * @description:
 */
public class MyHashMap {
    private int size;
    private List<List<Integer>>[] table;

    public void MyHashMap(){
        this.size = 16;
        table = new List[size];
    }

    public void MyHashMap(int size){
        this.size = size;
        table = new List[size];
    }

    private int hash(Integer key){
        return key * size;
    }

    public void add(List<Integer> entry){
        Integer key = entry.get(0);
        int hashCode = hash(key);
        int index = hashCode % size;
        table[index].add(entry);
    }

    public void delete(List<Integer> entry){
        Integer key = entry.get(0);
        int hashCode = hash(key);
        int index = hashCode % size;
        table[index].remove(entry);
    }

    public void  update(List<Integer> entry){
        Integer key = entry.get(0);
        int hashCode = hash(key);
        int index = hashCode % size;
        for (List<Integer> pair : table[index]) {
            if(pair.get(0) == entry.get(0)){
                pair.set(1,entry.get(1));
            }
        }
    }

    public List<Integer> get(Integer key){
        int hashCode = hash(key);
        int index = hashCode % size;
        for (List<Integer> pair : table[index]) {
            if(pair.get(0) == key){
                return pair;
            }
        }
        return null;
    }
}

面试的时候吹的再天花乱坠，只要上手写代码就原形毕露了🤣

正解

1.定义MyMap接口，约定常用方法

/**
 * @author Aromatic
 * @date 2025/9/29 上午10:23
 * @description:
 */
public interface MyMap<K,V> {
    void put(K key, V value);
    V get(K key);
    void remove(K key);
    int size();
    boolean isEmpty();
}

2.定义好MyRealHashMap的必要属性

/**
 * @author Aromatic
 * @date 2025/9/29 上午10:24
 * @description:
 */
public class MyRealHashMap<K,V> implements MyMap<K,V> {
    static class Node<K,V>{
        K key;
        V value;
        Node<K,V> next;
        public Node(K key, V value){
            this.key = key;
            this.value = value;
        }
    }

    private Node<K,V>[] table;
    private int size;
}

无非就两类：

• 定义Node数据结构（JDK 1.7为Entry）：一个含有键值数据的单向链表
• 定义HashMap的必要属性：table（Node数组）和size

3.实现put方法

@Override
    public void put(K key, V value) {
        int hash = key.hashCode();
        int index = hash % table.length;
        Node<K,V> newNode = new Node<>(key, value);
        if(table[index] == null){
            table[index] = newNode;
        } else {
            Node<K,V> current = table[index];
            while(current.next != null){
                if(current.key.equals(key)){
                    current.value = value;
                    return;
                }
                current = current.next;
            }
            if(current.key.equals(key)){
                current.value = value;
            } else {
                current.next = newNode;
                size++;
            }
        }
    }

put方法逻辑如下：

• 通过key计算hashCode，进一步计算index
• 创建新节点，储存Key和Value
• 根据index顺延寻找，判断链表上是否有与之相等的key：
  • 如果有，则新值替换旧值
  • 如果没有，则采用尾插法插入新节点，并将size递增

4.实现get方法

@Override
    public V get(K key) {
        int hash = key.hashCode();
        int index = hash % table.length;
        Node<K,V> current = table[index];
        while(current != null){
            if(current.key.equals(key)){
                return current.value;
            }
            current = current.next;
        }
        return null;
    }

总体来说与put方法的查找key逻辑差不多：

• 根据key计算index
• 在table[index]的链表上顺延查找：
  • 找到，返回Value
  • 没找到，返回null

5.实现remove方法

@Override
    public void remove(K key) {
        int hash = key.hashCode();
        int index = hash % table.length;
        Node<K,V> current = table[index];
        Node<K,V> prev = null;
        while(current != null){
            if(current.key.equals(key)){
                if(prev == null){
                    table[index] = current.next;
                } else {
                    prev.next = current.next;
                    size--;
                }
                return;
            }
            prev = current;
            current = current.next;
        }
    }

remove方法就比较特殊，因为如果要删除的节点在链表中间的话，就需要将被删除节点的前节点指向它的后节点，因此我们采用双指针法 ：

• 根据key计算index
• 双指针遍历，如果cur指针找到，则删除cur节点并连接perv和cur.next

其它方法

@Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }