✨ HashMap的特点

HashMap 是 Java 中的一个基于 哈希表 的集合类，用于存储键值对（key-value）映射。

• 基于哈希表实现：

  • 数据存储在数组中，每个数组位置对应一个链表或红黑树（JDK 1.8 及以上版本）。

  • 通过哈希值定位键值对的存储位置。（同时重写 equals() 方法和 hashcode() 方法

• 非线程安全：

  • 多线程操作可能导致数据不一致问题。

• 允许 null：

  • 键和值均可以为 null，但键只能有一个 null。

• 动态扩容：

  • 默认初始容量为 16。

  • 加载因子为 0.75。

  • 当使用的存储空间超过阈值（容量 × 加载因子）时，HashMap 会动态扩容。

⚡ HashMap提升性能的建议

• 合理设置初始容量：如果在使用时可以预估 HashMap 存储的数据量大小，那么需要在创建时设置一个合适的初始容量，以避免频繁的扩容操作。Java 中 HashMap 默认初始容量是 16。
• 调整负载因子：官方提供的默认负载因子是 0.75。可以根据具体应用场景调整这个值。较低的负载因子会减少冲突，提高查找效率，但会占用更多内存（更加容易触发扩容）。较高的负载因子则会减少内存消耗，但可能增加冲突的概率，降低查找效率。
  • 高并发读取场景：可以降低负载因子，以减少哈希冲突，提高读取性能。
  • 内存受限场景：可以提高负载因子，以减少扩容次数和内存消耗，但可能会降低写入和查询的性能。
• 确保 hashCode 均匀分布：对应 key 的 hashCode() 方法生成的哈希值需均匀分布，减少哈希冲突。避免使用质量不高的哈希函数，防止大量键映射到相同的槽位上，造成性能瓶颈。

🔨 HashMap的常用方法

🔨 构造方法

• public HashMap()：默认构造方法
• public HashMap(int initialCapacity)：指定初始容量的构造方法
• public HashMap(int initialCapacity, float loadFactor)：指定初始容量和加载因子的构造方法
• public HashMap(Map<? extends K, ? extends V> m)：从其他 Map 初始化的构造方法

📌 添加键值对

• public V put(K key, V value)：添加或更新键值对
• public void putAll(Map<? extends K, ? extends V> m)：批量添加键值对

📌 删除键值对

• public V remove(Object key)：移除键值对
• public boolean remove(Object key, Object value)：按键值同时匹配移除

📌 查询键值对

• public V get(Object key)：获取值
• public boolean containsKey(Object key)：检查是否包含键
• public boolean containsValue(Object value)：检查是否包含值
• public V getOrDefault(Object key, V defaultValue)：获取默认值

📌 视图操作

• public Set<K> keySet()：获取所有键的集合
• public Collection<V> values()：获取所有值的集合
• public Set<Map.Entry<K, V>> entrySet()：获取所有键值对的集合

📌 替换操作

• public V replace(K key, V value)：替换值
• public boolean replace(K key, V oldValue, V newValue)：条件替换值

📌 遍历操作

🔨 使用for-each循环和entrySet()方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.HashMap;
import java.util.Map;

public class MapTraversalExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("key1", 1);
        map.put("key2", 2);
        map.put("key3", 3);

        // 使用for-each循环和entrySet()遍历Map
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
    }
}

🔨 使用for-each循环和keySet()方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.HashMap;
import java.util.Map;

public class MapTraversalExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("key1", 1);
        map.put("key2", 2);
        map.put("key3", 3);

        // 使用for-each循环和keySet()遍历Map的键
        for (String key : map.keySet()) {
            System.out.println("Key: " + key + ", Value: " + map.get(key));
        }
    }
}

🔨 使用 Lambda 表达式和forEach()方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.HashMap;
import java.util.Map;

public class MapTraversalExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("key1", 1);
        map.put("key2", 2);
        map.put("key3", 3);

        // 使用Lambda表达式和forEach()方法遍历Map
        map.forEach((key, value) -> System.out.println("Key: " + key + ", Value: " + value));
    }
}

🔧 HashMap的底层原理

🔧 存储原理

🛠️ JDK 1.7 以前

在 JDK 1.7 版本之前， HashMap 数据结构是数组和链表，HashMap 通过哈希算法将元素的键映射到数组中的槽位。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是$O(n)$，所以冲突很严重，一个索引上的链表非常长，效率就很低了。

HashMap 的默认初始容量为 16，负载因子为 0.75。也就是说，当存储的元素数量超过 16 × 0.75 = 12 个时，HashMap 会触发扩容操作，

当要塞入一个键值对的时候，会根据一个 hash 算法计算 key 的 hash 值，然后通过数组大小 n-1 & hash 值之后，得到一个数组的下标，然后往那个位置塞入这键值对。当发生哈希冲突时会使用闭散列法

