深入理解Java集合框架

客官°小女子只卖身不卖艺 2021-09-22 00:20 553阅读 0赞

Java集合实现了常用数据结构，是开发中最常用的功能之一。

Java集合主要的功能由三个接口：List、Set、Queue以及Collection组成。

常见接口:

  • List : 列表，顺序存储，可重复
  • Set ：集合，与数学中的集合有同样的特性：元素不能重复
  • Queue：队列
  • Collection：所有Java集合的接口，定义了“集合”的常用接口

结构结构

数据结构

常用集合

  • ArrayList 一种可以动态增长或缩减的索引集合，底层通过Ojbect[]数组实现，默认容量为10，在使用是如果确定仓储的数据容量应尽量为其初始化以避免动态扩容时的拷贝开销
  • LinkedList 高效插入删除的有序序列，是双向链表，使用node节点存储数据；它又实现了双向队列
  • ArrayDeque 用循环数组实现的双端队列
  • HashSet 一种没有元素的无序集合
  • TreeSet 有序的集合
  • LinkedHashSet 能记录插入顺序的集合
  • PriorityQueue 优先队列
  • HashMap 存储键/值关系数据
  • TreeMap 能根据键的值排序的键/值关系数据数据
  • LinkedHashMap 可以键/值记录添加顺序

Java集合框架结构

Java集合Collection.png

如何选用这些数据结构

通常选用基于我们需要处理的数据的特点以及集合的特点来确定的。

如果只是简单存储一组数据，如几个用户的信息，这时选用ArrayList是比较合适的，如果数据频繁添加、删除那选用LinkedList是比较合适的。

如果想存储一组数据且不希望重复，那选用Set集合合适的。

如果希望添加插入的数据能够有顺序，那选择TreeSet是比较合适的，当然TreeMap也可以。

使用

ArrayList

  1. import org.junit.Test;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.Collections;
  6. import java.util.List;
  8. public class ArrayListTest { 
  10.     @Test
  11.     public void test() throws Exception { 
  12.         ArrayList<Integer> list = new ArrayList<>();
  13.         // 更推荐使用面向接口的使用方式，方便以后切换
  14.         //List<Integer> list = new ArrayList<>();
  15.         list.add(3);
  16.         list.add(2);
  17.         list.add(1);
  19.         // for打印
  20.         for (Integer e : list) { 
  21.             System.out.println(e);
  22.         }
  24.         // 排序 小->大
  25.         Collections.sort(list);
  26.         System.out.println(list); // 打印
  28.         // 排序 大->小
  29.         List<Integer> list2 = Arrays.asList(2,3,5);
  30.         Collections.sort(list2,(a,b)->b-a);
  32.         // 排序 大->小
  33.         list2.sort((a, b) -> b - a); // 功能同上
  34.         System.out.println(list2);
  35.     }
  36. }
  37. // 输出
  38. 3
  39. 2
  40. 1
  41. [1, 2, 3]
  42. [5, 3, 2]

Set

  1. import org.junit.Test;
  3. import java.util.HashSet;
  4. import java.util.Objects;
  5. import java.util.Set;
  7. public class SetTest { 
  9.     static class User { 
  10.         String name;
  11.         int age;
  13.         public User(String name, int age) { 
  14.             this.name = name;
  15.             this.age = age;
  16.         }
  18.         @Override
  19.         public int hashCode() { 
  20.             return Objects.hashCode(this.name);
  21.         }
  23.         // 逻辑根据名字判断User是否相同
  24.         @Override
  25.         public boolean equals(Object obj) { 
  26.             if (obj == null) return false;
  27.             if (obj instanceof User) { 
  28.                 User u = (User) obj;
  29.                 return this.name != null
  30.                         ? this.name.equals(u.name)
  31.                         : u.name == null;
  32.             }
  33.             return false;
  34.         }
  36.         @Override
  37.         public String toString() { 
  38.             return "User{" +
  39.                     "name='" + name + '\'' +
  40.                     ", age=" + age +
  41.                     '}';
  42.         }
  43.     }
  46.     @Test
  47.     public void test() throws Exception { 
  48.         Set<Integer> set = new HashSet<>();
  49.         set.add(1);
  50.         set.add(2);
  51.         set.add(3);
  52.         set.add(3);
  53.         System.out.println(set);
  55.         // 添加重复的人
  56.         Set<User> users = new HashSet<>();
  57.         users.add(new User("张三",18));
  58.         // 重复，不进行添加
  59.         users.add(new User("张三",19));
  60.         users.add(new User("李四",20));
  61.         for (User u : users) { 
  62.             System.out.println(u);
  63.         }
  64.     }
  65. }
  67. // 输出
  68. [1, 2, 3]
  69. User{ name='null', age=18}
  70. User{ name='李四', age=20}

