HashMap（p12）

底层结构? 1.7 1.8 ?

1.7 数组 + 链表 1.8 数组 +(链表 + 红黑树)

运行原理

put 操作: 为了可以快速查找选择如下方式

输入的 key 调用 hashcode 方法进行第一次运算得到 hash 值,然后再进行二次 hash,接着用二次 hash 的值与 map 的容量进行取余操作,计算后的余数作为该字符串在 map 中的下标,

为何使用红黑树?

当链表过长时,会降低查询性能,加入红黑树就可以解决这个问题

为何不一上来就树化?

当链表较短时,查询速度要比树来得快,还有一个理由就是内存占用方面,树占用的内存要比链表多,所以没必要一上来就树化

同一下标下的链表过长,怎么解决?

• 当插入 map 的 size 的四分之三以上的元素时,map 会自动扩容,解决链表过长的问题

何时会树化?

• 当原始 hash 码都相同时,扩容就无法解决链表过长的问题了,这时就要树化,前提条件是满足树化的阈值,阈值为 8,链表长度大于 8,并且容量大于等于 64 的场合,才会树化,容量不大于 64,会继续尝试扩容
• 红黑树特点: 父节点左边都比父节点本身小,右边都比父节点本身大,比较方式为,先比 hash 值大小,大小一样比较字符本身大小

索引计算优化?

优化前提是容量必须为 2 的 n 次幂

正常是用 hash 值,取余容量,但是也以优化成 hash 值按位&(容量-1)

为何二次 hash?

让 hash 变的更均匀,保证链表高度不会超过阈值,防止超长列表的产生

数据丢失

处于多线程的模式下,当两个 key 计算下标相同时,后赋值的 key 会覆盖掉先赋值的 key

扩容死链

重写 hashcode 为了有更好的 hash 分布,重写 equals 是为了,当两个 key 计算出的索引都一样 需要进一步用 equals 比较是否为同一个对象,hashcode 相同,equals 不一定相同,equals 相同,则 hashcode 一定相同

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 方法。