链表的插入采用的是头插法，即每当发生哈希冲突时，新的节点总是插入到链表的头部，老节点依次向后移动，形成新的链表结构。

在多线程环境下，头插法可能导致链表形成环，特别是在并发扩容时。当多个线程同时执行 put() 操作时，如果线程 A 正在进行头插，线程 B 也在同一时刻操作链表，可能导致链表结构出现环路，从而引发死循环，最终导致程序卡死或无限循环。

🛠️ JDK 1.8以后

在 JDK 1.8 版本的时候做了优化，当一个链表的长度超过 8 且数组大小大于等于 64 的时候就转换数据结构，不再使用链表存储，而是使用红黑树，查找时使用红黑树，时间复杂度为$O(log n)$，可以提高查询性能，但是在红黑树节点数量较少时，即数量小于6 时，会将红黑树转换回链表。

在 JDK1.8 的时候，改成了尾插法，即新的节点插入到链表的尾部，保持插入的顺序。并且引入了红黑树。

🔨 hash方法的底层实现

1
2
3
4
5
6

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    // 如果键值为 null，则哈希码为 0（依旧是说如果键为 null，则存放在第一个位置）；
    // 否则，通过调用hashCode()方法获取键的哈希码，并将其与右移 16 位的哈希码进行异或运算。
}

目的：将 key 的 hashCode 值进行处理，得到最终的哈希值。hash 方法就是为了增加随机性，让数据元素更加均衡的分布，减少碰撞

将哈希值无符号右移 16 位，高位补0，意味着原哈希值的高 16 位被移到了低 16 位的位置。再与自身进行异或操作，从而使得原始哈希值的高 16 位和低 16 位就可以参与到最终用于索引计算的低位中。

示例

1
2
3
4

原始: 0001 0010 0011 0100 0101 0110 0111 1000
右移: 0000 0000 0000 0000 0001 0010 0011 0100
异或: ---------------------------------------
结果: 0001 0010 0011 0100 0100 0100 0100 1100

🔧 数组索引计算原理

通常基于哈希值计算数组下标使用该公式：hash % length，其中 hash 为以经过 hash() 方法优化后的哈希值， length 为数组容量

从二进制的角度上是获取 hash 的二进制表示中最低 $log(length)$ 位的值。

因此取余运算可以使用位运算代替，当 length 是 2 的幂时，n - 1 的二进制表示是全 1（如 length=16，length-1=15，即 1111），这样按位与操作实际上会相当于对 hash 的低 $log(length)$ 位进行保留。

故可得公式：hash & (length - 1) = hash % length = (length - 1) & hash

示例：hash 为 14，length 为 8，也就是 n 为3

1
2
3
4

  1110 (hash = 14)
& 0111 (length - 1 = 7)
  ----
  0110 (结果 = 6)

🔨 哈希碰撞的解决方法

Hash 碰撞是指在使用哈希算法时，不同的输入数据通过哈希函数计算后，得到了相同的哈希值（即散列值）。因为哈希值相同，所以这些键会被映射到哈希表的同一个位置，从而引发“碰撞”。

解决方法

• 拉链法（闭散列法）：将哈希表中每个槽的位置变成一个链表，当多个键的哈希值相同时，将它们存储在同一个链表中。
• 开放寻址法（开散列法）：如果出现碰撞，寻找哈希表中的下一个可用位置。
• 再哈希法（双重哈希）：在出现碰撞时，使用第二个哈希函数计算新的索引位置，减少碰撞的概率。

💡 拉链法（开散列法）

使用链表来处理冲突，每个哈希表的槽不仅存储单个元素，而是存储指向链表头部的指针。所有具有相同哈希值的元素都会被放入到同一个链表中。!

优点：

• 简单易实现，扩展性好。
• 在处理大量数据时，性能更为稳定。

缺点：

• 如果碰撞频繁，链表会变长，导致查询性能下降。
• 需要额外的内存来存储链表的指针。

💡 开放寻址法（闭散列法）

在哈希表中寻找下一个空闲的槽位以存储发生碰撞的元素。

• 线性探查法：在哈希表中查找下一个连续的空槽，将碰撞的键存入该槽中。
• 平方探查法：类似于线性探查，但探查的步长是二次方，减少了聚集问题。
• 双散列法：使用两个不同的哈希函数，第一次哈希决定初始位置，第二次哈希决定探查步长。

优点：

• 不需要额外的内存来存储指针或链表结构。
• 如果负载因子低，查找和插入的效率较高。

缺点：

• 随着哈希表的填充度增加，探查的次数会增加，导致性能下降。
• 删除元素时候，不能真的删除，只能打标，否则会导致查找错误。只能在下一个元素插入时，发现标记后才能替换原来的元素。