浙江龙网

  1. 首页 > 生活百科 > >

HashMap底层原理及jdk1.8源码解读( 三 )

生活百科

4、resize方法解读看不清查看原链接：高清图链接

HashMap底层原理及jdk1.8源码解读

文章插图
/** * 初始化或者是将table大小加倍,如果为空，则按threshold分配空间，* 否则加倍后，每个容器中的元素在新table中要么呆在原索引处，要么有一个2的次幂的位移 */final Node<K,V>[] resize() { // 原来的数据Node<K,V>[] oldTab = table;// 获取原来的数组大小int oldCap = (oldTab == null) ? 0 : oldTab.length;// 旧数组的扩容阈值，注意看，这里取的是当前对象的 threshold 值，下边的第2种情况会用到 。int oldThr = threshold;// 初始化新数组的容量和阈值int newCap, newThr = 0;// 1.当旧数组的容量大于0时，说明在这之前肯定调用过 resize扩容过一次，才会导致旧容量不为0 。if (oldCap > 0) {// 容量达到最大if (oldCap >= MAXIMUM_CAPACITY) {// 扩容的大小设置为上限threshold = Integer.MAX_VALUE;// 直接返回默认原来的，无法在扩了return oldTab;}// 如果旧容量是在16到上限之间else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 新数组的容量和阈值都扩大原来的2倍newThr = oldThr << 1; // double threshold}// 2. 到这里 oldCap <= 0，oldThr(threshold) > 0，这就是 map 初始化的时候，// 第一次调用 resize的情况else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;// 3. 到这里 ， 说明 oldCap 和 oldThr 都是小于等于0的 。也说明我们的map是通过默认无参构造来创建的else {// zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;// 16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 12}// 只有经过2.才会进入if (newThr == 0) {float ft = (float)newCap * loadFactor;// 把计算后的ft符合大?。?则赋值newThrnewThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 最后得到要扩容的大小threshold = newThr;// 用于抑制编译器产生警告信息@SuppressWarnings({"rawtypes","unchecked"})// 在构造函数时，并没有创建数组，在第一次调用put方法，导致resize的时候 ， 才会把数组创建出来 。// 这是为了延迟加载 ， 提高效率 。Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;// 判断原来的数组有没有值，如果没有则把刚刚创建的数组进行返回if (oldTab != null) {// 便利旧数组for (int j = 0; j < oldCap; ++j) {Node<K,V> e;// 判断当前元素是否为空if ((e = oldTab[j]) != null) {oldTab[j] = null;// 如果第一个元素的下一个元素为null，说明链表只有一个if (e.next == null)// 则直接用它的hash值和新数组的容量取模就行(这样运算效率高)，得到新的下标位置newTab[e.hash & (newCap - 1)] = e;// 如果是红黑树else if (e instanceof TreeNode)// 则拆分红黑树，这个小编就不带着往下深究了,感兴趣可以自己点进去看看((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 说明是链表且长度大于1else { // preserve order// 链表旧位置的头尾节点Node<K,V> loHead = null, loTail = null;// 链表新位置的头尾节点Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;// 这里小编不太明白了，只能参考大佬的讲解 ， 还是有点懵逼，等有时间懂了再来重新梳理do {next = e.next;// 如果当前元素的hash值和oldCap做与运算为0，则原位置不变if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 不为0则把数据移动到新位置else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 原位置不变的一条链表 ， 数组下标不变if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 移动到新位置的一条链表 ， 数组下标为原下标加上旧数组的容量if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}5、get和containsKey方法解读/*** 根据key获取对应的value*/public V get(Object key) {Node<K,V> e;// 调用后存在就获取元素的value返回return (e = getNode(hash(key), key)) == null ? null : e.value;}/*** 判断key是否在map中存在*/public boolean containsKey(Object key) { // 调用方法存在及不为nullreturn getNode(hash(key), key) != null;}/*** 我们发现底层都是getNode来进行干活的*/final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 判断数组不能为空 ， 然后取到当前hash值计算出来的下标位置的第一个元素if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 如果hash值和key都相等并不为null，则说明我们要找的就是第一个元素if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))// 返回第一个元素return first;// 如果不是第一个就接着往下找if ((e = first.next) != null) {// 如果是红黑树if (first instanceof TreeNode)// 则以红黑树的查找方式进行获取到我们想要的key对应的值return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 这里说明为普通链表，我们依次往下找即可do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}// 找不到key对应的值，返回nullreturn null;}

推荐阅读


上一篇：基于 Apache Hudi 极致查询优化的探索实践

下一篇：详解JS中 call 方法的实现