HashMap与HashTable

HashMap的工作原理

HashMap是基于哈希表实现的，用于存储key-value的键值对，并允许使用null值和null键。由于是基于Hash表实现的，因此HashMap具有较高的查询效率，理想情况下HashMap的查找时间复杂度可达到O(1)。

(1)HashMap的存储结构 HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体（链地址法处理冲突）。HashMap内部封装了一个包含key和value的Entry类，用于存储键值对。在put操作中会根据key的hashcode计算在哈希表中的存储位置，并将Entry存入该位置。由于存在Hash冲突的情况，HashMap采用了链地址法来处理Hash冲突。即使用链表的形式将相同哈希值的元素连起来。如下图所示：

在这里插入图片描述

取元素时在HashMap的get方法中计算key的哈希值，并定位到元素所在桶的位置，接着使用equals方法查找到目标元素。

（2) HashMap的扩容与ReHash 由于HashMap存的长度是确定的，可以初始化时候指定长度或者默认长度16。随着HashMap中插入的元素越来越多，发生哈希冲突的概率会越来越大，相应的查找的效率就会越来越低。这意味着影响哈希表性能的因素除了哈希函数与处理冲突的方法之外，还与哈希表的装填因子大小有关。

我们将哈希表中元素数与哈希表长度的比值称为装填因子。装填因子 α= $\frac{哈希表中元素数}{哈希表长度}$

在HashMap中，装填因子的阈值为0.75，当装填因子大于0.75时则会出发HashMap的扩容机制。这里我们应该知道，扩容并不是在原数组基础上扩大容量，而是需要申请一个长度为原来2倍的新数组。因此，扩容之后就需要将原来的数据从旧数组中重新散列存放到扩容后的新数组。这个过程我们称之为Rehash。

Rehash的操作将会重新散列扩容前已经存储的数据，这一操作涉及大量的元素移动，是一个非常消耗性能的操作。因此，在开发中我们应该尽量避免Rehash的出现。比如，可以预估元素的个数，事先指定哈希表的长度，这样可以有效减少Rehash。

（3）JDK1.8中对HashMap的优化 JDK1.7 中，HashMap 采用位桶 + 链表的实现，即使用链表来处理冲突，同一 hash 值的链表都存储在一个数组中。但是当位于一个桶中的元素较多，即 hash 值相等的元素较多时，通过 key 值依次查找的效率较低。如下图所示的元素查找效率直接降低为了链表的时间复杂度o(n)

在这里插入图片描述为了优化这一问题，JDK 1.8 在底层结构方面做了一些改变，当每个桶中元素大于 8 的时候，会转变为红黑树，而红黑树的查找效率为o(logn)，高于链表的查找效率。详情参考：面试官：哈希表都不知道，你是怎么看懂HashMap的？ HashMap原理深入理解 HashMap的工作原理

HashMap扩容为什么是2的幂次方？

为了保证扩容后的数组索引与扩容前的数组索引一致
Rehash时的取余操作hash % length == hash & (length - 1)这个关系只有在length等于二的幂次方时成立

1). 保证新数组与老数组的索引一致

HashMap的初始容量是2的4次幂，扩容时候也是2的倍数。这样可以使添加的元素均匀的分布在HashMap中的数组上，减少Hash冲突。避免形成链表结构，进而提升查询效率。

16的二进制表示为10000，length-1的二进制位表示为01111，扩容之后变为32，二进制表示为100000，减1之后的二进制位为011111。

扩容前后只有一位的差距，即相当于(32-1)>>1==(16-1)。如下图所示：

1b9f4958eac5224f0e625dc679b3282d

这样在通过has&(length-1)时，只要hash对应的最左边的哪一个差异位为0，就能保证到扩容后的数组和老数组的索引一致。

当数组长度保持2的次幂，length-1的低位都为1，这样会使得数组索引index更加均匀。如下图:

a488d3b9cf221fac3f00681604fba489

上面的&运算，高位是不会对结果产生影响的（hash函数采用各种位运算也是为了使得低位更加散列）。只关注低位的bit,如果低位全部为1，那么对于h低位部分来说任何一位的变化都会对结果产生影响。也就是说，只要得到index=21这个存储位置，h的低位只有这一种组合。这也是数组长度设计为2次幂的原因

c28b9183a595598f0a4f2561797d51fe

如果不是2的次幂，也就是低位不是全为1此时，要使得index=21，h的低位部分不再具有唯一性了，哈希冲突的几率会变的更大，同时，index对应的这个bit位无论如何不会等于1了，而对应的那些数组位置也就被白白浪费了。

了解头插法和尾插法吗？

HashMap在处理哈希冲突时，会采用链表或红黑树来存储这些键值对。在链表结构中，插入新节点的方式主要有两种：

