本文共 897 字,大约阅读时间需要 2 分钟。
首先上个图
key经过hash函数作用后得到一个槽(buckets或slots)的索引(index),槽中保存着我们想要获取的值本文讨论给出的部分源码,来源于Oracle JDK 1.7.0_71
本文主要讲述hashMap的三个问题
1.Object的hashCode方法和equals方法?
2.hashMap如何设计好的方法,使得冲突尽可能少?
3.hashMap在冲突发生的情况下,如何处理?
1.Object的hashCode方法和equals方法
(1)在没有被重写的情况下
equals用于判定两个对象是否是同一个对象(即内存地址一样、种类一样、内容一样)
hashCode是基于地址进行的一种映射,具有以下性质:
①equals返回true,hashCode值肯定一样
换句话说,hashCode值不一样,equals必定返回false
②hashCode值相同,equals返回结果不确定,但是返回false的概率很小
(2)只重写equals的情况
这个时候,equals返回true并不能保证hashCode值一样。
从后面我们可以了解到,这对hashMap的实现会带来很大的困扰,因为我们认为相等的两个对象,会被映射到hashMap不同的bucket之中。
由(1)、(2)可知
无论何时,我们应该保证equals与hashCode的逻辑保持一致性,
即不管我们认为什么是相等,当两个对象相等时,他们的hashCode应该相同。而且,不提供保证,两个对象不相等时,hashCode的关系。
2.hashMap如何设计好的方法,使得冲突尽可能少
其实结果很简单,先上个图
可以看出,主要就是两步
①将hashCode与hashSeed先与,在将结果不断移位得到h
②将h与length-1相与就得到了index
其中length就是底层的bucket的长度,其实就是数组的长度,而index就是数组的下标。
3.hashMap在冲突发生的情况下,如何处理
这个也是很简单的,其实hashMap底层采用的数据结构就是一个链表数组,即它是一个数组,数组每一个元素是一个链表。