HashMap底层数据结构

底层数据结构是 数组。
示例

  1. HashMap<String, String> map = new HashMap<>();
  2. map.put("张三", "测试数据");
  3. map.put("李四", "测试数据");
  5. ## 底层其实是：
  6. ## [<>, <>, <张三,测试数据>,<>, <李四,测试数据>,<>]
  7. ## array[2] = <张三, 测试数据>
  8. ## map.get("张三") -> 计算key的hash值 -> 对数组长度取模 -> return array[2];

JDK1.8对hash算法和寻址算法的优化

hash算法优化
  1. static final int hash(Object key) {
  2.     int h;
  3.     return (key == null) 0 ? (h = key.hashCode()) ^ (h >>> 16);
  4. }
  6. #### 比如
  7. ####   hash                  1111 1111 1111 1111 1111 1010 0111 1100
  8. ##  hash>>>16                  0000 0000 0000 0000 1111 1111 1111 1111
  9. ## hash ^ (hash >>>16)         1111 1111 1111 1111 0000 0101 1000 0011
  11. #### 这样优化的目的
  12. 各个key设置的hash值,可能存在低16位是一样的，如果不考虑hash优化的话，他们经过取模计算之后，
  13. 会放在数组的同一个位置,需要进行复杂的hash冲突处理
  14. 优化之后，会使得高低16位都参与运算，降低hash冲突的概率

寻址算法的优化

数组长度为 n（前提：数组长度为 2的次方）
(n-1) & hash —> 计算出当前map元素在数组中的位置
使用（n-1） & hash 而不采用取模运算的原因： （n-1）& hash 的运算出的结果与hash对n取模运算的结果是一样的，但是取模运算的性能较差。

  1. 未优化的hash值    1111 1111 1111 1111 1111 1010 0111 1100
  2. n-1                0000 0000 0000 0000 0000 0000 0000 1111
  3. &n-1            0000 0000 0000 0000 0000 0000 0000 1100 -> 12
  5. 已优化的hash值    0000 0000 0000 0000 0000 0101 1000 0011
  6. n-1                0000 0000 0000 0000 0000 0000 0000 1111
  7. &n-1            0000 0000 0000 0000 0000 0000 0000 0011 -> 3   
  9. 未优化的hash值   1111 1111 1111 1001 1111 1010 0111 1100
  10. n-1               0000 0000 0000 0000 0000 0000 0000 1111
  11. &n-1            0000 0000 0000 0000 0000 0000 0000 1100 -> 12
  13. 已优化的hash值     0000 0000 0000 0000 0000 0101 1000 0101    
  14. n-1                0000 0000 0000 0000 0000 0000 0000 1111
  15. &n-1            0000 0000 0000 0000 0000 0000 0000 0101 -> 5

总结

hash算法优化：对每一个hash值，在他的低16位中，让高低16位进行异或，让他的低16位同时保持高低16位的特征，尽量避免一些hash值后续出现冲突，进入数组的同一个位置。
寻址算法优化：用与运算替代取模，提升性能。

hashMap如何解决hash碰撞问题

多个key，通过hash算法优化后的值还是一样，与n-1与运算后，发现定位的出来的数组的位置还是一样，出现了hash冲突问题。此时会在当前数组位置挂一个链表，这个链表放入多个元素，也就是多个,同时放在数组的一个位置中。
此时如果map.get，如果定位到数组里发现这个位置挂了一个链表，就遍历链表，从链表里面找到对应的就可以。遍历的时间复杂度为O(n)。
优化：如果链表的长度达到一定长度，会把链表转为红黑树，遍历一颗红黑树找到一个元素，此时时间复杂度为O(logn),性能会比链表高一些。

hashMap是如何进行扩容的

hashMap底层是一个数组，当这个数组满了之后，它会自动进行扩容，扩容为当前数组长度的两倍（rehash操作）。并重新计算寻址。扩容之后原本存在冲突的key，会在扩容之后重新分配到数组的新位置。

  1. ### 数组长度=16
  2. hash 1111 1111 1111 1111 0000 1111 0000 0101
  3. n-1  0000 0000 0000 0000 0000 0000 0000 1111
  4. &     0000 0000 0000 0000 0000 0000 0000 0101 -> 5
  6. hash 1111 1111 1111 1111 0000 1111 0001 0101
  7. n-1  0000 0000 0000 0000 0000 0000 0000 1111
  8. &    0000 0000 0000 0000 0000 0000 0000 0101 -> 5
  10. ### 数组长度=32
  11. hash 1111 1111 1111 1111 0000 1111 0000 0101
  12. n-1  0000 0000 0000 0000 0000 0000 0001 1111
  13. &    0000 0000 0000 0000 0000 0000 0000 0101 -> 5    
  15. hash 1111 1111 1111 1111 0000 1111 0001 0101
  16. n-1  0000 0000 0000 0000 0000 0000 0001 1111
  17. &    0000 0000 0000 0000 0000 0000 0001 0101 -> 21 
  19. 计算扩容后数组下标位置，可以判断当前hash值二进制结果是否多出一个bit的1,如果没有多，那么还是原来的index,
  20. 如果多了出来，那么就是index + oldCap（旧数组容量）。
  21. 通过这个方式，就避免了rehash的时候，用每个hash对新数组.length取模。取模性能不高，位运算的性能比较高。