面试中场景手撕

春秋两不沾，风月不相关

• 写一段java死锁的代码
• 实现HashMap的插入方法逻辑

写一段java死锁的代码

来源：拼多多-实习-java-二面

public class DeadLock {
    public static final String LOCK_1 = "lock1";
    public static final String LOCK_2 = "lock2";

    public static void main(String[] args) {
        Thread threadA = new Thread(() -> {
            try {
                while (true) {
                    synchronized (DeadLock.LOCK_1) {
                        System.out.println(Thread.currentThread().getName() + " 锁住 lock1");
                        Thread.sleep(1000);
                        synchronized (DeadLock.LOCK_2) {
                            System.out.println(Thread.currentThread().getName() + " 锁住 lock2");
                        }
                    }
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        });

        Thread threadB = new Thread(() -> {
            try {
                while (true) {
                    synchronized (DeadLock.LOCK_2) {
                        System.out.println(Thread.currentThread().getName() + " 锁住 lock2");
                        Thread.sleep(1000);
                        synchronized (DeadLock.LOCK_1) {
                            System.out.println(Thread.currentThread().getName() + " 锁住 lock1");
                        }
                    }
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        });

        threadA.start();
        threadB.start();
    }
}

---

实现HashMap的插入方法逻辑

来源：拼多多-实习-java-二面

jdk1.7

public class MyHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private Entry<K, V>[] table;

    public MyHashMap() {
        table = new Entry[DEFAULT_CAPACITY];
    }

    // Entry 类，用于存储键值对
    static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next;

        Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    // 插入方法
    public void put(K key, V value) {
        if (key == null) {
            // 处理 key 为 null 的情况
            putForNullKey(value);
            return;
        }

        // 计算 key 的哈希值
        int hash = hash(key);
        // 根据哈希值计算数组下标
        int index = indexFor(hash, table.length);

        // 遍历链表，检查是否已经存在相同的 key
        for (Entry<K, V> e = table[index]; e != null; e = e.next) {
            if (e.key.equals(key)) {
                // 如果 key 已经存在，更新 value
                e.value = value;
                return;
            }
        }

        // 如果 key 不存在，插入新的 Entry
        addEntry(hash, key, value, index);
    }

    // 处理 key 为 null 的情况
    private void putForNullKey(V value) {
        // 通常 HashMap 允许一个 null key，存储在数组的第一个位置
        for (Entry<K, V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                e.value = value;
                return;
            }
        }
        addEntry(0, null, value, 0);
    }

    // 计算哈希值
    private int hash(K key) {
        return key.hashCode();
    }

    // 根据哈希值和数组长度计算下标
    private int indexFor(int hash, int length) {
        return hash % length;
    }

    // 添加新的 Entry
    private void addEntry(int hash, K key, V value, int index) {
        Entry<K, V> e = table[index];
        table[index] = new Entry<>(key, value, e);
    }
}

jdk1.8

public class MyHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private static final int TREEIFY_THRESHOLD = 8; // 链表转红黑树的阈值
    private Node<K, V>[] table;
    private int size;

    public MyHashMap() {
        table = new Node[DEFAULT_CAPACITY];
    }

    // 节点类，用于存储键值对
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;

        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    // 插入方法
    public V put(K key, V value) {
        return putVal(hash(key), key, value);
    }

    // 核心插入逻辑
    private V putVal(int hash, K key, V value) {
        Node<K, V>[] tab;
        Node<K, V> p;
        int n, i;

        // 如果 table 为空，初始化 table
        if ((tab = table) == null || (n = tab.length) == 0) {
            n = (tab = resize()).length;
        }

        // 计算数组下标，如果该位置为空，直接插入新节点
        if ((p = tab[i = (n - 1) & hash]) == null) {
            tab[i] = newNode(hash, key, value, null);
        } else {
            Node<K, V> e;
            K k;

            // 如果 key 已经存在，更新 value
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
                e = p;
            }
            // 如果节点是红黑树节点，调用红黑树的插入方法
            else if (p instanceof TreeNode) {
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            }
            // 否则遍历链表
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        // 插入新节点
                        p.next = newNode(hash, key, value, null);
                        // 如果链表长度超过阈值，转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) {
                            treeifyBin(tab, hash);
                        }
                        break;
                    }
                    // 如果 key 已经存在，更新 value
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        break;
                    }
                    p = e;
                }
            }

            // 如果 key 已经存在，返回旧值并更新 value
            if (e != null) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

        // 如果 size 超过阈值，扩容
        if (++size > DEFAULT_CAPACITY * DEFAULT_LOAD_FACTOR) {
            resize();
        }
        return null;
    }

    // 计算哈希值
    private int hash(K key) {
        if (key == null) {
            return 0;
        }
        int h = key.hashCode();
        return h ^ (h >>> 16); // 扰动函数，减少哈希冲突
    }

    // 扩容方法
    private Node<K, V>[] resize() {
        // 实现扩容逻辑（略）
        return table;
    }

    // 链表转红黑树
    private void treeifyBin(Node<K, V>[] tab, int hash) {
        // 实现链表转红黑树逻辑（略）
    }

    // 创建新节点
    private Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
        return new Node<>(hash, key, value, next);
    }
}

-----------------未完待续--------------------