HashMap 的数据结构
- 数组+链表
- 数组：
Entry<K,V>[] table - 链表：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
//存储下一个节点地址，所以hashMap是单项链表
Entry<K,V> next;
//注意这个不是真的k的hashcode，是经过hashmap扰动之后的hashcode
int hash;
}
- 问题，既然有数组，那么数组的大小怎么设置？
HashMap 容器初始化怎么设置
//如果对hashMap初始化传入这两个参数，那么数组大小多少呢，是传入多少就多少嘛？
HashMap map = new HashMap(2,0.75);
//下面是实例化的源码
public HashMap(int initialCapacity, float loadFactor) {
//加载因子
this.loadFactor = loadFactor;
//阈值
threshold = initialCapacity;
init();
}
//所以我们只能设置，hashmap的加载因子和阈值，这两个跟数组大小什么关系
//阈值 = 数组大小*加载因子
//每次put的时候如果数组元素个数>=阈值就要进行扩容
//现在问题是我们传入这个阈值，对数组大小有什么影响？
//看下put的源码
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
//会拿传入阈值去初始化数组大小，得到大于等于阈值的二的幂次方
inflateTable(threshold);
}
}
put->inflateTable -> roundUpToPowerOf2
roundUpToPowerOf2是设置容器初始值的关键- // Find a power of 2 >= toSize 在
roundUpToPowerOf2的注释有这句话，说是容器初始值要2的幂次方大于 tosize，后面再来讨论为什么要这么做，先看下怎么做到的
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
上面那段代码最关键的是 Integer.highestOneBit 写个测试方法简单测下这个方法的作用
public static void main(String[] args) {
System.out.println(Integer.highestOneBit(15));//8
System.out.println(Integer.highestOneBit(16));//16
System.out.println(Integer.highestOneBit(20));//16
}
测试可知Integer.highestOneBit获得的结果 1.二的幂次方 2.大于等于传入值 。点进入看下源码实现
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
按照highestOneBit的移位和或运算举个列子传入值为17
17 0001 0001
>> 0000 1000 右移1位结果
| 0001 1001 或运算结果
>> 0000 0110 右移2位结果
| 0001 1111 或运算结果
>> 0000 0001 右移4位结果
| 0001 1111 或运算
........ 最后会发现，结果都是 0001 1111 也就是说把 0001 0001 的低位全部改成 1
i - (i >>> 1)
i >>> 1 0000 1111
i - (i >>> 1) 0001 1111-0000 1111=0001 0000
总结：highestOneBit 1.右移动+或运算的目的是将所有位改为1 这个称为全1 2.i - (i >>> 1) 首先 i >>> 1的目的是获取比全1少一位，然后全1减去少一位的就是最高位是1，其他都是0，这样就可以拿到比传入值小的二的幂次方。
hashmap是怎么获取比传入值大的二的幂次方：Integer.highestOneBit((number - 1) << 1)
加入传入的number = 15 要获得的是16
Integer.highestOneBit((number - 1) << 1)
number - 1 15-1 14
<< 1 14-> 28
Integer.highestOneBit（28）= 16
总结：Integer.highestOneBit((number - 1) 1.<< 1 ) 1.<< 1 左移一位比较好理解，因为Integer.highestOneBit获取的是小于等于传入值的二的幂次方，所以左移一位可以传入值变大二的幂次方，结果也会大于等于传入值 2.number-1比较不好理解，这个主要是避免特殊情况，加入number=16，如果没有减一 16<<1=32,Integer.highestOneBit(32) = 32,然而结果是要获取16 3.以上就是获取容器大小为二得幂次方得方式，挺复杂也挺牛逼得。
为什么数组长度是二的幂次方
跟计算hash槽位有关，往下看
java7 HashMap 是怎么计算key的哈希槽位的
前提需要了解 HashMap 数据结构：数组+链表
indexFor(hash, table.length)
indexFor 通过hash和数组长度计算
static int indexFor(int h, int length) {
return h & (length-1);
}
假如 h：0010 1011 length：16
length-1 0001 0000 -> 0000 1111
h & (length-1) 0010 1011
0000 1011 转为十进制为11在0-15
总结： 1.要知道indexFor的目的是什么，是要获取0-（length-1）的数字 2.lengthe-1有什么含义，这就涉及到为什么length要是二的幂次方，从二进制的角度看，二的幂次方最高位是1其他都是0，减一这样就获得最高位是0，其他位都是1，hashcode & 上 除了最高位的都是1之后结果的范围只能在0-（length-1），所以从这里就可以知道为什么上面获取数组的长度为二的幂次方。3.但是这个算法又有个问题，就是hashCode & (length-1) 这个操作hashCode 只有低位跟（length—1）发生 & 操作，参与到槽位的分配，高位参与不到，可能导致槽位分配不均匀，所以，需要进行hash扰动。
存入之得hash值是怎么计算得，如何更加均匀
问题：是直接通过key.hashCode嘛，如果是这样得话，可能存在一个问题，我们对象重新hashcode方法，但是大部分值都一样，这样就做不到hash均匀分撒，所以HashMap对hashCode之后得值进行了hash扰动，让其更加散列，看下HashMap具体是怎么实现得。
final int hash(Object k) {
//获得hash种子，默认为0
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
//0 异或 key的hashcode ，结果不变
h ^= k.hashCode();
//h >>> 的过程就是让高位参与hash槽计算
//异或操作扰动hash
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
总结：hash这个方法大概就是通过左移，异或操作让原本的hashCode能够更加散列，让原本的hashCode高位能参与到hash槽位的计算
数组长度计算，槽位计算，hash取值这三个是HashMap的重点也是难点，同样也是互相联系的
链表是怎么插入的，经典面试题，头插入and尾插法
HashMap 遇到hash冲突怎么解决，用链表，用链表就涉及到一个问题，怎么插入链表比较合适
- 头插法
场景：往第2个槽位put数据
//头插法一行代码就可以搞定
//1.新建一个节点，next节点指向原本链表的头节点 next = table[1]
//2.头节点 table[1] = 新建节点
table[1] = new Entry（hash，key，value，next = table[1]）;
- 尾插法
//获取头节点
//需要遍历节点，将最后一位节点的next指向新节点
for(Entry entry = table[1];entry = entry.next){
if(entry.next == null){
entry.next = new Entry（hash，key，value，next = null）;
}
}
比较： 很明显头插法比尾插法简单，效率更高，大概是因为这个原因，HahsMap采用了头插法，但是头插法也带来了多线程扩容问题:循环链表，导致后面如果有get或者put需要遍历链表的时候就会出现死循环。
put方法
public V put(K key, V value) {
//刚开始没有设置数组大小，就会进入`inflateTable`方法促使话数组大小
//inflateTable调用roundUpToPowerOf2方法获取到数组大小为二的幂次方
//threshold 默认16
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
//对 null 的设置，所以hashmap是可以传入null作为key的
//key = nulll 放到数组的第一位
return putForNullKey(value);
//根据key获得到经过扰动的hashcode
int hash = hash(key);
//根据hashcode和数组长度获取hash槽位
int i = indexFor(hash, table.length);
//遍历所在的hash槽位上的链表，如果存在相同的key就替代
//什么才算是相同的key，这就涉及到为什么重写hashCode之后还要重新equals
//通过比较hahsCode是否相等，之后还需要比较==或者通过equals比较是否相同
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//添加元素
addEntry(hash, key, value, i);
return null;
}
addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
//数组扩容条件 (size >= threshold) && (null != table[bucketIndex])
//数组元素大小大于等于阈值同时需要put的头节点不为空
if ( (size >= threshold) && (null != table[bucketIndex])
//) {
//扩容大小是原来数组大小的两倍
resize(2 * table.length);
//扩容之后需要重新计算hash值
hash = (null != key) ? hash(key) : 0;
//扩容之后重新计算槽位
bucketIndex = indexFor(hash, table.length);
}
//新建新的节点
createEntry(hash, key, value, bucketIndex);
}
createEntry
void createEntry(int hash, K key, V value, int bucketIndex) {
//头插法插入数据
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
HashMap 扩容，以及多线程下扩容的问题
addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
//在添加元素的时候会进行判断是否扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容
resize(2 * table.length);
//todo 不懂为什么还要重新计算hashCode
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//...
}
resize
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//新建一个数组
Entry[] newTable = new Entry[newCapacity];
//进行数据迁移
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//新数组赋值给老数组
table = newTable;
//扩容之后重新设置阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//两层for循环
//第一层针对数组
//第二层针对链表
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//重新计算操作
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
**总结：**1.扩容数组长度为原来的两倍 2.扩容是新建一个新的数组，hashmap直接引用新的数组对象 3.扩容之后需要重新设置阈值 4.扩容多线程会产生循环链表
扩容之后迁移数据槽位分配有什么规律嘛
假设1：
hash： 0010 0011
原数组长度16：0001 0000
原槽位： 0010 0011 & （0001 0000 - 0000 0001）
0010 0011 & 0000 1111 = 0000 0011 (十进制为3)
现数组长度2*16=32： 0010 0000
现槽位： 0010 0011 & （0010 0000 - 0000 0001）
0010 0011 & 0001 1111 = 0000 0011 (十进制为3)
结果：发现槽位还是原来那个位置
假设2：
把hash从0010 0011 改为 0011 0011
现槽位： 0010 0011 & （0010 0000 - 0000 0001）
0011 0011 & 0001 1111 = 0001 0011 (十进制为3+16)
总结：数组扩容之后，迁移数据，槽位要么是在原来的地方，要么是原来的槽位+原来数组长度
多线程下扩容出现的循环链表
