认识hashmap从基础的数据结构，了解1.7和1.8的区别和优化，理解如何扩容和负载因子的关联，以及使用hashmap的优化。

1.HashMap的基础数据结构

底层是以数组加链表构成的。

数组变量属性是Node<K,V>[] table。Node<K,V>是HashMap内部类，实现Map.Entry<K,V>接口。

Node内部类拥有四个属性：hash，key，value，next（Node）

链表在1.7之前是采用头插法的链表，1.8之后是采用尾插法。当链表个数达到8个并且数组长度超过64会变成红黑树。

2.hash碰撞的解决方法

HashMap中每个元素会根据key计算出在数组中的位置，如果计算出相同的位置下标，就会出现hash碰撞问题。

• 再哈希法

• 当哈希地址计算出来的下标值发生冲突，用其他的函数计算出另一个哈希函数 地址下标值，直到冲突不再产生为止。

• 开放寻址法

• 假设当前数组位置是1，它存放一个值a，现在想存一个b，但是这个位置被占了，就把b放到下一个位置2上去，如果2也被占了，就继续往下找，直到找到新位置。

• 拉链法

• 用的是链表的方式，在值上面增加一个next，指向下一个对象的内存地址，当出现hash冲突时，将新对象放到next指针上。

• 建立公共溢出区

• 数据分为数据区和溢出区，当hash冲突出现时，把冲突的元素都放入到溢出区。

HashMap是采用拉链法解决hash碰撞的。

3.链表转化为红黑树的条件

当链表中数据较多是，查询的效率会下降，所以在1.8版本后做了一个升级。

当链表长度大于8并且数组长度大于64，就会转换为红黑树。

如果链表长度大于8，但是数组长度小于64，会进行扩容操作。不会转换为红黑树。

红黑树需要进行左旋，右旋，变色操作来保持平衡，当数组长度小于64时，使用数组加链表比使用红黑树查询速度更要快、效率要更高。

在HashMap有一段描述，大致意思是说：在理想状态下受随机分布的hashCode影响，链表中的节点遵循泊松分布。链表中的节点数是8的概率已经接近千分之一，这个时候链表的性能已经很差，所以在这种比较罕见和极端的情况下才会把链表转变为红黑树，大部分情况下HashMap还是使用链表，如果理想的均匀分布节点数不到8就已经自动扩容了。

4.默认容量，负载因子

初始容量只是哈希表在创建时的容量，这里的容量是哈希表中桶的数量，数组初始化容量是16。

默认的负载因子是0.75f

5.扩容的条件和算法

当哈希表中的条目数超出了加载因子与当前容量的乘积时，就要对该哈希表进行扩容、rehash，也就是重建内部数据结构，扩容后的哈希表将具有两倍的原容量。

hashmap初始化容量时候，对容量大小做的处理，保证初始化容量为最近的2的幂次方，因为当数组长度为2的幂次方时，可以使用位运算来计算元素在数组中的下标，提高运算效率，除此之外还可以增加hash值的随机性，减少hash冲突。

6.负载因子为什么是0.75

加载因子是用来判断当前HashMap<K,V>中存放的数据量，默认的加载因子是0.75。

加载因子比较大，扩容发生的频率比较低，浪费的空间比较小，发生hash冲突的几率比较大。

比如，加载因子是1的时候，hashmap长度为128，实际存储元素的数量在64至128之间时间段比较多，这个时间段发生hash冲突比较多，造成数组中其中一条链表比较长，会影响性能。

加载因子比较小，扩容发生的频率比较高，浪费的空间比较多，发生hash冲突的几率比较小。

比如，加载因子是0.5的时候，hashmap长度为128，当数量达到65的时候会触发扩容，扩容后为原理的256，256里面只存储了65个，浪费了。综合了一下，取了一个平均数0.75作为加载因子。

当负载因子为0.75,代入到泊松分布公式，计算出来长度为8时，概率=0.00000006，概率很小了，这也是为什么上面我们提到的当链表长度为8时才会转红黑树的原因。

7.jdk1.7和1.8对比

对比jdk1.7和1.8版本可以发现，1.7版本的时候有二个地方是有些问题的，第一个是扩容的时候需要rehash操作，将所有的数据重新计算HashCode，然后赋给新的HashMap，rehash的过程是非常耗费时间和空间的。

