HashMap

一、什么是

• 基于哈希表的数据结构
• 允许以O(1)的时间复杂度进行元素的插入，查询和删除

二、底层结构

1.数据结构

• 在1.8以后，数组+链表+红黑树

数组：HashMap底层是一个数组，每个数组元素存放一个链表或红黑树（在JDK 1.8之后，链表过长时会转化为红黑树）。

链表：当新元素插入HashMap时，它首先根据哈希值找到数组中的某个位置（桶）。如果该位置为空，则直接插入；如果该位置已经存在元素（发生碰撞），则通过链表解决冲突。

红黑树：在JDK 1.8中，当链表长度超过一定阈值（默认是8）时，链表会转换为红黑树，从而将时间复杂度从O(n)降低到O(log n)。

 2.哈希函数和哈希值

• 每个键都会通过哈希函数计算出一个哈希值，然后通过哈希值决定数据应该存储在哪个桶中。桶是一个数组的存储位置。
• 哈希函数的主要目的是将数据均匀地分布在不同的桶中，从而减少哈希碰撞（即两个不同的键映射到同一个桶中的情况）。

3.负载因子和扩容

(1)负载因子

• HashMap有一个重要的参数叫负载因子，它决定了当数组中元素数量超过数组容量的多大比例时会触发扩容操作。默认的负载因子是0.75。

(2)扩容操作

• 当HashMap的元素数量达到数组容量的75%时，HashMap会自动进行扩容操作，通常会将数组容量扩展为原来的2倍。
•  扩容时，HashMap会重新分配一个更大的数组，并将原来的元素重新映射到新的数组中

三、底层代码

1.关键点解析

(1)构造函数

• HashMap提供了多个构造函数，包括无参构造函数、指定初始容量的构造函数、指定初始容量和负载因子的构造函数等。

(2)put方法

• put方法是插入元素的核心逻辑。
• 首先，计算键的哈希值。
• 其次，根据哈希值找到数组中的桶位置。
• 最后，如果该位置为空，则直接插入新元素；如果该位置已经存在元素，则通过链表或红黑树解决冲突。
• 如果链表长度超过阈值（默认是8），则链表会转换为红黑树。
• 如果元素数量超过扩容阈值（默认是数组容量的75%），则进行扩容操作。

(3)get方法

•  get方法用于根据键查找对应的值。
• 首先，计算键的哈希值。
• 其次，根据哈希值找到数组中的桶位置。
• 最后，如果该位置为空，则返回null；如果该位置上有元素，则遍历该位置对应的链表或红黑树，找到与键相等的键值对，然后返回该键值对的值。

(4)resize方法 

• resize方法是扩容的核心逻辑。
• 重新分配一个更大的数组，并将原来的元素重新映射到新的数组中。
• 在重新映射过程中，会根据元素的哈希值计算在新数组中的位置，并将元素插入到相应的桶中。

2.示例代码

(1)思路

• 首先创建了一个HashMap实例，并插入了一些键值对。
• 然后，通过键来访问元素，并遍历了HashMap中的所有键值对。
• 最后，通过插入大量元素来触发扩容操作，并再次遍历了HashMap。

(2)代码

import java.util.HashMap;  
 
public class HashMapExample { 
    public static void main(String[] args) { 
        // 创建HashMap实例 
        HashMap<String, Integer> map = new HashMap<>();
 
        // 插入键值对 
        map.put("apple",  1);
        map.put("banana",  2); 
        map.put("cherry",  3); 
 
        // 访问元素
        System.out.println(map.get("apple"));   // 输出: 1 
        System.out.println(map.get("orange"));  // 输出: null 
 
        // 遍历HashMap 
        for (String key : map.keySet())  {
            System.out.println(key  + ": " + map.get(key));  
        }
 
        // 扩容操作（自动触发） 
        for (int i = 0; i < 1000; i++) {
            map.put("key"  + i, i); 
        } 
 
        // 再次遍历HashMap 
        for (String key : map.keySet())  {
            System.out.println(key  + ": " + map.get(key)); 
        } 
    } 
} 

四、线程安全性

1.HashMap是非线程安全

• 多个线程同时访问和修改HashMap时，可能会出现数据不一致的情况。
• 解决方法：增加额外的同步机制

2.ConcurrentHashMap

• 一个线程安全的哈希表
• 通过分段锁来实现并发访问

五、键的null值

1.HashMap允许null值

• HashMap允许使用一个null键和多个null值。当使用null键时，它会被映射到数组的第一个位置（索引为0的桶）。

• map.put(null,  "value1"); // 允许键为 null 
  map.put("key1",  null);   // 允许值为 null

 2.与HashTable的区别

• Hashtable不允许键或值为null。
• 如果强制将null作为键或值插入Hashtable，会抛出NullPointerException。

六、遍历方式

1. 使用 for-each 循环遍历键值对

for (Map.Entry<String, String> entry : map.entrySet())  {
    String key = entry.getKey(); 
    String value = entry.getValue(); 
    System.out.println("Key:  " + key + ", Value: " + value);
}

2. 使用 Iterator 遍历键值对

Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator(); 
while (iterator.hasNext())  {
    Map.Entry<String, String> entry = iterator.next(); 
    String key = entry.getKey(); 
    String value = entry.getValue(); 
    System.out.println("Key:  " + key + ", Value: " + value);
}

3. 使用 keySet 遍历键

for (String key : map.keySet())  {
    String value = map.get(key); 
    System.out.println("Key:  " + key + ", Value: " + value);
}

4. 使用 values 遍历值

for (String value : map.values())  {
    System.out.println("Value:  " + value);
}

七、常见面试题

1.为什么 HashMap 在 JDK 1.8 中引入了红黑树？

• 在 JDK 1.8 之前，HashMap 使用链表来解决哈希冲突。当链表过长时，查找、插入和删除操作的时间复杂度会退化为 O(n)。引入红黑树后，当链表长度超过 8 时，链表会转换为红黑树，将时间复杂度降低到 O(log n)，提高了性能。 

2.HashMap 的初始容量和负载因子是多少？

• HashMap 的默认初始容量是 16，负载因子是 0.75。 

3.HashMap 的扩容机制是什么？

• 当 HashMap 的元素数量超过数组容量的 75% 时，会触发扩容操作，数组容量会扩展为原来的 2 倍。扩容时，HashMap 会重新分配一个更大的数组，并将原来的元素重新映射到新的数组中。 

4.HashMap 如何保证线程安全？

• HashMap 本身不是线程安全的。如果需要在多线程环境下使用 HashMap，可以使用 ConcurrentHashMap 或者对 HashMap 进行同步处理，例如使用 Collections.synchronizedMap 方法。 

八、HashMap性能优化

1.初始容量的选择

2.负载因子的调整

3.自定义哈希函数

九、Hashmap、HashTable和LinkedHashMap区别