为何HashMap的数组长度一定是2的次幂
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); }
如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index
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); //将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。 e.next = newTable[i]; newTable[i] = e; e = next; } } }
- 将老数组中的数据逐个链表地遍历 扔到新的扩容后的数组中
- 数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后
- 通过和 length-1进行位运算得到最终数组索引位置
1、
HashMap的数组长度一定保持2的次幂
比如16的二进制表示为 10000，那么length-1就是15，二进制为01111
同理扩容后的数组长度为32，二进制表示为100000，length-1为31，二进制表示为011111
- 会保证低位全为1，而扩容后只有一位差异，也就是多出了最右位的1
- 在通过 h&(length-1)的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)
2、
数组长度保持2的次幂，length-1的低位都为1，会使得获得的数组索引index更加均匀
3、
- &运算，高位是不会对结果产生影响的（hash函数采用各种位运算可能也是为了使得低位更加散列）
- 只关注低位bit，如果低位全部为1，那么对于h低位部分来说，任何一位的变化都会对结果产生影响，也就是说，要得到index=21这个存储位置，h的低位只有这一种组合
4、
- 如果不是2的次幂，也就是低位不是全为1此时，要使得index=21，h的低位部分不再具有唯一性了，哈希冲突的几率会变的更大
- index对应的这个bit位无论如何不会等于1了，而对应的那些数组位置也就被白白浪费了
get函数
public V get(Object key) { //如果key为null,则直接去table[0]处去检索即可。 if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); }
get方法通过key值返回对应value，如果key为null，直接去table[0]处检索
getEntry函数
final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } //通过key的hashcode值计算hash值 int hash = (key == null) ? 0 : hash(key); //indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }
key(hashcode)–>hash–>indexFor–>最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录
e.hash == hash 这里是否有必要判断？从而引出下个话题
重写equals方法需同时重写hashCode方法
如果没有重写hashCode方法
put:key(hashcode1)–>hash–>indexFor–>最终索引位置
get:通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置
由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null
小结：
在重写equals的方法的时候，必须注意重写hashCode方法
同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值
而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）
HashMap的数据结构
特点简介
- 无序
因为不一定挂到哪一个单向链表上的，因此加入顺序和取出也不一样
- 不可重复
1、使用equals方法来保证HashMap集合key不可重复，如key重复来，value就会覆盖
2、存放在HashMap集合key部分的元素，其实就是存放在HashSet集合中，则HashSet集合也需要重写equals和hashCode方法
参考文章
https://blog.csdn.net/woshimaxiao1/article/details/83661464