第二个是当并发执行扩容操作时会造成环形链和数据丢失的情况，开多个线程不断进行put操作，当旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，就是因为头插法，所以最后的结果打乱了插入的顺序，就有可能发生环形链和数据丢失的问题，引起死循环，导致CPU利用率接近100%。在JDK1.8中，对HashMap这二点进行了优化。

7.1扩容rehash操作

第一点是经过rehash之后元素的位置，要么是在原位置，要么是在原位置再移动2次幂的位置。

HashMap的数组长度恒定为2的n次方，也就是说只会为16，32，64，128这种数。即便你给的初始值是13，最后数组长度也会变成16，它会取与你传入的数最近的一个2的n次方的数。在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成原位置+原数组长度。

HashMap中运算数组的位置使用的是数组长度-1，因为每次扩容会把原数组的长度*2，那么再二进制上的表现就是多出来一个1。比如初始长度为16的数组，对应的leng-1就是15，原数组15二进制后八位为0000 1111。扩容后的长度为32的数组，对应的leng-1就是31，二进制就变成了0001 1111。

再次扩容长度为64的数组，对应的leng-1就是63，二进制是0011 1111。扩容之后元素的位置是否改变则取决于与这个多出来的1的运算结果，运算结果为0则不需要换位置，运算结果为1则换新位置，新位置为老位置的高位进1。

举二个例子说明这个现象，假设某个元素的hashcode为52，这个52与15运算做按位与运算的的结果是4，这个52与31做按位与运算的的结果是20，20不就是等于4+16吗，刚好是原数组的下标+原数组的长度。

假设某个元素的hashcode为100，100&15=4，100&31=4，对于HashCode为100的元素来说，扩容后与扩容前其所在数组中的下标均为4。所以经过rehash之后，元素的位置要么是在原位置，要么是在原位置加原数组长度的位置。既省去了重新计算hash值的时间，而且由于新增的1bit是0还是1，可以认为是随机的，复杂度更高，从而让分布性更高一些。

说人话，总结jdk1.8的好处：

• 如何计算下标值的？

• 通过hash(key)函数  + (n – 1) & hash] 得到的

• hash(key)函数 是什么？

• (h = key.hashCode()) ^ (h >>> 16)，通过高16位和低16（数据右移）位进行异或，增加随机性。

• (n – 1) & hash]？

• n是数组长度，(n – 1) & hash]其实也就是让hash值除以数组长度求余，为了获取下标值。通过与操作实现求余相同的结果，与操作效率更高。

• 数组长度为2的n次幂的原因

• 为了保证求位置下标值进行与操作算法

• //返回给定目标容量的 2 次方
  static final int tableSizeFor(int cap) {
      int n = cap - 1;
      n |= n >>> 1;
      n |= n >>> 2;
      n |= n >>> 4;
      n |= n >>> 8;
      n |= n >>> 16;
      return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  }

7.2并发扩容链表头插法改为尾插法？

第二点，发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部，因此不会出现环形链表的情况，但是在多线程环境下，会发生数据覆盖的情况。

如果没有hash碰撞的时候，它会直接插入元素。

如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，线程A会把线程B插入的数据给覆盖，导致数据发生覆盖的情况，发生线程不安全。

实际的报错现象就是：java.util.ConcurrentModificationException并发修改异常。

导致原因：并发争取修改导致，一个线程正在写，一个线程过来争抢，导致线程写的过程被其他线程打断，导致数据不一致。

8解决并发问题？保证线程安全

• 使用HashTable

• HashTable是线程安全的，只不过实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

• 使用工具类Collections.synchronizedMap(new HashMap<>)

• 和Hashtable一样，实现上在操作HashMap时自动添加了synchronized来实现线程同步，都对整个map进行同步，在性能以及安全性方面不如ConcurrentHashMap。

• 使用读写分离，写时复制，CopyOnWrite

• 往一个容器里面加元素的时候，不直接往当前容器添加，而是先将当前容器的元素复制出来放到一个新的容器中，然后新的元素添加元素，添加完之后，再将原来容器的引用指向新的容器，这样就可以对它进行并发的读，不需要加锁，因为当前容器不添加任何元素。利用了读写分离的思想，读和写是不同的容器。会有内存占用问题，在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存。会有数据一致性问题，CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。

• 使用ConcurrentHashMap

