java面试题:HashMap和HashTable的区别、HashMap底层实现原理和扩容机制

一 HashMap和HashTable的区别

HashMap 和 HashTable 都是 Java 中用于存储键值对的数据结构，但它们有一些重要的区别。以下是 HashMap 和 HashTable 的主要区别：

线程安全性：
- HashMap 是非线程安全的。多个线程可以同时访问和修改 HashMap，如果没有适当的同步措施，可能会导致数据不一致或竞争条件。
- HashTable 是线程安全的。它的方法都被同步（synchronized）了，可以在多线程环境中使用，但这可能会降低性能。
允许空键和空值：
- HashMap 允许使用空（null）键和空（null）值。这意味着可以将 null 作为键或值存储在 HashMap 中。
- HashTable 不允许使用空（null）键或空（null）值。如果尝试存储空（null）键或空（null）值，会抛出 NullPointerException。
继承关系：
- HashMap 继承自 AbstractMap 类，而 HashTable 继承自 Dictionary 类（已过时）。
效率和性能：
- 由于 HashMap 不进行同步，适用于单线程环境，因此在性能上通常比 HashTable 更高效。
- HashTable 的同步操作可能导致性能下降，特别是在高并发环境下。
迭代器和枚举：
- HashMap 的迭代器是快速失败的（fail-fast iterator），可以检测到在迭代过程中其他线程对 HashMap 的修改。
- HashTable 的枚举（Enumeration）不是快速失败的，不能检测到其他线程的修改。
泛型支持：
- HashMap 支持泛型，可以指定键和值的类型。
- HashTable 不支持泛型，只能存储 Object 类型。

总的来说，如果在多线程环境下需要使用键值对存储，可以考虑使用 ConcurrentHashMap 来替代 HashTable，因为 ConcurrentHashMap 提供了更好的并发性能。在单线程环境下，通常首选使用 HashMap，因为它的性能更好。

java">import java.util.HashMap;

public class Test {
    public static void main(String[] args) {
        // 创建一个HashMap对象，键是String类型，值是Integer类型
        HashMap<String, Integer> hashMap = new HashMap<>();

        // 添加键值对到HashMap
        hashMap.put("zhangsan", 25);
        hashMap.put("lisi", 30);
        hashMap.put("wangwu", 28);
        hashMap.put("zhaoliu", 22);

        // 访问HashMap中的值
        System.out.println("Age of zhangsan: " + hashMap.get("zhangsan"));
        System.out.println("Age of wangwu: " + hashMap.get("wangwu"));

        // 检查是否包含某个键
        System.out.println("Contains key 'Bob': " + hashMap.containsKey("Bob"));
        System.out.println("Contains key 'Eve': " + hashMap.containsKey("Eve"));

        // 遍历HashMap的键值对
        for (String name : hashMap.keySet()) {
            int age = hashMap.get(name);
            System.out.println(name + " is " + age + " years old.");
        }

        // 删除键值对
        hashMap.remove("zhaoliu");

        // 获取HashMap的大小
        System.out.println("Size of HashMap: " + hashMap.size());
    }
}

二 HashMap底层实现原理和扩容机制

HashMap 的底层实现原理是基于哈希表（Hash Table）。它使用哈希函数将键映射到数组索引，然后将值存储在该索引处。当发生哈希碰撞（多个键映射到同一索引位置）时，HashMap 使用链表（或红黑树，自Java 8开始）来存储多个键值对。

底层数据结构：

HashMap 内部使用一个数组来存储哈希桶（Bucket）。
每个桶可以存储一个或多个键值对。
每个键值对被封装为一个 Node 对象，其中包含键、值以及下一个节点的引用。

存储流程：

当添加键值对时，HashMap 使用键的哈希码通过哈希函数计算出索引位置。
如果该位置为空，则直接将键值对放入。
如果位置不为空，可能发生哈希碰撞，HashMap 会遍历链表（或树）查找是否存在相同的键。
如果存在相同的键，更新对应的值，否则将新的键值对插入链表（或树）中。

扩容机制（Rehashing）：

HashMap 在添加键值对时，会监测当前元素数量是否超过了负载因子与初始容量的乘积（默认负载因子为0.75）。
如果超过了阈值，HashMap 会进行扩容，将数组大小增加一倍，然后重新计算每个键值对的新位置。
扩容时，所有键值对都需要重新计算哈希码并放入新的位置。这是一个相对耗时的操作。
扩容后，新的容量是原来的两倍，负载因子变得更小，从而减少哈希碰撞的概率，提高了性能。

红黑树（Red-Black Tree）：
在 JDK 8 及以后的版本中，HashMap 在处理哈希碰撞时引入了红黑树来提高性能，这被称为 “树化”（Treeify）操作。当链表长度达到一定阈值时，链表会被转换为红黑树，以减少查找、插入和删除操作的时间复杂度。以下是 HashMap 中红黑树部分的详细解释：

红黑树是一种自平衡的二叉搜索树，具有以下特性：

每个节点要么是红色，要么是黑色。
根节点是黑色的。
所有叶子节点（NIL 节点，空节点）都是黑色的。
如果一个节点是红色的，则其子节点必须是黑色的。
从根节点到任何叶子节点的路径上，黑色节点的数量相同。

红黑树在 HashMap 中的应用：
当 HashMap 中的链表长度超过一定阈值（默认为8）时，链表会被树化。这是为了防止出现长链表导致查找、插入和删除操作的性能下降。以下是树化操作的步骤：

如果链表长度小于等于阈值（8），则不进行树化，继续使用链表存储。
如果链表长度大于阈值，将链表转换为红黑树。
树化后，当链表中元素个数减少到小于等于6时，会将红黑树重新转换为链表，以节省内存。

优势和注意事项：
红黑树相对于链表在查找、插入和删除操作上具有更好的性能，其时间复杂度为 O(log n)，而链表的时间复杂度为 O(n)。这在处理大量数据时可以显著提高性能。

然而，红黑树的创建和维护相对于链表要复杂，占用的内存也更多。因此，红黑树主要用于优化哈希碰撞导致的性能问题，对于较小的链表，仍然使用链表存储。在实际使用中，应注意权衡和合理配置 HashMap 的初始化容量和负载因子，以便获得最佳性能。

红黑树是 HashMap 在解决哈希碰撞问题时的一种优化手段，可以提高大链表情况下的性能。它是一种自平衡的二叉搜索树，用于优化查找、插入和删除操作的性能。

总结：
HashMap 的底层实现原理基于哈希表，使用数组存储键值对，通过哈希函数映射到数组索引。在哈希碰撞时，使用链表或红黑树来存储多个键值对。为了保持性能，HashMap 会在负载因子达到一定阈值时进行扩容，以减少哈希碰撞的影响。这个底层实现使得 HashMap 能够高效地支持快速的键值对存储和检索。