HashMap

  1. import org.junit.Test;
  3. import java.util.HashMap;
  4. import java.util.Map;
  6. public class HashMapTest { 
  7.     @Test
  8.     public void test() throws Exception { 
  9.         HashMap<String,String> map = new HashMap<>();
  11.         map.put("张三","110");
  12.         map.put("李四","119");
  13.         map.put("王二","120");
  14.         // 键重复，更新原有的
  15.         map.put("王二","139");
  17.         for (Map.Entry<String, String> entry : map.entrySet()) { 
  18.             System.out.println(entry.getKey()+" ---> "+entry.getValue());
  19.         }
  20.     }
  21. }
  22. // 打印
  23. 李四 ---> 119
  24. 张三 ---> 110
  25. 王二 ---> 139

源码分析

基于JDK1.8。

不重要的方法已经清除，保留的方法已经注释。

ArrayList

  1. package java.util;
  3. import java.util.function.Consumer;
  4. import java.util.function.Predicate;
  5. import java.util.function.UnaryOperator;
  6. import sun.misc.SharedSecrets;
  8. public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  9. { 
  10.     /** * 默认容量 */
  11.     private static final int DEFAULT_CAPACITY = 10;
  13.     /** * 空数组，用作初始化 */
  14.     private static final Object[] EMPTY_ELEMENTDATA = { };
  16.     /** * 共享空数组 */
  17.     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
  19.     /** * 存放数据数 */
  20.     transient Object[] elementData; // non-private to simplify nested class access
  22.     /** * 数组大小，elementData存储元素数量同步 */
  23.     private int size;
  25.     /** * 构造器 */
  26.     public ArrayList(int initialCapacity) { 
  27.         if (initialCapacity > 0) { 
  28.             this.elementData = new Object[initialCapacity];
  29.         } else if (initialCapacity == 0) { 
  30.             this.elementData = EMPTY_ELEMENTDATA;
  31.         } else {  // inittialCapatity < 0 抛出异常
  32.             throw new IllegalArgumentException("Illegal Capacity: "+
  33.                                                initialCapacity);
  34.         }
  35.     }
  37.     /** * 构造器 */
  38.     public ArrayList() { 
  39.         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  40.     }
  42.     /** * 构造器 */
  43.     public ArrayList(Collection<? extends E> c) { 
  44.         elementData = c.toArray(); // c!= null
  45.         if ((size = elementData.length) != 0) { 
  46.             if (elementData.getClass() != Object[].class)
  47.                 // 不是一个一个取值赋值给elementData，copyOf使用System.arrayCopy(), arrayCopy使用本地方法（JNI）效率很高
  48.                 elementData = Arrays.copyOf(elementData, size, Object[].class);
  49.         } else { 
  50.             // replace with empty array.
  51.             this.elementData = EMPTY_ELEMENTDATA;
  52.         }
  53.     }
  55.     /** * 去掉数组（elementData）中不存数据的部分 */
  56.     public void trimToSize() { 
  57.         modCount++;
  58.         if (size < elementData.length) { 
  59.             elementData = (size == 0)
  60.               ? EMPTY_ELEMENTDATA
  61.               : Arrays.copyOf(elementData, size);
  62.         }
  63.     }
  65.     /** * 调整List大小，可以扩容和缩容，缩容时最小容量不小于10 */
  66.     public void ensureCapacity(int minCapacity) { 
  67.         int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
  68.             ? 0
  69.             : DEFAULT_CAPACITY;
  71.         // 小于最小容量不调整，因此最小容量不会小于10
  72.         if (minCapacity > minExpand) { 
  73.             ensureExplicitCapacity(minCapacity);
  74.         }
  75.     }
  77.     /** * 最大容量 */
  78.     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  80.     /** * 动态扩容方法， 容量为之前的1.5倍 oldCapacity + (oldCapacity >> 1) */
  81.     private void grow(int minCapacity) { 
  82.         // overflow-conscious code
  83.         int oldCapacity = elementData.length;
  84.         int newCapacity = oldCapacity + (oldCapacity >> 1);
  85.         if (newCapacity - minCapacity < 0)
  86.             newCapacity = minCapacity;
  87.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  88.             newCapacity = hugeCapacity(minCapacity);
  89.         // minCapacity is usually close to size, so this is a win:
  90.         elementData = Arrays.copyOf(elementData, newCapacity);
  91.     }
  93.     private static int hugeCapacity(int minCapacity) { 
  94.         if (minCapacity < 0) // overflow
  95.             throw new OutOfMemoryError();
  96.         return (minCapacity > MAX_ARRAY_SIZE) ?
  97.             Integer.MAX_VALUE :
  98.             MAX_ARRAY_SIZE;
  99.     }
  101.     /** * 获取list大小 */
  102.     public int size() { 
  103.         return size;
  104.     }
  106.     /** * 判断list是否为空 */
  107.     public boolean isEmpty() { 
  108.         return size == 0;
  109.     }
  111.     // 每次取出元素操作时都会调用此方法对Ojbect数组原型进行类型转换
  112.     E elementData(int index) { 
  113.         return (E) elementData[index];
  114.     }
  116.     /** * 获取元素 */
  117.     public E get(int index) { 
  118.         rangeCheck(index); // 检查是否越界
  119.         return elementData(index);
  120.     }
  122.     /** * 添加元素 */
  123.     public boolean add(E e) { 
  124.         ensureCapacityInternal(size + 1);  // Increments modCount!!
  125.         elementData[size++] = e;
  126.         return true;
  127.     }
  129.     /** * 删除 */
  130.     public E remove(int index) { 
  131.         rangeCheck(index);
  132.         modCount++;
  133.         E oldValue = elementData(index);
  134.         int numMoved = size - index - 1;
  135.         if (numMoved > 0)
  136.             System.arraycopy(elementData, index+1, elementData, index,
  137.                              numMoved);
  138.         elementData[--size] = null; 
  139.         return oldValue;
  140.     }
  142.     /** * 两个list做差集 */
  143.     public boolean retainAll(Collection<?> c) { 
  144.         Objects.requireNonNull(c);
  145.         return batchRemove(c, true);
  146.     }
  148.     /** * 批量移除 */
  149.     private boolean batchRemove(Collection<?> c, boolean complement) { 
  150.         final Object[] elementData = this.elementData;
  151.         int r = 0, w = 0;
  152.         boolean modified = false;
  153.         try { 
  154.             for (; r < size; r++)
  155.                 if (c.contains(elementData[r]) == complement)
  156.                     elementData[w++] = elementData[r];
  157.         } finally { 
  158.             if (r != size) { 
  159.                 System.arraycopy(elementData, r,
  160.                                  elementData, w,
  161.                                  size - r);
  162.                 w += size - r;
  163.             }
  164.             if (w != size) { 
  165.                 // clear to let GC do its work
  166.                 for (int i = w; i < size; i++)
  167.                     elementData[i] = null;
  168.                 modCount += size - w;
  169.                 size = w;
  170.                 modified = true;
  171.             }
  172.         }
  173.         return modified;
  174.     }
  176.     @Override
  177.     public void forEach(Consumer<? super E> action) { 
  178.         Objects.requireNonNull(action);
  179.         final int expectedModCount = modCount;
  180.         @SuppressWarnings("unchecked")
  181.         final E[] elementData = (E[]) this.elementData;
  182.         final int size = this.size;
  183.         for (int i=0; modCount == expectedModCount && i < size; i++) { 
  184.             // 调用回调 （e）->{ //操作e }
  185.             action.accept(elementData[i]);
  186.         }
  187.         // 遍历过程禁止修改list！
  188.         if (modCount != expectedModCount) { 
  189.             throw new ConcurrentModificationException();
  190.         }
  191.     }
  193.     /** * 移除步骤： * 1. 标记移除 * 2. 修改线程 * 3. 移动元素 * 4. 清除尾部元素 */
  194.     @Override
  195.     public boolean removeIf(Predicate<? super E> filter) { 
  196.         Objects.requireNonNull(filter);
  198.         int removeCount = 0;
  199.         final BitSet removeSet = new BitSet(size);
  200.         final int expectedModCount = modCount;
  201.         final int size = this.size;
  202.         // 标记元素
  203.         for (int i=0; modCount == expectedModCount && i < size; i++) { 
  204.             @SuppressWarnings("unchecked")
  205.             final E element = (E) elementData[i];
  206.             if (filter.test(element)) { 
  207.                 removeSet.set(i);
  208.                 removeCount++;
  209.             }
  210.         }
  211.         if (modCount != expectedModCount) { 
  212.             throw new ConcurrentModificationException();
  213.         }
  214.         // shift surviving elements left over the spaces left by removed elements
  215.         final boolean anyToRemove = removeCount > 0;
  216.         if (anyToRemove) { 
  217.             final int newSize = size - removeCount;
  218.             // 移动元素 例如： [1][2][3] size=2 移动后 [1][3][3]
  219.             for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { 
  220.                 i = removeSet.nextClearBit(i);
  221.                 elementData[j] = elementData[i];
  222.             }
  223.             // 清除尾部元素
  224.             for (int k=newSize; k < size; k++) { 
  225.                 elementData[k] = null;  // Let gc do its work
  226.             }
  227.             // 更新size
  228.             this.size = newSize;
  229.             if (modCount != expectedModCount) { 
  230.                 throw new ConcurrentModificationException();
  231.             }
  232.             modCount++;
  233.         }
  234.         return anyToRemove;
  235.     }
  236. }

