HashMap

🚀面试口诉

1，hashmap是我们几乎每天用到的集合类,它以键值对的形式存在。
2, 在jdk1.7中：底层是数组加链表，1.8中采用的是数组加链表加红黑树，红黑树的引入是为了提高查询效率
3，1.7中hash碰撞采用头插法，头插法会形成循环链表（？），1.8尾插法
4，hash算法1.8进行了简化，up主记不清了，
5，最好传入一个二的次幂的初始化容量， put时，会初始化数组，容量为大于等于初始化容量的最近的二次幂，比如初始化容量为6，他初始化就是8。
6，key的hash值 与 上容量-1，计算出所在位置
7，扩容的问题：加载因子0.75，达到 容量 *0.75后就会扩容，两倍扩容
8，树化，数组容量达到64,链表长度大于等于8，后才会进行树化，链表长度小于6就会解除树化

构造方法：

put方法

  1. public V put(K key, V value) {
  2.         return putVal(hash(key), key, value, false, true);
  3.     }

第一次初始化数组

HashMap存储位置计算

jdk1.7
位置计算方式

  1.  key.hashCode()&(length-1)

jdk1.8高低索引
原因：HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同

  1. //jdk 1.80引入了高低索引，使得更加随机
  2. static final int hash(Object key) {
  3.         int h;
  4.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  5.     }

位置计算方式

  1. hash(k)&(length-1)

假设下标直接是key.hashCode()&(length-1)，则只有hashCode()的低位参与运算（因为hashCode()是32位的，而length-1一般不大，比如容量16,16-1=15,15二进制就是1111，换成32位的话，高位就全是0了，根据&运算规则1&1=1，其他情况都是0，所以hashCode()高位没参与运算了），如果低位不变，只是高位变，key.hashCode()&(length-1)值还是一样，那么就冲突了。

key.hashCode()右移16位就是高位变成了低位，原来高位全补0，,然后做^运算，实际就是原来的hashCode()值的高位与低位做^运算，这就解决了低位不变高位无论变与不变仍冲突的问题，现在无论高位低位哪个变，最终hash值都会变，更加散列

树化

树化前提：

  • 容量大于64
  • 链表长度大于8

过程：

  1. 把普通节点转化为treeNode
  2. 调用treeify进行树化

树化消耗性能，减少树化

扩容
前提

  • size大于等于 容量*加载因子

扩容大小
原本来的两倍，左移一位

  1.  if (oldCap > 0) {
  2.             if (oldCap >= MAXIMUM_CAPACITY) {
  3.                 threshold = Integer.MAX_VALUE;
  4.                 return oldTab;
  5.             }
  6.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  7.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
  8.                 newThr = oldThr << 1; // double threshold
  9.         }

扩容机制

计算hash值在旧容量最高位对应的二进制是1还是0，是1则会移动到高位索引(原索引位置+原容量)，是零则在低位索引也就是原位置

get方法

总结

添加新数据的方式

1.7头插
优势：

  1. 头插不需要遍历
  2. 设计者认为后插入的一般会先查找

问题：

  1. 多线程有可能循环链表产生，找不到尾节点，cup卡死

1.8尾插

数据结构