首先做个知识铺垫，对于 HashMap 的了解更加深入
数组
数组就是在内存中连续申请一片内存用于存储数据，插入取出只需要使用数组的下标就可以了。时间复杂度为 O(1)，而其中查找其中的值需要遍历数组，其时间复杂度为 O(n)，对于有序数组来说可以使用二分查找等提高查找效率。但对于插入来说，如果要维护好数组的形态，则需要将插入点之后的数据依次向后。
链表
链表是由一个一个结点连接而成，每个结点中都会有一个指针指向与自己类型相同的下一个结点。故插入和删除只要改变前后结点的指针，释放内存，即可删除，操作时间复杂度为 O(1) ，但在内存中的分布并不连续，故我们查找数据的时候只能通过遍历的方式，其时间复杂度为 O(n)。
HashMap
HashMap 就是结合了数组和链表，查找，插入，删除的效率特别快。不考虑哈希冲突的情况下，时间复杂度几乎为 O(1)。而其的缺陷就是哈希冲突
HashMap 的主体是数组，链表是解决哈希冲突的方案(在 JDK 1.8 后链表中的结点超过八个将会优化成红黑树 ConcurrentHashMap 也进行了红黑树优化)
先来定义哈希函数为 具体位置 = 哈希函数(key)
而数组 table[具体位置] 即可插入，查找，等操作。但如果不同的 key 进行哈希函数运算得到相同的地址造成哈希冲突，通过在后面添加结点使用链表链接来解决哈希冲突。
在 HashMap 底层，运用了很多大量的位运算，可以加快运行速度。且 HashMap 的容量是按照 2 的 X 次幂进行扩充，对于扩充来说，还将之前散列好的数据进行散列，老数组散列成新数组通过位运算，速度也很快，故使用 2 的 X 次幂的策略扩充。
注意 HashMap 的初试容量并不是 16，而是 0，将会在第一次 put 的时候初始化容量为 16(感觉有点杠精的感觉...)
都知道 HashMap 是键值对(key-value)形式，那么什么样的对象才可以作为 key 呢？
那就是不可变对象(String, Integer 等）避免计算哈希值时发生改变。所以我们通常覆写 equal() 还要覆写 hashCode() 方法
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
对于分布不均匀的 HashMap jdk 1.8 会比 jdk 1.7 快
如果在极端情况哈希分布不均匀，jdk 1.8 的红黑树优化将会远远快于 jdk 1.7
网友评论