HashMap源码解析二

HashCode是什么

还是举个栗子：一个工厂有500号人，下图用两种方案来存储厂里员工的信件。

image

左右各有27个信箱，左边保安大哥存信的时候不做处理，想放哪个信箱就放哪个信箱，当员工去找信的时候，只好挨个信箱找，再挨个比对信箱里信封的名字，万一哥们脸黑，要找的放在最后一个信箱的最底下，悲剧…所以这种情况的时间复杂度为O(N)；右边采用HashCode的方式将27个信箱分类，分类的规则是名字首字母(第一个箱子放不写名字的哥们)，保安大哥将符合对应姓名的信件放在对应的信箱里，这样员工就不用挨个找了，只需要比对一个信箱里的信件即可，大大提高了效率，这种情况的时间复杂度趋于一个常数O(1)。

例子中右图其实就是hashCode的一个实现，每个员工都有自己的hashCode，比如李四的hashCode是L，王五的hashCode是W(这取决于你的hash算法怎么写)，然后我们根据确定的hashCode值把信箱分类，hashCode匹配则存在对应信箱。在Java的Object中可以调用hashCode()方法获取对象hashCode，返回一个int值。那么会出现两个对象的hashCode一样吗?答案是会的，就像上上个例子中盖伦和老王的hashCode就一样，这种情况网上有人称之为”hash碰撞”，出现这种所谓”碰撞”的处理上面已经介绍了解决思路，具体源码后续介绍。

小结

hashCode是一个对象的标识，Java中对象的hashCode是一个int类型值。通过hashCode来指定数组的索引可以快速定位到要找的对象在数组中的位置，之后再遍历链表找到对应值，理想情况下时间复杂度为O(1)，并且不同对象可以拥有相同的hashCode。

HashMap的时间复杂度

通过上面信箱找信的例子来讨论下HashMap的时间复杂度，在使用hashCode之后可以直接定位到一个箱子，时间的耗费主要是在遍历链表上，理想的情况下(hash算法写得很完美)，链表只有一个节点，就是我们要的

image

那么此时的时间复杂度为O(1)，那不理想的情况下(hash算法写得很糟糕)，比如上面信箱的例子，假设hash算法计算每个员工都返回同样的hashCode

image

所有的信都放在一个箱子里，此时要找信就要依次遍历C信箱里的信，时间复杂度不再是O(1)，而是O(N)，因此HashMap的时间复杂度取决于算法的实现上，当然HashMap内部的机制并不像信箱这么简单，在HashMap内部会涉及到扩容、Java8中会将长度超过8的链表转化成红黑树，这些都在后续介绍。

小结

HashMap的时间复杂度取决于hash算法，优秀的hash算法可以让时间复杂度趋于常数O(1)，糟糕的hash算法可以让时间复杂度趋于O(N)。