头插法：新节点插入到链表的头部
尾插法：新节点插入到链表的尾部

JDK1.7 及以前使用头插法处理哈希冲突，JDK 1.8及以后改为尾插法，并引入红黑树优化长链表查询

头插法

头插法代码实现如下：

newNode.next = head; 
head = newNode;

头插法的优势

插入效率高：时间复杂度为O(1)，无需遍历链表
符合"最近使用"原则：新插入的元素更可能被再次访问，放在头部可以提高访问效率
实现简单：不需要维护额外的尾指针

头插法的问题与缺陷

并发扩容导致链表成环：
- 多线程环境下，当HashMap扩容时，头插法可能导致链表逆序插入
- 线程A和线程B交替操作时，可能形成环形链表
- 一旦形成环形链表，get操作会陷入无限循环，CPU使用率飙升至100%
顺序不一致：
- 链表顺序与插入顺序相反，可能影响某些依赖插入顺序的操作
- 遍历顺序不可预测，可能导致迭代器失效问题
扩容性能问题：
- 头插法在扩容时需要处理链表倒置，增加额外计算开销
- 重新哈希时需要考虑顺序反转，实现复杂度较高

尾插法

尾插法代码实现如下：

if (tail == null) {
    head = e;
} else {
    tail.next = e;
}
tail = e;

尾插法的优势

避免链表成环：
- 尾插法保持链表顺序不变，彻底解决并发扩容导致的环形链表问题
- 扩容时节点迁移顺序一致，不会产生循环引用
保持插入顺序：
- 链表顺序与插入顺序一致，遍历结果更稳定可预测
- 符合先进先出原则，适合缓存实现等场景
简化扩容逻辑：
- 扩容时节点重新分配更直接，减少复杂度
- 不需要处理链表倒置问题，提高代码可维护性
与红黑树转换的协同：
- JDK 1.8引入红黑树优化，尾插法保持的顺序便于链表转红黑树
- 树化操作时不需要额外调整节点顺序

尾插法的局限性

插入效率略低：
- 需要遍历到链表末尾或维护尾指针
- 在短链表中性能差异不明显，但长链表中可能影响插入速度 - 并发问题并未完全解决：
- HashMap本身仍是非线程安全的，尾插法只是减少了特定问题的风险
- 多线程同时操作仍可能导致数据不一致
- 链表转红黑树时若多线程同时操作，仍可能导致死循环或结构异常 - 内存开销：
- 需要额外维护尾指针，增加少量内存消耗

为什么 JDK8 中 HashMap 从头插法改为了尾插法？

Java HashMap从头插法改为尾插法的主要原因在于解决多线程环境下的链表成环问题，并优化整体性能与稳定性。这一改变在JDK 1.8中实现，是HashMap底层结构的重要演进。

头插法在JDK 1.7及之前版本中被采用，其设计初衷是认为新插入的元素更可能被频繁访问，将其置于链表头部可提升查询效率。然而，这种设计在多线程扩容时存在严重缺陷。当多个线程同时触发扩容操作时，头插法的链表反转特性会导致链表节点引用关系混乱。具体表现为：线程A在扩容过程中挂起时保留了旧链表的引用，而线程B已完成扩容并反转了链表顺序；当线程A恢复执行后，基于过期引用继续操作，最终形成环形链表。这种环形链表一旦被遍历，会导致CPU占用率飙升至100%，程序陷入死循环。

尾插法在JDK 1.8中的引入从根本上解决了这一问题。通过保持链表插入顺序不变，尾插法确保扩容时节点迁移的顺序一致性，避免了环形链表的形成。这不仅消除了死循环风险，还带来了额外的优势：链表顺序与插入顺序一致，使得遍历结果更可预测；同时，这种顺序稳定性为红黑树转换提供了便利——当链表长度超过阈值时，顺序一致的链表更易于转换为平衡的红黑树结构。

此外，尾插法的改进还体现在性能优化上。虽然头插法的单次插入时间复杂度为O(1)，但扩容时需要处理链表反转，增加了计算开销；而尾插法通过维护头尾指针（JDK 1.8实现），使扩容迁移更直接高效。这种设计也更好地配合了JDK 1.8引入的高位运算扩容优化，减少了哈希重计算的开销。

值得注意的是，尽管尾插法显著提升了HashMap的稳定性，但它并未完全解决线程安全问题。HashMap本质上仍是非线程安全的，多线程环境下数据覆盖、竞态条件等问题依然存在。因此，在并发场景中，ConcurrentHashMap仍是更安全的选择。这一改进体现了Java集合框架在性能、安全性与可维护性之间的平衡考量，反映了对数据结构实际应用场景的深入理解

