面试题：Java Hashtable与HashMap在源码实现上的核心差异分析

Question

从线程安全性、哈希算法、扩容机制、键值对存储结构等源码实现角度，深入分析Hashtable与HashMap的核心差异，并说明这些差异在实际应用场景中的影响。

Answer 1

线程安全性

• Hashtable：
  • 源码实现：Hashtable的几乎所有方法（如put、get等）都被synchronized关键字修饰，这使得它是线程安全的。例如put方法：

public synchronized V put(K key, V value) {
    // 实现逻辑
}

• 实际影响：在多线程环境下可以直接使用，无需额外同步措施。但由于锁粒度较大，在高并发场景下性能较低，线程竞争激烈时会导致大量线程等待。
• HashMap：
  • 源码实现：HashMap的方法没有使用synchronized修饰，是非线程安全的。例如put方法：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

• 实际影响：在单线程环境下性能较高。但在多线程环境中使用时，可能会出现数据不一致等问题，如在扩容时可能导致链表成环，需要使用ConcurrentHashMap等线程安全的集合替代，或者手动同步。

哈希算法

• Hashtable：
  • 源码实现：直接使用对象的hashCode方法返回值作为哈希值，即int hash = key.hashCode();。
  • 实际影响：简单直接，但可能导致哈希冲突较多，尤其是当hashCode方法实现不理想时，会影响存储和查询效率。
• HashMap：
  • 源码实现：通过(h = key.hashCode()) ^ (h >>> 16)对hashCode进一步处理，这种方式将高位和低位信息都融入哈希值计算，减少哈希冲突。例如hash方法：

static final int hash(Object key) {
    int h;
    return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 实际影响：在相同数据量下，哈希冲突相对较少，能提高哈希表的存储和查找效率。

扩容机制

• Hashtable：
  • 源码实现：当count >= threshold（count为已存储元素个数，threshold为阈值）时进行扩容，扩容后的容量为原来的2倍 + 1。例如：

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;
    int newCapacity = (oldCapacity << 1) + 1;
    // 后续扩容逻辑
}

• 实际影响：扩容后容量增长较大，减少扩容频率，但可能造成空间浪费，特别是在数据量增长缓慢的情况下。
• HashMap：
  • 源码实现：当size >= threshold（size为已存储元素个数，threshold为阈值）时扩容，扩容后的容量为原来的2倍。例如：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null)? 0 : oldTab.length;
    int newCap = oldCap << 1;
    // 后续扩容逻辑
}

• 实际影响：扩容后容量增长适中，既能及时应对数据增长，又不会过度浪费空间，在大多数场景下能较好平衡性能和空间。

键值对存储结构

• Hashtable：
  • 源码实现：使用Entry数组存储键值对，Entry类实现了Map.Entry接口，采用链表法解决哈希冲突。例如：

private static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    // 其他方法
}

• 实际影响：在哈希冲突较多时，链表长度可能较长，查询性能会下降。
• HashMap：
  • 源码实现：JDK 1.8 之前和Hashtable类似，使用Entry数组和链表。JDK 1.8 及之后，当链表长度大于等于8且数组长度大于等于64时，链表会转换为红黑树，以提高查询性能。例如：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    // 其他方法
}

• 实际影响：在哈希冲突较少时，链表结构性能较好；在哈希冲突较多时，红黑树结构能保持较好的查询性能，整体性能更优。

综上所述，在单线程或多线程但线程安全要求不高的场景，HashMap因其高性能而适用；在多线程且对线程安全要求严格的场景，Hashtable虽性能有限但可直接提供线程安全保障，不过在高并发场景下，ConcurrentHashMap是更好的选择。