本文呈现HashMap工作原理，和关于HashTable、ConcurrentHashMap的区别

一起来揭晓吧… …

什么是HashMap?

  • HashMap采用了“数组+链表+红黑树”的数据结构，能在查询和修改的时候继承了数组的线性查找和链表的寻址修改。
  • 存储方式是以键值对的方式进行存储(即:key-value)，HashMap可以存储为Null的键于值，而HashTable不支持（通过查看源码可知，HashTable获取的键值对分别是两个对象，判断对象为Null就抛异常；而HashMap则是通过处理，所以支持）
  • HashMap是非线程安全的，HashTable是线程安全的，所以HashMap效率比较快

HashMap的工作原理？

  • HashMap基于hashing的原理，我们使用put(key, value)存储对象到HashMap，使用get(key)从HashMap对象中获取对象。当我们调用put()方法时，会先对key调用hashCode()，计算并返回hashCode用于在Map中找到对应的bucket位置存储Node对象。
  • HashMap的初始长度为16
  • HashMap负载因子为0.75
  • 当HashMap的容量达到16*0.75=12时，就需要HashMap扩容，即扩容为原来的2倍,来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。
  • 如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表

如果两个对象的hashCode一致，会有什么后果？

因为HashMap的存储器的对象是通过key的hashCode来确认应该存放在哪一个bucket的位置，由于hashCode一致，所以会找到同一个bucket的位置，并将对象以链表的形势存放在这个bucket位置下

如果发生了碰撞，应该如何通过key取到值对象？

当我们调用get(key)方法时，会通过key计算其hahshCode，找到对应的bucket位置，再通过调用key.equals()方法在链表中找到正确的节点，最终找到值对象。

减少碰撞的方法？

  • 扰动函数可以减少碰撞，原理是如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这就意味着存链表结构减小，这样取值的话就不会频繁调用equal方法，这样就能提高HashMap的性能。（扰动即Hash方法内部的算法实现，目的是让不同对象返回不同hashcode。）

  • 使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。为什么String, Interger这样的wrapper类适合作为键？因为String是final的，而且已经重写了equals()和hashCode()方法了。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。

HashMap中hash函数怎么实现？

key hash
null 0
not null h = key.hashCode(); hash = h ^ (h >>> 16);

因为HashMap支持键为null，所以有两组算法

如何计算HashMap的下标？

  • 假设HashMap的数组长度为len
  • 假设键的hashCode为 hash = key.hashCode()
  • 下标: (len - 1) & (hash ^ (hash >>> 16))

重新调整HashMap大小存在什么问题吗？

当多线程的情况下，可能产生条件竞争。当重新调整HashMap大小的时候，确实存在条件竞争，如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的数组位置的时候，HashMap并不会将元素放在LinkedList的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了

为什么选用红黑树，而不选用二叉查找树？

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

红黑树的特性（摘抄维基百科）

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色（叶子是NIL节点）。
  4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

HashMap和HashTable的区别？

  1. hash值得计算不一样
    1. HashMap： (h = key.hashCode()) ^ (h >>> 16)
    2. HashTable: h = key.hashCode()
  2. 下标计算不一样
    1. HashMap: (tableLength -1) & (h = key.hashCode()) ^ (h >>> 16)
    2. HashTable: ((h = key.hashCode()) & 0x7FFFFFFF) % tableLength
  3. HashMap是非线程安全，HashTable是线程安全的。 单线程使用情况下，HashMap的效率会更快
  4. 负载因子是相同的：0.75
  5. 默认大小和扩容方案不一样：
    1. HashMap: 默认大小为16， 扩容：tableLength * 2
    2. HashTable: 默认大小为11， 扩容： tableLength * 2 + 1
  6. HashTable对每个方法都添加了synchronized关键字

ConcurrentHashMap

  • hash计算: h = key.hashCode(); (h ^ (h >>> 16) & 0x7fffffff)
  • 下标计算: i = (tableLength - 1) & hash
  • 初始值16
  • 负载因子：0.75
  • 当ConcurrentHashMap的容量达到16*0.75=12时，就需要ConcurrentHashMap扩容
  • ConcurrentHashMap采用了分段锁技术，线程安全

最后更新： 2019年10月12日 20:21

原始链接： https://maiyikai.github.io/2019/03/08/1552012657/

赏
× ~谢谢大爷~
打赏二维码