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 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); } } 复制代码
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槽位有关,往下看
HashMap
数据结构:数组+链表
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
扰动。
问题:是直接通过 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槽位的计算
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
需要遍历链表的时候就会出现死循环。
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; } 复制代码
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); } 复制代码
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++; } 复制代码
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); } //... } 复制代码
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); } 复制代码
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) 总结:数组扩容之后,迁移数据,槽位要么是在原来的地方,要么是原来的槽位+原来数组长度 复制代码