在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。
1.结构图
2.成员变量
1 | final float loadFactor; //加载因子 |
表示任务队列。
3.方法
1 | public V put(K key, V value) { |
(1)如果初始化table。
(2)计算key的hash值。
(3)通过hash值计算value在table中的index。
(4)判断key是否存在,如果存在直接覆盖。
(5)添加key-value。
1 | static int hash(int h) { |
这里将对象的hashCode再hash是为了减少冲突。比如Obj1的hashCode为1000 0000 0000 0000, Obj2的hashCode为1111 0000 0000 0000,当length没有足够大,使用indexFor方法获取的index将相同;使用再hash后的Obj1的hashCode为1000 1001 0000 1000, Obj2的hashCode为1111 1110 1110 1111,尽量让1变得均匀,防止低位不变,高位变化时,造成的hash冲突,使用indexFor方法获取的index将变得不同。
1 | private void inflateTable(int toSize) { |
capacity相当于table的总长度,threshold是table总长度乘以加载因子。
1 | static int indexFor(int h, int length) { |
这个方法非常巧妙,它通过 h & (table.length -1) 来得到该对象的保存位,而HashMap底层数组的长度总是 2 的 n 次方,这是HashMap在查找速度上的优化。
这段代码保证初始化时HashMap的容量总是2的n次方,即底层数组的长度总是为2的n次方。
当length总是 2 的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。
假设数组长度分别为15和16,优化后的hash码分别为8和9,那么&运算后的结果如下:
1 | h & (table.length-1) hash table.length-1 |
从上面的例子中可以看出:当它们和15-1(1110)“与”的时候,产生了相同的结果,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞,
8和9会被放到数组中的同一个位置上形成链表,那么查询的时候就需要遍历这个链 表,得到8或者9,这样就降低了查询的效率。同时,我们也可以发现,
当数组长度为15的时候,hash值会与15-1(1110)进行“与”,那么 最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,
空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!而当数组长度为16时,
即为2的n次方时,2n-1得到的二进制数的每个位上的值都为1,这使得在低位上&时,得到的和原hash的低位相同,加之hash(int h)方法对key的hashCode的进一步优化,加入了高位计算,
就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。
1 | void addEntry(int hash, K key, V value, int bucketIndex) { |
(1)判断是否已经达到允许数据存放的总数量。如果true则扩充table的容量,
1 | void resize(int newCapacity) { |
当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,这是一个常用的操作,而在HashMap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。
那么HashMap什么时候进行扩容呢?当HashMap中的元素个数超过数组大小loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过160.75=12的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。
1 | void createEntry(int hash, K key, V value, int bucketIndex) { |
在index上存放Entry,这里是一个链表结构,先将在这个index上的Entry取出来,然后放在新生成Entry.next中。这样就符合上面图中的数据结构。
1 | public V get(Object key) { |
(1)计算index。
(2)获取table上index位置的值。
(3)遍历链表。