🍊 底层工作原理
当我们向HashMap中插入元素(k1, v1)时，它会应用哈希算法获得一个哈希值，并将其映射到相应的内存地址。通过这种方式，我们可以获取与键相关的数据。如果该位置没有其他元素，它会直接放入一个Node类型的数组中。默认情况下，HashMap初始大小为16，并且负载因子为0.75。负载因子是一个介于0和1之间的浮点数，它决定了HashMap在扩容之前内部数组的填充度。因此，当元素数量达到12时，底层将进行扩容，将数组大小扩大为原来的2倍。如果该位置已经存在其他元素(k2, v2)，那么HashMap将调用k1的equals方法和k2进行比较。如果返回值为true，则表明两个元素相同并使用v1替换v2。如果返回值为false，则表明两个元素不同，并以链表的形式存储(k1, v1)。不过，当链表中的元素数量较多时，查询效率将下降。为了解决这个问题，在JDK1.8版本中对HashMap进行了升级。具体而言，当HashMap中存储的数据满足链表长度超过8、数组长度大于64时，将会将链表替换为红黑树，以提高查询效率。
你可以把HashMap想象成一本电话簿，每个电话簿里都有很多联系人的名字和对应电话号码。但是，电话簿有个特殊的地方，它不是按照联系人名字的首字母顺序排列的，而是按照一个特别的规则排列的。
这个规则就是Hash算法。Hash算法的作用就是将联系人的名字通过一定的计算，转化成一个数字（hash值），然后再根据这个数字找到对应的页面，在页面中查找联系人的电话号码。就像我们在电话簿中找到联系人的电话号码一样。
但是，如果很多联系人的名字都是相似的，就像张三、张三三、张三四等，这时候用Hash算法就会遇到一个问题：如果两个联系人的名字经过Hash算法计算后得到的数字一样，就会出现“冲突”，也就是两个联系人的名字被映射到同一个页面上了。这时候，HashMap就需要解决这个冲突的问题。
HashMap的解决方法就是用链表的方式把冲突的联系人存储起来。例如，张三和张三三两个联系人，经过Hash算法计算后得到的数字一样，导致他们被映射到同一个页面上了。那么，HashMap就会把张三和张三三这两个联系人都存储在同一个链表中。
但是，随着联系人越来越多，同一个页面中存放的联系人也越来越多，链表就会变得很长，这样查找联系人的效率就会变慢。而为了提高查找效率，HashMap就会把链表变成红黑树，这样查找联系人的效率就会更高了。这就像我们在电话簿中找到联系人的电话号码，如果联系人名字相同的有很多个，我们就可以通过电话簿的索引来快速地找到联系人的电话号码，不需要一个一个地查找。
另外，HashMap还有一个很重要的参数，就是负载因子。负载因子是一个介于0和1之间的浮点数，它决定了HashMap在扩容之前内部数组的填充度。如果负载因子设置得太小，就会导致数组很快就被填满了，就需要扩容；如果负载因子设置得太大，虽然数组中还有很多位置可以使用，但由于链表或红黑树太长，查找效率却很低。因此，建议负载因子设为0.75，这个值经过多次实验得出，能够保证在时间和空间上达到一个平衡。
总的来说，HashMap是一种非常重要的数据结构，在很多场景下都会被使用到。有了对HashMap的深入了解，我们就可以在使用它的时候更加得心应手了。
🍊 数据结构
HashMap的底层数据结构是一个哈希表，它是由一个数组和若干个链表或红黑树构成的。下面分别介绍数组、链表和红黑树这三种数据结构的特点和用途。
🎉 1.数组
HashMap中的数组主要用于存储哈希表的节点，它是由若干个Node对象构成的。Node是HashMap中的一个内部类，它包含了键值对数据、哈希值、指向下一个节点的指针等信息。Node的定义如下：
// 定义了一个泛型的静态类 Node，实现了 Map.Entry 接口 static class Node<K,V> implements Map.Entry<K,V> { // hash 值 final int hash; // 键 final K key; // 值 V value; // 链表的下一个节点 Node<K,V> next; // 构造函数，初始化变量 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; // hash 值 this.key = key; // 键 this.value = value; // 值 this.next = next; // 链表的下一个节点 } // 获取键 public final K getKey() { return key; } // 获取值 public final V getValue() { return value; } // 获取键值对的字符串表示形式 public final String toString(){ return key + "=" + value; } // 获取哈希码 public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } // 设置新的值，返回旧的值 public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // 判断两个键值对是否相等 public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
数组中的每个元素都是一个Node对象，它可以包含一个键值对，同时也可以是链表或红黑树的头节点。数组的长度会随着元素的不断插入而不断增加，当元素的数量超过数组容量的75%时，HashMap会进行扩容操作。
🎉 2.链表
在HashMap中，链表主要用于解决哈希冲突，当两个键值的哈希值相同时，它们会被存储在同一个位置的链表中。链表的每个节点都是一个Node对象，其中包含了键值对和指向下一个节点的指针。
链表的插入操作非常简单，只需要将新节点插入到链表的头部即可。但在查找操作中，由于需要遍历链表，所以效率较低。
为了提高查找效率，JDK1.8中增加了链表转红黑树的功能，当链表长度超过8时，会将其转换为红黑树。这个转换过程会使得查找的效率大大提高。
🎉 3.红黑树
红黑树是一种自平衡的二叉搜索树，它的左右子树高度差不超过1，能够保证查找、插入、删除等操作的时间复杂度为O(log n)。在HashMap中，红黑树用于取代链表，在链表长度超过8时，将链表转换为红黑树，以提高查找效率。
红黑树中的每个节点也是一个Node对象，它包含了键值对、哈希值等信息。与链表不同，红黑树中的节点是按照键值大小排列的，这使得查找操作可以具有O(log n)的时间复杂度。
当红黑树中的节点数小于6时，可以将其转换为链表，以节约内存。转换过程也是非常简单的，只需要按照键值顺序遍历树，然后重新将节点存储到原来的数组中即可。
🍊 哈希算法
首先，我们需要了解哈希算法。哈希算法是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。通俗点说，就是将任意大小的数据映射到固定大小的数据上。在HashMap中，哈希算法的作用是将键值映射到数组中的一个位置上。
在Java中，哈希算法的实现主要有两种：除留余数法和乘数法。
📝 1.除留余数法
除留余数法是一种较为常见的哈希算法，它的基本思想是将数据除以某个数后取余数作为它的哈希值。比如，我们可以选择数组长度作为除数，对于键k，我们可以用 k % 数组长度来得到它的哈希值。
具体来说，在HashMap中，哈希算法的实现是通过取键值k的hashCode()值，然后使用除留余数法将其映射到数组的某个索引位置上。HashMap中的哈希算法实现如下：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
其中，key.hashCode()方法返回的是键值key的哈希值，h >>> 16是对h进行无符号右移16位操作。这里的h ^ (h >>> 16)是为了让哈希值的高位和低位都能够参与哈希运算。
📝 2.乘数法
乘数法是另一种常见的哈希算法，在Java中也有应用。它的基本思想是，将数据乘以一个小数，然后取结果的小数部分，再乘以数组长度，最后取整数部分作为哈希值。具体实现中，可以选择一个介于0和1之间的小数作为乘数，通常选择一个接近黄金比例的数。
在Java中，乘数法的实现可以参考HashMap中的hash函数：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
这里的实现方式和除留余数法类似，不同之处在于乘数法需要再进行一次乘法运算。
🍊 HashMap版本问题
大家都知道，在Java中，HashMap是一种常用的数据结构，经常被用来存储键值对。其中，键是唯一的，值可以重复。但是在JDK1.7版本中，HashMap存在两个问题，会导致CPU利用率非常高，而在JDK1.8版本中，这两个问题得到了优化。
首先，我们来看看JDK1.7中HashMap的问题。在扩容时，HashMap需要进行rehash操作，这个过程非常消耗时间和空间，因为需要重新计算所有元素的hash值，并把它们放到新的位置上。其次，当并发执行扩容操作时，会出现链表元素倒置的情况，从而导致环形链和数据丢失等问题。
为了解决这些问题，在JDK1.8版本中，HashMap做了如下的优化。首先，在元素经过rehash之后，其位置要么是在原位置，要么是在原位置+原数组长度，这并不需要像旧版本的实现那样重新计算hash值，而只需要看看原来的hash值新增的那个bit是1还是0就好了。在数组的长度扩大到原来的2倍、4倍、8倍时，索引也会根据保留的二进制位上新增的1或0进行适当调整。
其次，在JDK1.8中，发生哈希碰撞时，插入元素不再采用头插法，而是直接插入链表尾部，从而避免了环形链表的情况。这样可以减少链表的长度，从而提高查询效率。
不过，在多线程环境下，还是会发生数据覆盖的情况。如果同时有线程A和线程B进行put操作，线程B在执行时已经插入了元素，而此时线程A获取到CPU时间片时会直接覆盖线程B插入的数据，从而导致数据覆盖和线程不安全的情况。
为了解决这个问题，可以采用synchronized关键字或者ConcurrentHashMap来实现线程安全的put操作。其中，synchronized关键字可以确保在put操作期间，没有其他线程可以修改HashMap中的数据。而ConcurrentHashMap则是使用一种类似于分段锁的方法来保证线程安全。每个段都有自己的锁，多个线程可以同时访问不同的段，从而提高并发能力。
综上所述，JDK1.8中对HashMap的改进很有价值，可以让我们更加高效地使用这个数据结构，并避免线程安全问题和CPU利用率过高的问题。
🍊 HashMap并发修改异常
在高并发场景下，使用HashMap可能会出现并发修改异常，这是因为多个线程同时竞争去修改同一个数据，导致了数据不一致的情况。例如，有两个线程A和B同时要往HashMap中添加元素，A线程添加了一个key-value，但是在value还没有添加完成时，B线程也来添加了同样的key-value，这时候就会覆盖掉A线程所添加的value，这就是出现并发修改异常的情况。
为了解决这个问题，有四种解决方案。第一种是使用HashTable，它是线程安全的，但是它把所有相关操作都加上了锁，因此在竞争激烈的并发场景中性能会非常差。第二种是使用工具类Collections.synchronizedMap(new HashMap<>())，将HashMap转化成同步的，但是同样会有性能问题。第三种解决方案是使用写时复制（CopyOnWrite）技术。在往容器中加元素时，不会直接添加到当前容器中，而是先将当前容器的元素复制出来放到一个新的容器中，然后在新的容器中添加元素。写操作完毕后，再将原来容器的引用指向新的容器。这种方法可以进行并发的读，不需要加锁。但是在复制的过程中会占用较多的内存，并且不能保证数据的实时一致性。
最后，使用ConcurrentHashMap则是一种比较推荐的解决方案。它使用了volatile，CAS等技术来减少锁竞争对性能的影响，避免了对全局加锁。在JDK1.7版本中，ConcurrentHashMap使用了分段锁技术，将数据分成一段一段的存储，并为每个段配备了锁。这样，当一个线程占用锁访问某一段数据时，其他段的数据也可以被其他线程访问，从而能够实现真正的并发访问。在JDK1.8版本中，ConcurrentHashMap内部使用了volatile来保证并发的可见性，并采用CAS来确保原子性，来解决了性能问题和数据一致性问题。
综上所述，当我们在高并发场景下需要使用HashMap时，我们可以采用四种方式来解决并发修改异常，其中ConcurrentHashMap是最优的解决方案。
🍊 HashMap影响HashMap性能的因素
HashMap是Java中经常使用的一种数据结构，它可以存储键值对（key-value），并在O(1)的时间内快速访问到对应的value值。但是，在使用HashMap时有两个关键因素会影响它的性能，分别是加载因子和初始容量。
加载因子用于确定HashMap中存储的数据量，并且默认加载因子为0.75。这个数值是经过充分考虑得出的，如果加载因子比较大，扩容发生的频率就会比较低，而浪费的空间会比较小，但是发生hash冲突的几率会比较大。举个例子，如果加载因子为1，HashMap长度为128，实际存储元素的数量在64至128之间，这个时间段发生hash冲突比较多，会影响性能。
相反，如果加载因子比较小，扩容发生的频率会比较高，浪费的空间也会比较多，但是发生hash冲突的几率会比较小。比如，如果加载因子为0.5，HashMap长度为128，当数量达到65的时候会触发扩容，扩容后为原理的256，256里面只存储了65个，浪费了。
为了平衡这两者，我们可以取一个平均数0.75作为加载因子，这样既可以减少hash冲突的几率，又可以尽可能地利用空间。
另一个影响HashMap性能的关键因素是初始容量，它始终为2的n次方，可以是16、32、64等这样的数字。即使你传递的值是13，数组长度也会变成16，因为它会选择最近的2的n次方的数。
在HashMap中，使用（hash值 &（长度-1））的二进制进行&运算来得到元素在数组中的下标。这样做可以保证运算得到的值可以落到数组的每一个下标上，避免了某些下标永远没有元素的情况。
举个例子，如果我有一个HashMap，容量为16，我的hash值是11001110 11001111 00010011 11110001（hash值），然后要进行&运算，运算的值是00000000 00000000 00000000 00001111（16-1的2进制）。这个值是16-1的2进制表示。然后，进行&运算得到的结果是00000000 00000000 00000000 00000001。这个运算的意思是，我把hash值的2进制的后4位和1111进行比较，然后，我的hash值的后4位的范围是0000-1111之间，这样我就可以与上1111，最后的值就可以在0000-1111之间，也就是0-15之间。
这样可以保证运算后的值可以落到数组的每一个下标中。如果数组长度不是2的幂次，后四位就不可能是1111，这样如果我用0000~1111的一个数和有可能不是1111的数进行&运算，那么就有可能导致数组的某些位下标永远不会有值，这样就无法保证运算后的值可以落在数组的每个下标上面。
因此，在使用HashMap时，要注意设置合适的加载因子和初始容量，才能保证它的性能最优。
🍊 HashMap使用优化
你想要优化 HashMap 的使用效率，可能就需要一些技巧了。那么，我个人总结了五个优化建议，帮助你更好地使用 HashMap。
🎉 1. 使用短String或者Integer作为键
首先，我们知道 HashMap 中的键值对是通过键来存储和查找的。因此，选择一个合适的键是非常重要的。我建议使用短 String、Integer 这些类作为键，特别是 String，因为它是不可变的（final），已经重写了 equals 和 hashCode 方法，符合 HashMap 计算 hashCode 的不可变性要求，可以最大限度地减少碰撞的出现。这样，我们可以有效地提高 HashMap 的查询效率。
🎉 2. 使用迭代器遍历entrySet
第二，建议不要使用 for 循环遍历 Map，而是使用迭代器遍历 entrySet，因为在各个数量级别迭代器遍历效率都比较高。举个例子，假如我们有一个 HashMap 存储了 10000 个键值对，我们想要遍历这个 Map，一共有两种方式：
第一种，使用 for 循环遍历 Map：
Map<String, Integer> map = new HashMap<String, Integer>(); // ...添加键值对... for (String key : map.keySet()) { Integer value = map.get(key); // 处理 value }
第二种，使用迭代器遍历 entrySet：
Map<String, Integer> map = new HashMap<String, Integer>(); // ...添加键值对... Iterator<Map.Entry<String, Integer>> iter = map.entrySet().iterator(); while (iter.hasNext()) { Map.Entry<String, Integer> entry = iter.next(); String key = entry.getKey(); Integer value = entry.getValue(); // 处理 value }
我们可以看到，第二种方式使用了迭代器，而不是 for 循环。这是因为在各个数量级别迭代器遍历效率都比较高，相比之下，for 循环则会稍慢一些。
🎉 3. 使用线程安全的 ConcurrentHashMap 或者迭代器 iterator.remove 方法来删除元素
第三，建议使用线程安全的 ConcurrentHashMap 来删除 Map 中的元素，或者在迭代器 Iterator 遍历时，使用迭代器 iterator.remove() 方法来删除元素。不可以使用 for 循环遍历删除，否则会产生并发修改异常 CME。如果我们需要从 HashMap 中删除元素，我们可以使用以下代码：
// 在迭代器 Iterator 遍历时使用 iterator.remove() 方法来删除元素 Iterator<Map.Entry<String, Integer>> iter = map.entrySet().iterator(); while (iter.hasNext()) { Map.Entry<String, Integer> entry = iter.next(); if (entry.getValue() == 0) { iter.remove(); // 在迭代器中删除元素 } } // 使用 ConcurrentHashMap 来删除元素 ConcurrentMap<String, Integer> map = new ConcurrentHashMap<String, Integer>(); map.put("key", 1); map.remove("key");
🎉 4. 在设定初始大小时要考虑加载因子的存在
第四，建议在设定初始大小时要考虑加载因子的存在，最好估算存储的大小。我们可以使用 Maps.newHashMapWithExpectedSize(预期大小) 来创建一个 HashMap，Guava 会帮我们完成计算过程，同时考虑设定初始加载因子。加载因子越大，hash 冲突的概率就越高。因此，建议在指定初始大小时，要考虑加载因子的存在，尽量估算存储大小，以减少冲突的发生。
Map<String, Integer> map = Maps.newHashMapWithExpectedSize(10000);
🎉 5. 适当加大初始大小，同时减少加载因子
最后，如果 Map 是长期存在而 key 又是无法预估的，那就可以适当加大初始大小，同时减少加载因子，降低冲突的机率。在长期存在的 Map 中，降低冲突概率和减少比较的次数更加重要。我们可以使用以下代码来设置初始大小和加载因子：
Map<String, Integer> map = new HashMap<String, Integer>(10000, 0.75f);
综上所述，以上就是个人总结的五个优化建议，希望能给大家带来帮助，提高 HashMap 的使用效率。
