HashMap核心机制put、get、哈希碰撞、扩容、红黑树、负载因子

HashMap是怎么工作的？

一、HashMap长什么样

HashMap底层是一个数组（table），数组的每个位置叫一个"桶"（bucket）。

往HashMap里存一个键值对，先算出key的哈希值，然后决定这个键值对应该放到哪个桶里。如果两个key算出来要去同一个桶，就叫"哈希碰撞"。

数组下标  0   1   2   3   4   5   6   7         |   |   |   |   |   |   |   |         ↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓         桶   桶   桶   桶   桶   桶   桶   桶

默认初始化时数组长度是16，负载因子0.75。也就是说存到第12个键值对时，就会触发扩容。

二、put的时候发生了什么

当调用 map.put(key, value) 时，内部做了这几步：

第一步，算哈希。先调key.hashCode()得到一个int，然后把高16位和低16位做异或，让哈希值更均匀。

第二步，算下标。用哈希值 &（数组长度-1），算出这个键值对应该放哪个桶