HashMap

底层数据结构：数组链表+红黑树

默认的容量为：16（1<<4）

扩容的条件：size>=容量*加载因子

扩容大小：旧容量2倍（newCap = oldCap << 1）

树化（terrify）的条件

  1. 容量长度大于等于64
  2. 链表成都大于8

树化的过程

  1. 把普通节点转换为TreeNode

  2. 调用treeify进行树化

    1. 调整节点
    2. 左旋右旋

put导致死循环的原因。在JDK1.7中插入元素使用头插法，插入的时候不需要遍历哈希桶，在多线程下这样可能形成循环链表。JDK8采用尾插法，循环找到最后一个节点，然后在最后一个节点插入元素。

存储结构

image.png

  1. public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { 
  3.     /** * 默认容量16 */
  4.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  6.     /** * 最大容量，1 << 30 = 1073741824 */
  7.     static final int MAXIMUM_CAPACITY = 1 << 30;
  9.     /** * 默认加载因子，是决定存储容量扩容的关键指标，计算公式： size/总容量 */
  10.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
  12.     /** * 小于这个值无法使用红黑树，HashMap容量不推荐为奇数，比这个数小后树退化为数组 * 红黑树扩展时也参考这个属性 */
  13.     static final int TREEIFY_THRESHOLD = 8;
  15.     /** * 容量小于这个值红黑树将退化为数组存储 */
  16.     static final int UNTREEIFY_THRESHOLD = 6;
  18.     /** * 将数组转化为红黑树推荐的容量 */
  19.     static final int MIN_TREEIFY_CAPACITY = 64;
  21.     /** *　使用数组存储的数据结构，node节点 */
  22.     static class Node<K,V> implements Map.Entry<K,V> { 
  23.         final int hash;
  24.         final K key;
  25.         V value;
  26.         Node<K,V> next;
  28.         Node(int hash, K key, V value, Node<K,V> next) { 
  29.             this.hash = hash;
  30.             this.key = key;
  31.             this.value = value;
  32.             this.next = next;
  33.         }
  34.     }
  36.     /** * 计算对象的hash值，是hash code分配更均匀，减少冲突几率 */
  37.     static final int hash(Object key) { 
  38.         int h;
  39.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  40.     }
  42.     /** * 计算2的幂次方表容量 * 也就是说表容量只能为： ... 4 8 16 32 64 128 256 ... 1024 ... 1073741824 */
  43.     static final int tableSizeFor(int cap) { 
  44.         int n = cap - 1;
  45.         n |= n >>> 1;
  46.         n |= n >>> 2;
  47.         n |= n >>> 4;
  48.         n |= n >>> 8;
  49.         n |= n >>> 16;
  50.         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  51.     }
  53.     /* ---------------- Fields -------------- */
  55.     /** * 数组存储结构，默认第一次使用时会分配空间 */
  56.     transient Node<K,V>[] table;
  58.     /** * 键值对数量 */
  59.     transient int size;
  61.     /** * 对table修改的次数，调整table时改变 —— rehash、remove、add等操作 * 用来判断在读取操作过程中是否出现table修改 */
  62.     transient int modCount;
  64.     /** * 扩容时的临界值，计算为 capacity*loadFactor */
  65.     int threshold;
  67.     /** * 加载因子, 默认0.75 */
  68.     final float loadFactor;
  70.     /* ---------------- Public operations -------------- */
  72.     /** * 默认构造函数，table容量为16 */
  73.     public HashMap() { 
  74.         this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
  75.     }
  77.     /** * 获取存储键值对数量 */
  78.     public int size() { 
  79.         return size;
  80.     }
  82.     /** * 判空 */
  83.     public boolean isEmpty() { 
  84.         return size == 0;
  85.     }
  87.     /** * 通过key获取value * 下面的getNode是核心方法。 */
  88.     public V get(Object key) { 
  89.         Node<K,V> e;
  90.         return (e = getNode(hash(key), key)) == null ? null : e.value;
  91.     }
  93.     /** * 获取操作 */
  94.     final Node<K,V> getNode(int hash, Object key) { 
  95.         Node<K,V>[] tab;   
  96.         Node<K,V> first, e; 
  97.         int n; // n table长度
  98.         K k;
  100.         if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { 
  101.             if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
  102.                 return first;
  103.             if ((e = first.next) != null) { 
  104.                 // 根据存储结构来获取数据
  106.                 // 红黑树，调用getTreeNode
  107.                 if (first instanceof TreeNode)
  108.                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  110.                 // 遍历链表
  111.                 do { 
  112.                     //较key查询value
  113.                     if (e.hash == hash &&
  114.                         ((k = e.key) == key || (key != null && key.equals(k))))
  115.                         return e;
  116.                 } while ((e = e.next) != null);
  117.             }
  118.         }
  119.         return null;
  120.     }
  122.     /** * 添加数据 */
  123.     public V put(K key, V value) { 
  124.         return putVal(hash(key), key, value, false, true);
  125.     }
  127.     /** * Implements Map.put and related methods. * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. */
  128.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  129.                    boolean evict) { 
  130.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  132.         // table未初始化会执行
  133.         if ((tab = table) == null || (n = tab.length) == 0)
  134.             n = (tab = resize()).length;
  136.         // 存放值
  137.         if ((p = tab[i = (n - 1) & hash]) == null)// 判断通过hash计算出的位置是否有值
  138.             // 没有就在该位置（i）创建一个node并赋值
  139.             tab[i] = newNode(hash, key, value, null);
  140.         else { // 这里时计算出的位置有值存在
  141.             Node<K,V> e; K k;
  143.             if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
  144.                 // 判断hash值、key相同，认为
  145.                 e = p;
  146.             else if (p instanceof TreeNode)
  147.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  148.             else { 
  149.                 // 遍历哈希桶
  150.                 for (int binCount = 0; ; ++binCount) { 
  151.                     // 遍历到桶最后一个元素(链表最后一个元素)
  152.                     if ((e = p.next) == null) { 
  153.                         // 添加元素
  154.                         p.next = newNode(hash, key, value, null);
  155.                         // 判断，只有哈希桶至少为8个的时候才进行树化，TREEIFY_THRESHOLD默认为8
  156.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  157.                             treeifyBin(tab, hash);
  158.                         break;
  159.                     }
  160.                     // 判断键值是否相同
  161.                     if (e.hash == hash &&
  162.                         ((k = e.key) == key || (key != null && key.equals(k))))
  163.                         break;
  164.                     // 下一个元素 
  165.                     p = e;
  166.                 }
  167.             }
  169.             // 更新值
  170.             if (e != null) {  // existing mapping for key —— 存在键的映射
  171.                 V oldValue = e.value;
  172.                 if (!onlyIfAbsent || oldValue == null)
  173.                     e.value = value;
  174.                 afterNodeAccess(e);
  175.                 return oldValue;
  176.             }
  177.         }
  178.         ++modCount;
  179.         // 超出HashMap存放元素的阈值threshold = capacity * loadFactor（0.75）
  180.         if (++size > threshold)
  181.             // 调整Hash存在空间大小
  182.             resize();
  183.         afterNodeInsertion(evict);
  184.         return null;
  185.     }
  187.     /** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */
  188.     final Node<K,V>[] resize() { 
  189.         Node<K,V>[] oldTab = table;
  190.         // 旧容量，为哈希桶长度
  191.         int oldCap = (oldTab == null) ? 0 : oldTab.length;
  192.         int oldThr = threshold;
  193.         int newCap, newThr = 0;
  194.         // 这个if用来保证HashMap阈值threshold不超限
  195.         if (oldCap > 0) { 
  196.             // 判断是否超出最大容量，到最大容量不再扩容
  197.             if (oldCap >= MAXIMUM_CAPACITY) { 
  198.                 // 阈值设置整型最大值
  199.                 threshold = Integer.MAX_VALUE;
  200.                 // 返回并不再调整大小
  201.                 return oldTab;
  202.             }
  203.             // 在容量范围内
  204.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
  205.                 newThr = oldThr << 1; // double threshold 为原先的两倍
  206.         }
  207.         else if (oldThr > 0) // initial capacity was placed in threshold
  208.             newCap = oldThr;
  209.         else {                // zero initial threshold signifies using defaults
  210.             newCap = DEFAULT_INITIAL_CAPACITY;
  211.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  212.         }
  214.         // 计算加载因子，设置新的阈值 阈值=新容量*加载因子
  215.         if (newThr == 0) { 
  216.             float ft = (float)newCap * loadFactor;
  217.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  218.                       (int)ft : Integer.MAX_VALUE);
  219.         }
  220.         threshold = newThr;
  221.         // 新的哈希桶
  222.         @SuppressWarnings({ "rawtypes","unchecked"})
  223.         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  224.         table = newTab;
  225.         // 将旧桶的元素更新到新桶
  226.         if (oldTab != null) { 
  227.             for (int j = 0; j < oldCap; ++j) { 
  228.                 Node<K,V> e;
  229.                 if ((e = oldTab[j]) != null) { 
  230.                     oldTab[j] = null;
  231.                     if (e.next == null)
  232.                         // 旧桶中的值移动到新桶
  233.                         newTab[e.hash & (newCap - 1)] = e;
  234.                     else if (e instanceof TreeNode)
  235.                         // 执行红黑树操作
  236.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  237.                     else {  // preserve order - 翻转顺序
  238.                         Node<K,V> loHead = null, loTail = null;
  239.                         Node<K,V> hiHead = null, hiTail = null;
  240.                         Node<K,V> next;
  241.                         do { 
  242.                             next = e.next;
  243.                             if ((e.hash & oldCap) == 0) { 
  244.                                 if (loTail == null)
  245.                                     loHead = e;
  246.                                 else
  247.                                     loTail.next = e;
  248.                                 loTail = e;
  249.                             }
  250.                             else { 
  251.                                 if (hiTail == null)
  252.                                     hiHead = e;
  253.                                 else
  254.                                     hiTail.next = e;
  255.                                 hiTail = e;
  256.                             }
  257.                         } while ((e = next) != null);
  258.                         if (loTail != null) { 
  259.                             loTail.next = null;
  260.                             newTab[j] = loHead;
  261.                         }
  262.                         if (hiTail != null) { 
  263.                             hiTail.next = null;
  264.                             newTab[j + oldCap] = hiHead;
  265.                         }
  266.                     }
  267.                 }
  268.             }
  269.         }
  270.         return newTab;
  271.     }
  273.     /** * 树化方法 * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */
  274.     final void treeifyBin(Node<K,V>[] tab, int hash) { 
  275.         int n, index; Node<K,V> e;
  276.         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  277.             resize();
  278.         else if ((e = tab[index = (n - 1) & hash]) != null) { 
  279.             TreeNode<K,V> hd = null, tl = null;
  280.             do { 
  281.                 TreeNode<K,V> p = replacementTreeNode(e, null);
  282.                 if (tl == null)
  283.                     hd = p;
  284.                 else { 
  285.                     p.prev = tl;
  286.                     tl.next = p;
  287.                 }
  288.                 tl = p;
  289.             } while ((e = e.next) != null);
  290.             if ((tab[index] = hd) != null)
  291.                 hd.treeify(tab);
  292.         }
  293.     }
  295.     /* ------------------------------------------------------------ */
  296.     // Tree bins
  298.     /** * 红黑树 * * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn * extends Node) so can be used as extension of either regular or * linked node. */
  299.     static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
  300.         TreeNode<K,V> parent;  // red-black tree links
  301.         TreeNode<K,V> left;
  302.         TreeNode<K,V> right;
  303.         TreeNode<K,V> prev;    // needed to unlink next upon deletion
  304.         boolean red;
  305.         TreeNode(int hash, K key, V val, Node<K,V> next) { 
  306.             super(hash, key, val, next);
  307.         }
  308.     }
  309. }

(完)

文章同步我的个人博客：https://www.elltor.com/archives/106.html

发表评论

表情：
评论列表 （有 0 条评论，553人围观）

还没有评论，来说两句吧...

相关阅读

    相关 深入理解Java集合框架性能问题

    Java集合框架是Java编程中用于存储和操作数据的工具包。在使用过程中，可能会遇到一些性能问题，以下是一些常见的理解和解决策略： 1. **数据量过大**：如果一个集合包含

    怼烎@怼烎@/ 0 赞/ 151 阅读