【Java面试】HashMap和HashTable的区别、HashMap底层实现原理和扩容机制

分手后的思念是犯贱 2024-03-23 23:56 47阅读 0赞

### 一 HashMap和HashTable的区别 ###

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

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

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

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` 对象，其中包含键、值以及下一个节点的引用。

**存储流程：**

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

**扩容机制（Rehashing）：**

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

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

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

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

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

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

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

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

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

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