hashmap底层原理面试 hashmap源码扩容( 二 ) _hashmap

然后，我们知道HashMap的默认容量是16 ，然后是在哪里赋值的？从上面这个代码就可以知道this.threshold = tableSizeFor(initialCapacity);
static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n1;}这里涉及到计算机基本知识的，右移运算和或运算，下面给出图例：通过比较麻烦的计算得出n为16
往代码里翻，还找到下面这个构造方法public HashMap(Map m)：这个构造方法是用于构造一个映射关系与指定 Map 相同的新 HashMap：
public HashMap(Map m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false); }看一下putMapEntries这个方法：
final void putMapEntries(Map m, boolean evict) {// 传入的集合长度int s = m.size();if (s > 0) {// 判断table是否已经初始化处理if (table == null) { // pre-size 未初始化的情况// 加上1.0F的目的是对小数向上取整，保证最大容量，减少resize的调用次数float ft = ((float)s / loadFactor)1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);// 计算出来的t大于HashMap的阀值，进行tableSizeForif (t > threshold)threshold = tableSizeFor(t);}else if (s > threshold) // 已经初始化的情况，进行扩容resizeresize();// 遍历，将map中的所有元素都添加到hashMap中for (Map.Entry e : m.entrySet()) {K key = e.getKey();V value = https://www.shwenmu.com/wenda/e.getValue();putVal(hash(key), key, value, false, evict);}}}5、Jdk8中HashMap的算法5.1、HashMap中散列算法在HashMap的java.util.HashMap#hash ，这个方法中有特定的用于计算哈希值的方法：这个方法的作用？这个方法就是用于hashMap当put对应的key之后，计算特定的hashCode ，然后再(n-1)&hash计算对应的数组table的下标，这个后面跟一下HashMap源码才比较清楚：
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}看起来代码只有两行，然后其实蕴含了一种散列算法的思想，下面简单分析一下：这里先将代码进行拆分，看起来清晰点：
static final int hash(Object key) {// 传入的key为null ，返回默认值0if (key == null) return 0;// 计算哈希codeint h = key.hashCode();// 将计算出来的hashCode右移16位，相当于乘于(1/2)的16次方int t = h >>> 16;// 将两个值做异或运算然后返回return h ^ t;}其实里面要做的事情是先计算出hashCode ，然后将hashCode右移16位，然后这两个数再做异或运算。看起来是这么一回事，然后作者的意图是什么？首先既然是散列算法，散列算法的目的就是为了让数据均匀分布
从图可以看出，使用异或运算，出现0和1的概率是相等的，所以这就是为什么要使用异或运算的原因，散列算法的本质目的就是为了让数据均匀分布，使用异或运算得出的哈希值因为比较均匀散列分布，所以出现哈希冲突的概率就小很多

补充：
与运算：两个数相应的位数字都是1 ，与运算后是1 ，其余情况是0；或运算：两个数相应的位数字只要有1个是1 ，或运算后是1 ，否则是0；异或运算：两个数相应的位数字相同，结果是0 ，否则是1；

然后为什么再进行右移16位？我们知道， int类型最大的数值是2的32次方，然后可以分为高16位加上低16位，右移16位就是使数值变小了， “左大右小” ，这个是位移运算的准则
5.2、什么是HashMap中哈希冲突？哈希冲突也可以称之为哈希碰撞，理论上的哈希冲突是指计算出来的哈希值一样，导致冲突了，不过在HashMap中的哈希冲突具体是指(n-1)&hash ，这个值是hashMap里数组的下标。Jdk8之前的处理方法是通过链表处理，只要hash冲突了，就会将节点添加到链表尾部；jdk8之后的做法是通过链表红黑树的方法，最开始哈希冲突了，也是用链表，然后链表节点达到8个，数组长度超过64的情况，转成红黑树，这个可以在源码里找到答案