• ConcurrentHashMap大量的利用了volatile，CAS等技术来减少锁竞争对于性能的影响。在JDK1.7版本中ConcurrentHashMap避免了对全局加锁，改成了局部加锁（分段锁），分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。不过这种结构的带来的副作用是Hash的过程要比普通的HashMap要长。所以在JDK1.8版本中CurrentHashMap内部中的value使用volatile修饰，保证并发的可见性以及禁止指令重排，只不过volatile不保证原子性，使用为了确保原子性，采用CAS（比较交换）这种乐观锁来解决。

8.1 CAS

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存地址里面的值和A的值是一样的，那么就将内存里面的值更新成B。

CAS是通过无限循环来获取数据的，若果在第一轮循环中，a线程获取地址里面的值被b线程修改了，那么a线程需要自旋，到下次循环才有可能机会执行。

volatile有三个特性：可见性，不保证原子性，禁止指令重排。

可见性：线程1从主内存中拿数据1到自己的线程工作空间进行操作（假设是加1）这个时候数据1已经改为数据2了，将数据2写回主内存时通知其他线程（线程2，线程3），主内存中的数据1已改为数据2了，让其他线程重新拿新的数据（数据2）。

不保证原子性：线程1从主内存中拿了一个值为1的数据到自己的工作空间里面进行加1的操作，值变为2，写回主内存，然后还没有来得及通知其他线程，线程1就被线程2抢占了，CPU分配，线程1被挂起，线程2还是拿着原来主内存中的数据值为1进行加1，值变成2，写回主内存，将主内存值为2的替换成2，这时线程1的通知到了，线程2重新去主内存拿值为2的数据。

禁止指令重排：首先指令重排是程序执行的时候不总是从上往下执行的，就像高考答题，可以先做容易的题目再做难的，这时做题的顺序就不是从上往下了。禁止指令重排就杜绝了这种情况。

9 HashMap开发使用优化？

对hashmap使用的优化，我个人看法有六点，

第一点，建议采用短String，Integer这样的类作为键。特别是String，他是不可变的，也是final的，而且已经重写了equals 和hashCode方法，这个和HashMap 要求的计算hashCode的不可变性要求不谋而合，核心思想就是保证键值的唯一性，不变性，其次是不可变性还有诸如线程安全的问题，以上这么定义键，可以最大限度的减少碰撞的出现。如果hashCode 不冲突，那查找效率很高，但是如果hashCode一旦冲突，要调用equals一个字节一个自己的去比较，key越短效率越高。

第二点迭代器遍历Map，在各个数量级效率稳定且较高，一般采用Iterator迭代器遍历Map，使用迭代器遍历entrySet在各个数量级别效率都比较高。

第三点concurrentHashMap或迭代器Iterator遍历删除，当遍历Map需要删除的时候，不可以for循环遍历，否则会产生并发修改异常CME，只能使用迭代器iterator.remove()来删除元素，或者使用线程安全的concurrentHashMap来删除Map中的元素。

第四点考虑加载因子地设定初始大小，设定时一定要考虑加载因子的存在。使用的时候最好估算存储的大小，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。Guava的做法是把默认容量的数字设置成预期大小 / 0.75F + 1.0F，可以使用Maps.newHashMapWithExpectedSize(预期大小);来创建一个HashMap，计算的过程guava会帮我们完成。

第五点减小加载因子，如果Map是一个长期存在而不是每次动态生成的，而里面的key又是没法预估的，那可以适当加大初始大小，同时减少加载因子，降低冲突的机率。毕竟如果是长期存在的map，浪费点数组大小不算啥，降低冲突概率，减少比较的次数更重要。

第六点使用IntObjectHashMap，HashMap的结构是 Node[] table; Node 下面有Hash，Key，Value，Next四个属性。而IntObjectHashMap的结构是int[] keys 和 Object[] values。在插入时，同样把int先取模落桶，如果遇到冲突，则不采样HashMap的链地址法，而是用开放地址法（线性探测法）index＋1找下一个空桶，最后在keys[index]，values[index]中分别记录。在查找时也是先落桶，然后在key[index++]中逐个比较key。所以，对比整个数据结构，省的不止是int vs Integer，还有每个Node的内容。性能IntObjectHashMap还是稳赢一点的，随便测了几种场景，耗时至少都有24ms vs 28ms的样子，好的时候甚至快1/3。

参考笔记：詹志伟-HashMap我可以讲半小时