分析头插法导致链表成环原因

头插法导致链表成环的核心原因在于多线程并发扩容时，头插法的链表反转特性与线程间数据可见性问题共同作用的结果。具体分析如下：当多个线程同时触发HashMap扩容时，每个线程都会独立执行数据迁移。假设初始链表为A→B→C，线程T1和T2同时开始迁移：

线程竞争：两个线程都读取到链表头节点A及其next节点B。此时T1被挂起，T1仍持有A和B的引用，而T2继续执行。头插反转：T2通过头插法将节点迁移到新数组，形成C→B→A的顺序。由于头插法每次插入都会反转链表局部顺序，最终新链表的节点顺序与原链表相反。过期引用：当T1恢复执行时，它仍基于旧的引用（A→B）进行操作，而实际内存中B的next已指向A（因T2已完成反转）。T1将A头插到新位置后，A.next指向B，而B.next又指向A，形成A⇄B的环形结构。

这种环形链表的形成本质上源于两个关键因素：一是头插法固有的顺序反转特性，使得不同线程看到的链表状态不一致；二是扩容操作的非原子性，导致线程间无法感知彼此的修改。一旦环形链表形成，后续对该链表的遍历操作将陷入无限循环，造成CPU 100%的严重后果。 JDK 1.8改用尾插法后，由于节点迁移保持原有顺序，即使多线程并发操作也不会产生这种环形结构，从根本上解决了这一问题。但需注意，HashMap本身仍是非线程安全的，尾插法仅规避了特定死循环场景

HashTable 实现原理

Hashtable 是 Java 中一个线程安全的散列表实现，它基于哈希表的数据结构，存储键值对（key-value）。以下是其主要实现原理：

数据结构：

Hashtable 使用数组加链表的方式实现，底层是一个 Entry[] 数组，每个数组元素是一个链表。
当发生哈希冲突时，使用拉链法解决，即将冲突的元素放在同一个数组索引位置的链表中。

线程安全：

Hashtable 的大部分方法（如 put、get 等）都使用了 synchronized 关键字，确保在多线程环境下对表的操作是线程安全的。

哈希值计算：

使用 hash(key) 方法计算键的哈希值，然后通过 (hash & 0x7FFFFFFF) % table.length 计算出该键在数组中的索引位置。

扩容机制：

当表中的元素数量达到阈值（threshold = 容量 × 加载因子）时，会触发扩容操作，通常会将数组大小扩大为原来的两倍。

不允许 null 键或值：

Hashtable 不允许键或值为 null，否则会抛出 NullPointerException。

以下是 Hashtable 的部分核心源码分析：

内部类 Entry

Entry 是 Hashtable 的内部类，用于存储键值对，它是一个单向链表的节点

private static class Entry<K,V> implements Map.Entry<K,V> {
    int hash;
    K key;
    V value;
    Entry<K,V> next;

    Entry(int hash, K key, V value, Entry<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    // 其他方法省略
}

构造函数

Hashtable 提供了多种构造函数，用于初始化表的容量和加载因子

public Hashtable() {
    this(11, 0.75f); // 默认容量为11，加载因子为0.75
}

public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0 || loadFactor <= 0)
        throw new IllegalArgumentException();
    this.loadFactor = loadFactor;
    table = new Entry[initialCapacity];
    threshold = (int)(initialCapacity * loadFactor);
}

put 方法

put 方法用于插入键值对。

public synchronized V put(K key, V value) {
    if (value == null)
        throw new NullPointerException();
    Entry<K,V> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index]; e != null; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }
    if (count >= threshold) {
        rehash(); // 扩容
        tab = table;
        index = (hash & 0x7FFFFFFF) % tab.length;
    }
    tab[index] = new Entry<K,V>(hash, key, value, tab[index]);
    count++;
    return null;
}

get 方法

get 方法用于获取键对应的值

public synchronized V get(Object key) {
    Entry<K,V> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index]; e != null; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return e.value;
        }
    }
    return null;
}

扩容方法 rehash

当表中的元素数量超过阈值时，会调用 rehash 方法进行扩容。

protected void rehash() {
    int oldCapacity = table.length;
    Entry<K,V>[] oldMap = table;
    int newCapacity = oldCapacity * 2 + 1;
    Entry<K,V>[] newMap = new Entry[newCapacity];
    modCount++;
    threshold = (int)(newCapacity * loadFactor);
    table = newMap;
    for (int i = oldCapacity - 1; i >= 0; i--) {
        for (Entry<K,V> old = oldMap[i]; old != null; ) {
            Entry<K,V> e = old;
            old = old.next;
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = newMap[index];
            newMap[index] = e;
        }
    }
}