面试题：优化Java HashMap解决哈希冲突性能的自定义策略

策略原理

减少哈希冲突概率：采用更复杂且均匀分布的哈希函数。例如，结合FNV哈希算法和MurmurHash算法的优点。FNV哈希算法的特点是快速且简单，MurmurHash算法则以分布均匀著称。通过将两者结合，对键进行多次哈希运算，然后将结果进行位运算混合，使得哈希值在哈希表中的分布更加均匀，从而减少哈希冲突的概率。
提高查询和插入效率：在发生哈希冲突时，使用链表和红黑树结合的方式。当链表长度较短时（例如小于8），使用链表存储冲突元素，因为链表插入操作时间复杂度为O(1)，在短链表情况下查询效率也尚可。当链表长度达到一定阈值（如8）时，将链表转换为红黑树，红黑树的查询、插入和删除操作平均时间复杂度为O(log n)，能有效提高在长冲突链情况下的查询和插入效率。
兼顾内存使用：避免过度使用复杂数据结构造成内存浪费。对于短链表，链表节点结构相对简单，内存占用少。在转换为红黑树时，虽然红黑树节点结构稍复杂，但在长冲突链情况下，其高效的查询和插入操作减少了整体的内存使用（因为不需要不断扩展链表长度）。同时，在哈希表扩容时，合理控制扩容因子，避免频繁扩容造成内存碎片和性能损耗。

数据结构变化

哈希表主体：依然采用数组作为哈希表的基本结构，数组元素类型为自定义节点类型。
自定义节点类型：设计一个Node类，包含键值对（key - value）、指向下一个节点的引用（next）以及用于红黑树的颜色和左右子节点引用（在链表形态下左右子节点引用为空）。例如：

class Node<K, V> {
    K key;
    V value;
    Node<K, V> next;
    boolean color; // 红黑树颜色，true为红色，false为黑色
    Node<K, V> left;
    Node<K, V> right;
    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

红黑树辅助方法：为了实现红黑树的操作，需要一些辅助方法，如左旋、右旋、插入修复、删除修复等方法，这些方法用于维护红黑树的性质。

相关方法实现思路

哈希函数：

private int hash(Object key) {
    int h1 = 2166136261; // FNV哈希算法初始值
    int h2 = 0;
    byte[] data = key.toString().getBytes();
    for (byte b : data) {
        h1 = (h1 ^ b) * 16777619;
    }
    h2 = MurmurHash3.hash32(data, 0, data.length, 0);
    return h1 ^ h2;
}

插入方法：
- 计算键的哈希值，确定数组索引位置。
- 如果该位置为空，直接插入新节点。
- 如果该位置不为空，判断当前节点是链表还是红黑树。
  - 如果是链表，遍历链表，若找到相同键则更新值，否则在链表尾部插入新节点。插入后检查链表长度，若达到阈值则转换为红黑树。
  - 如果是红黑树，按照红黑树插入算法插入新节点，然后进行插入修复操作以维护红黑树性质。

public void put(K key, V value) {
    int hash = hash(key);
    int index = hash & (table.length - 1);
    Node<K, V> node = table[index];
    if (node == null) {
        table[index] = new Node<>(key, value);
        return;
    }
    if (node.left == null) { // 链表形态
        while (node != null) {
            if (node.key.equals(key)) {
                node.value = value;
                return;
            }
            if (node.next == null) {
                break;
            }
            node = node.next;
        }
        node.next = new Node<>(key, value);
        if (isListTooLong(node)) {
            convertListToTree(index);
        }
    } else { // 红黑树形态
        insertIntoTree(index, key, value);
    }
}

查询方法：
- 计算键的哈希值，确定数组索引位置。
- 如果该位置为空，返回null。
- 如果该位置不为空，判断当前节点是链表还是红黑树。
  - 如果是链表，遍历链表查找键，找到则返回对应值，否则返回null。
  - 如果是红黑树，按照红黑树查找算法查找键，找到则返回对应值，否则返回null。

public V get(K key) {
    int hash = hash(key);
    int index = hash & (table.length - 1);
    Node<K, V> node = table[index];
    if (node == null) {
        return null;
    }
    if (node.left == null) { // 链表形态
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
    } else { // 红黑树形态
        return searchInTree(index, key);
    }
    return null;
}

链表转红黑树方法：
- 遍历链表，将节点依次插入红黑树（使用红黑树插入算法）。
- 对插入后的红黑树进行插入修复操作以维护红黑树性质。

private void convertListToTree(int index) {
    Node<K, V> head = table[index];
    Node<K, V> root = null;
    while (head != null) {
        root = insertIntoTree(root, head.key, head.value);
        head = head.next;
    }
    table[index] = root;
}

红黑树插入方法：
- 按照二叉搜索树插入算法找到插入位置并插入新节点。
- 将新节点颜色设为红色。
- 调用插入修复方法。

private Node<K, V> insertIntoTree(Node<K, V> root, K key, V value) {
    if (root == null) {
        return new Node<>(key, value);
    }
    int cmp = key.hashCode() - root.key.hashCode();
    if (cmp < 0) {
        root.left = insertIntoTree(root.left, key, value);
    } else if (cmp > 0) {
        root.right = insertIntoTree(root.right, key, value);
    } else {
        root.value = value;
    }
    return insertFixup(root);
}

插入修复方法：
- 处理红黑树插入后的不平衡情况，通过左旋、右旋和颜色调整操作维护红黑树性质。

private Node<K, V> insertFixup(Node<K, V> root) {
    while (root != null && root != getRoot() && root.parent.color) {
        if (root.parent == root.parent.parent.left) {
            Node<K, V> uncle = root.parent.parent.right;
            if (uncle != null && uncle.color) {
                root.parent.color = false;
                uncle.color = false;
                root.parent.parent.color = true;
                root = root.parent.parent;
            } else {
                if (root == root.parent.right) {
                    root = root.parent;
                    leftRotate(root);
                }
                root.parent.color = false;
                root.parent.parent.color = true;
                rightRotate(root.parent.parent);
            }
        } else {
            // 对称情况处理
        }
    }
    getRoot().color = false;
    return root;
}

左旋方法：
- 对红黑树节点进行左旋操作，调整节点关系。

private void leftRotate(Node<K, V> x) {
    Node<K, V> y = x.right;
    x.right = y.left;
    if (y.left != null) {
        y.left.parent = x;
    }
    y.parent = x.parent;
    if (x.parent == null) {
        table[index] = y;
    } else if (x == x.parent.left) {
        x.parent.left = y;
    } else {
        x.parent.right = y;
    }
    y.left = x;
    x.parent = y;
}

右旋方法：
- 对红黑树节点进行右旋操作，调整节点关系。

private void rightRotate(Node<K, V> y) {
    Node<K, V> x = y.left;
    y.left = x.right;
    if (x.right != null) {
        x.right.parent = y;
    }
    x.parent = y.parent;
    if (y.parent == null) {
        table[index] = x;
    } else if (y == y.parent.right) {
        y.parent.right = x;
    } else {
        y.parent.left = x;
    }
    x.right = y;
    y.parent = x;
}

星途面试题库

面试题：优化Java HashMap解决哈希冲突性能的自定义策略

知识考点

面试题答案

策略原理

数据结构变化

相关方法实现思路