一.基本概念

image.png
HashMap 是基于哈希表的 Map 接口的实现,以 Key-Value 的形式存在,即存储的对象是 Entry (同时包含了 Key 和 Value) 。
在HashMap中,其会根据hash算法来计算key-value的存储位置并进行快速存取。key唯一,值可以相同
注意:
Java 容器实际上包含的是引用变量,而这些引用变量指向了我们要实际保存的 Java 对象。
总结:
基于Map接口实现、允许null键/值、非同步、不保证有序(比如插入的顺序)、也不保证序不随时间变化。

1.两个重要的参数:

容量(Capacity):buckets的数目
负载因子(Load factor):buckets填满程度的最大比例
对迭代性能要求很高的话,不要把容量设置的过大,也不要把负载因子设置过小
当bucket填充的数目(即hashmap中元素的个数)大于capacity*load factor时就需要调整buckets的数目为当前的2倍

2.put函数的实现

对key的hashCode()做hash,然后再计算index;

  • 如果没碰撞直接放到bucket里;
  • 如果碰撞了,以链表的形式存在buckets后;链表的插入和删除比较快
  • 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树;
  • 如果key相同就更新其value;
  • 如果bucket满了(超过load factor*current capacity),就要resize。 具体代码的实现如下:

    3.get函数的实现

    bucket里的第一个节点,直接命中;

  • 如果有冲突,则通过key.equals(k)去查找对应的entry

  • 若为树,则在树中通过key.equals(k)查找,O(logn);
  • 若为链表,则在链表中通过key.equals(k)查找,O(n)。 具体代码的实现如下:

    4.hash函数的实现

    在get和put的过程中,计算下标时,先对hashCode进行hash操作,然后再通过hash值进一步计算下标,如下图所示:
    image.png
    在对hashCode()计算hash时具体实现是这样的: ```java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

``` 在设计hash函数时,因为目前的table长度n为2的幂,而计算下标的时候,是这样实现的(使用&位操作,而非%求余):(n -1)& hash

设计者认为这方法很容易发生碰撞。为什么这么说呢?
在n - 1为15(0x1111)时,其实散列真正生效的只是低4bit的有效位,当然容易碰撞了。
因此,设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量),就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了,就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下,既减少了系统的开销,也不会造成的因为高位没有参与下标的计算(table长度比较小时),从而引起的碰撞。

如果还是产生了频繁的碰撞,会发生什么问题呢?
使用树来处理频繁的碰撞
在获取HashMap的元素时,基本分两步:

  • 首先根据hashCode()做hash,然后确定bucket的index;
  • 如果bucket的节点的key不是我们需要的,则通过keys.equals()在链中找。

在Java 8之前的实现中是用链表解决冲突的,在产生碰撞的情况下,进行get时,两步的时间复杂度是O(1)+O(n)。因此,当碰撞很厉害的时候n很大,O(n)的速度显然是影响速度的。
因此在Java 8中,利用红黑树替换链表,这样复杂度就变成了O(1)+O(logn)了,这样在n很大的时候,能够比较理想的解决这个问题,在Java 8:HashMap的性能提升一文中有性能测试的结果。

5.RESIZE的实现

当put时,如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例,那么就会发生resize。在resize的过程,简单的说就是把bucket扩充为2倍,之后重新计算index,把节点再放到新的bucket中;
大致意思就是说,当超过限制的时候会resize,然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。

怎么理解呢?例如我们从16扩展为32时,具体的变化如下所示:
image.png
因此元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:
image.png
因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图:
image.png
这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。

二.总结

1.什么时候会使用HashMap?他有什么特点?

是基于Map接口的实现,存储键值对时
它可以接收null的键值,是非同步的,HashMap存储着Entry(hash, key, value, next)对象。

2. 你知道HashMap的工作原理吗?

①通过hash的方法,通过put和get存储和获取对象。
存储对象时,我们将K/V传给put方法时,它调用hashCode计算hash从而得到bucket位置,进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。
获取对象时,我们将K传给get,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals()方法确定键值对。
如果发生碰撞的时候,Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java 8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。

3. 你知道get和put的原理吗?equals()和hashCode()的都有什么作用?

通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。
如果产生碰撞,则利用key.equals()方法去链表或树中去查找对应的节点

4. 你知道hash的实现吗?为什么要这样实现?

在Java 1.8的实现中,是通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在bucket的n比较小的时候,也能保证考虑到高低bit都参与到hash的计算中,同时不会有太大的开销。

5. 如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?

如果超过了负载因子(默认0.75),则会重新resize一个原来长度两倍的HashMap,并且重新调用hash方法。