1.容器

Java中提供了一套完整的容器存储体系来供开发人员进行多种类型对象的存储需求。

1.容器体系

image.png
Java中的容器体系为两大部分：Collection集合体系、Map容器体系
Collection接口：
List接口：Vector、ArrayList、LinkedList
Queue接口：
Set接口：TreeSet、HashSet
Map接口：
HashTable、HashMap、TreeMap

2.四者区别

List（顺序）：元素存储有序、可重复；
Queue（队列）：元素存储有序、可重复；
Set（去重）：元素存储无序、不可重复；
Map（映射）：元素存储无序、key-value均不可重复、key只能存在单个null值。
注意点：
无序性：无序性指的不是随机性、而是说底层不是按照数组索引的方式进行存储，是由Hash散列值决定
唯一性：通过元素的equals()和hashcode()两者一同决定。

3.迭代器

任何容器，都必须提供某种插入元素后可以取出的方法。不同的容器底层具有不同的实现，需要提供各自的方法进行操作。存在的问题是对于之间写过的代码无法重用于新的容器。
迭代器（是一种设计模式）：将上层容器的操作与底层的具体实现解耦。迭代器中提供了hasNext()、next()方法来进行通用的容器操作。

  1. public class Demo {
  3.     public static void main(String[] args) {
  4.         Collection collection = new ArrayList();
  5.         collection.add("Java");
  6.         collection.add("Python");
  8.         // 获取迭代器进行遍历
  9.         Iterator iterator = collection.iterator();
  10.         while (iterator.hasNext()){
  11.             System.out.println(iterator.next());
  12.         }
  13.     }
  14. }

2.List

1.体系&特点

image.png
体系：List接口下提供了Vector、ArrayList、LinkedList三种子类实现
特点：List接口中，元素存储有序、可重复

2.Vector

Vector是一个较为古老的List容器、是List接口体系中唯一一个线程安全的容器、底层为Object[]数组。
image.png

3.ArrayList

ArrayList是List接口体系中最为常用的数组容器、是线程不安全的，底层为Object[]数组。
image.png
image.png

4.ArrayList-扩容机制

1.ArrayList中提供了三种构造方式
空参构造：不给定初始容量、在初始化创建时，底层指定容量为0；
有参构造：给定初始化容量、在初始化创建时，底层直接赋值该合法容量。

  1.     /**
  2.      * 默认容量大小
  3.      */
  4.     private static final int DEFAULT_CAPACITY = 10;
  6.     /**
  7.      * 空元素数组
  8.      */
  9.     private static final Object[] EMPTY_ELEMENTDATA = {};
  11.     /**
  12.      * 默认容量空元素数组
  13.      */
  14.     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  16.     /**
  17.      * Object元素数组
  18.      */
  19.     transient Object[] elementData; // non-private to simplify nested class access
  21.     /**
  22.      * 数组元素个数
  23.      */
  24.     private int size;
  26.     /**
  27.      * 空参构造
  28.      */
  29.     public ArrayList() {
  30.         // 空参构造，赋值空数组
  31.         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  32.     }
  34.     /**
  35.      * 有参构造
  36.      */
  37.     public ArrayList(int initialCapacity) {
  38.         if (initialCapacity > 0) {
  39.             // 合法，则直接指定该合法容量
  40.             this.elementData = new Object[initialCapacity];
  41.         } else if (initialCapacity == 0) {
  42.             // 为0，则赋值空数组
  43.             this.elementData = EMPTY_ELEMENTDATA;
  44.         } else {
  45.             // 不合法，抛出异常
  46.             throw new IllegalArgumentException("Illegal Capacity: "+
  47.                                                initialCapacity);
  48.         }
  49.     }
  51.     /**
  52.      * Constructs a list containing the elements of the specified
  53.      * collection, in the order they are returned by the collection's
  54.      * iterator.
  55.      *
  56.      * @param c the collection whose elements are to be placed into this list
  57.      * @throws NullPointerException if the specified collection is null
  58.      */
  59.     public ArrayList(Collection<? extends E> c) {
  60.         elementData = c.toArray();
  61.         if ((size = elementData.length) != 0) {
  62.             // c.toArray might (incorrectly) not return Object[] (see 6260652)
  63.             if (elementData.getClass() != Object[].class)
  64.                 elementData = Arrays.copyOf(elementData, size, Object[].class);
  65.         } else {
  66.             // replace with empty array.
  67.             this.elementData = EMPTY_ELEMENTDATA;
  68.         }
  69.     }
  71.     public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
  72.         @SuppressWarnings("unchecked")
  73.         T[] copy = ((Object)newType == (Object)Object[].class)
  74.             ? (T[]) new Object[newLength]
  75.             : (T[]) Array.newInstance(newType.getComponentType(), newLength);
  76.         System.arraycopy(original, 0, copy, 0,
  77.                          Math.min(original.length, newLength));
  78.         return copy;
  79.     }

2.ArrayList添加元素操作
a.add()：该方法中将size+1后调用ensureCapacityInternal()确保容量足够；然后将元素加入elementData[]元素数组中。
b.ensureCapacityInternal()方法中会根据构造器容量初始化，赋值minCapacity最小容量。
如果elementData[]为空，则最小容量初始化为10，然后再次调用ensureExplicitCapacity(minCapacity)确保第一次初始化后容量是否足够；
如果elementData[]不为空，则直接调用ensureExplicitCapacity(minCapacity)确保第一次初始化容量足够。如果minCapacity（增加元素后的大小） > elementData[]（提供的容量大小）则调用grow()扩容。
c.grow()方法中会在第一次舒适化容量的基础之上，通过 >> 1（有符号右移一位）来进行扩容，也就是在原有
容量基础之上增加1/2。扩容到原有的1.5倍。
d.每次扩容之后，会调用Arrays.copyOf()方法将旧数组复制到新数组中。而copyOf()方法中又调用了System.arraycopy()方法进行数组复制。
注意点：由于ArrayList中每进行一次数组扩容，则需要进行数组的拷贝动作。所以，建议在初始化时就指定容量大小，以减少复制次数，提高系统性能。

  2.     public boolean add(E e) {
  3.         // size + 1 后确保容量是否足够
  4.         ensureCapacityInternal(size + 1);
  5.         // 赋值元素到Object[]中
  6.         elementData[size++] = e;
  7.         return true;
  8.     }
  10.     /**
  11.      * size + 1 后确保容量足够
  12.      */
  13.     private void ensureCapacityInternal(int minCapacity) {
  14.         // 如果数组为空，则直接初始化默认容量为10
  15.         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  16.             // 最小容量 = Max（ 默认容量10， 新增元素后的最小容量=1）
  17.             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  18.         }
  20.         // 再次确保容量是否足够
  21.         ensureExplicitCapacity(minCapacity);
  22.     }
  24.     private void ensureExplicitCapacity(int minCapacity) {
  25.         modCount++;
  27.         // 需要的最小容量，能提供的容量  > 0则说明不够，需要进行扩容
  28.         if (minCapacity - elementData.length > 0)
  29.             grow(minCapacity);
  30.     }    
  32.     /**
  33.      * grow()方法是ArrayList中用来进行扩容的方法
  34.      *
  35.      * @param minCapacity the desired minimum capacity
  36.      */
  37.     private void grow(int minCapacity) {
  38.         // 获取能提供的容量大小
  39.         int oldCapacity = elementData.length;
  41.         // 第一次扩容：old向右移动一位，相当于old / 2 = 0.5；再原有容量的基础上增加1/2 = 1.5倍 (奇偶不同)
  42.         int newCapacity = oldCapacity + (oldCapacity >> 1);
  43.         if (newCapacity - minCapacity < 0)
  44.             newCapacity = minCapacity;
  45.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  46.             newCapacity = hugeCapacity(minCapacity);
  47.         // minCapacity is usually close to size, so this is a win:
  48.         elementData = Arrays.copyOf(elementData, newCapacity);
  49.     }
  51.     private static int hugeCapacity(int minCapacity) {
  52.         if (minCapacity < 0) // overflow
  53.             throw new OutOfMemoryError();
  54.         return (minCapacity > MAX_ARRAY_SIZE) ?
  55.             Integer.MAX_VALUE :
  56.             MAX_ARRAY_SIZE;
  57.     }

5.Vector&ArrayList差异

ArrayList和Vector之间最大的区别就是Vector是线程安全的。

6.LinkedList

LinkedList也是List接口体系中的一个子类实现，也是线程不安全容器。底层为双向链表。

7.ArrayList&LinkedList差异

访问操作：ArrayList支持随机访问、且改查快速；LinkedList不支持随机访问，且增删快速。
线程安全：两者均为线程不安全性容器。
底层机制：ArrayList底层为Object[]数组；LinkedList在JDK6之前为循环链表、之后为双向链表。
空间占用：ArrayList需要预留空间；LinkedList需要空间存储指针。

3.Set

1.体系&特点

image.png
特点：元素存储无序、不重复。

2.HashSet

HashSet是Set接口下的一个子类实现，也是线程不安全的，底层由HashMap[数组+链表]实现。

3.HashSet如何去重

1、HashSet调用add()时，会先通过元素的hashcode()计算出hash索引（元素在table中所处的位置）
2、当前位置无元素，则直接插入；有元素，则比较hashcode();
3、hashcode()不同，则认为不重复，进行插入；hashcode()相同，则再比较equals()，相同则直接覆盖。

4.Set中元素顺序

不同的Set底层实现具有不同的顺序保障机制
1、HashSet中，通过hashCode()来保障元素的口顺序；
2、TreeSet中，实现了Comparable接口，通过compareTo()方法对元素比较来保障元素顺序；
3、LinkedhashSet中，通过元素插入来保障元素顺序。

  1. // hashCode() 异或 (hashCode() 无符号右移16位)
  2. int hash = key.hashcode() ^ (key.hashCode() >>> 16)

4.Map

1.体系&特点

image.png
特点：元素存储无序、key-value双列存储、key中只能存在一个null值，value中可以重复。
实际存储：key-value实际上是存储在hsahMap中的一个静态内部类Node(hash, key, value, next)中。

2.HashMap

HashMap也是Map接口下的一个子类实现，也是线程不安全的容器存储。
底层机制：
JDK7~哈希表[数组 + 链表]
JDK8~哈希表[数组 + 链表] + 红黑树

3.HashMap-扩容机制

散列计算：
HashMap中通过(n - 1) & hash来计算散列位置。在JDK7和JDK8中具有不同的一个实现
JDK7：JDK7中HashMap的底层实现为 [数组 + 链表]
计算Hash方式：该hash()方法中进行了四次扰动，性能较为低效。

  1. static int hash(int h) {
  2.     h ^= (h >>> 20) ^ (h >>> 12);
  3.     return h ^ (h >>> 7) ^ (h >>> 4);
  4. }
  1. **JDK8：**JDK8中HashMap的底层实现为[数组 + 链表] + 红黑树<br />计算Hash方式：该hash()方法中进行了两次扰动，性能有了很大提升。
  1.     static final int hash(Object key) {
  2.         int h;
  3.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  4.     }

扩容机制流程图：
image.png
put方法扩容：
相关参数：

  1.     /**
  2.      * 加载因子
  3.      */
  4.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
  6.     /**
  7.      * 单个链表结点长度
  8.      */
  9.     static final int TREEIFY_THRESHOLD = 8;
  11.     /**
  12.      * The bin count threshold for untreeifying a (split) bin during a
  13.      * resize operation. Should be less than TREEIFY_THRESHOLD, and at
  14.      * most 6 to mesh with shrinkage detection under removal.
  15.      */
  16.     static final int UNTREEIFY_THRESHOLD = 6;
  18.     /**
  19.      * 哈希表中的结点总数大小
  20.      */
  21.     static final int MIN_TREEIFY_CAPACITY = 64;
  23.     /**
  24.      * 最大容量，2的幂次方 2^30
  25.      */
  26.     static final int MAXIMUM_CAPACITY = 1 << 30;
  28.     /**
  29.      * 默认初始容量，2的幂次方 = 16
  30.      */
  31.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  1. **构造方法：**
  1.     /**
  2.      * 空参构造：默认初始容量16，加载因子0.75
  3.      */
  4.     public HashMap() {
  5.         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  6.     }
  8.     /**
  9.      * 有参构造：指定初始容量、加载因子还是0.75
  10.      */
  11.     public HashMap(int initialCapacity) {
  12.         this(initialCapacity, DEFAULT_LOAD_FACTOR);
  13.     }
  15.     /**
  16.      * 供有参构造进行调用
  17.      */
  18.     public HashMap(int initialCapacity, float loadFactor) {
  19.         // 非法容量：抛出异常
  20.         if (initialCapacity < 0)
  21.             throw new IllegalArgumentException("Illegal initial capacity: " +
  22.                                                initialCapacity);
  23.         // 超出最大容量：赋值最大容量
  24.         if (initialCapacity > MAXIMUM_CAPACITY)
  25.             initialCapacity = MAXIMUM_CAPACITY;
  26.         // 加载因子
  27.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
  28.             throw new IllegalArgumentException("Illegal load factor: " +
  29.                                                loadFactor);
  30.         this.loadFactor = loadFactor;
  31.         this.threshold = tableSizeFor(initialCapacity);
  32.     }
  1. **添加元素：**
  1.     /**
  2.      * put方法添加元素：先调用hash()方法计算key所在的hash索引
  3.      */
  4.     public V put(K key, V value) {
  5.         return putVal(hash(key), key, value, false, true);
  6.     }
  8.     /**
  9.      * key == null ？ 直接返回0 ： （哈希 异或 哈希无符号右移16位）
  10.      *         目的是为了降低hash碰撞的情况
  11.      */
  12.     static final int hash(Object key) {
  13.         int h;
  14.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  15.     }
  17.     /**
  18.      * 3、添加元素方法：计算出的hash索引、key、value(为了双列存储)
  19.      */
  20.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  21.                    boolean evict) {
  22.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  23.         // 1.空参构造：resize()中初始化容量为16
  24.         if ((tab = table) == null || (n = tab.length) == 0)
  25.             n = (tab = resize()).length;
  27.         // 2.计算hash索引：获取元素插入的数组下标
  28.         if ((p = tab[i = (n - 1) & hash]) == null)
  29.             // 为空，则直接加入
  30.             tab[i] = newNode(hash, key, value, null);
  31.         else {
  32.             Node<K,V> e; K k;
  34.             // key相同：hashCode()、equals()相同，则直接覆盖旧元素
  35.             if (p.hash == hash &&
  36.                 ((k = p.key) == key || (key != null && key.equals(k))))
  37.                 e = p;
  38.             // 3.key不同：判断是链表还是红黑树
  39.             else if (p instanceof TreeNode)
  40.                 // 红黑树加入法
  41.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  42.             else {
  43.                 // 链表循环法
  44.                 for (int binCount = 0; ; ++binCount) {
  45.                     if ((e = p.next) == null) {
  46.                         p.next = newNode(hash, key, value, null);
  47.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  48.                             treeifyBin(tab, hash);
  49.                         break;
  50.                     }
  51.                     if (e.hash == hash &&
  52.                         ((k = e.key) == key || (key != null && key.equals(k))))
  53.                         break;
  54.                     p = e;
  55.                 }
  56.             }
  57.             if (e != null) { // existing mapping for key
  58.                 V oldValue = e.value;
  59.                 if (!onlyIfAbsent || oldValue == null)
  60.                     e.value = value;
  61.                 afterNodeAccess(e);
  62.                 return oldValue;
  63.             }
  64.         }
  65.         ++modCount;
  66.         // threshold为扩容阈值
  67.         if (++size > threshold)
  68.             resize();
  69.         afterNodeInsertion(evict);
  70.         return null;
  71.     }
  73.     /**
  74.      * 4、扩容方法：初始容量扩容为16
  75.      */
  76.     final Node<K,V>[] resize() {
  77.         Node<K,V>[] oldTab = table;
  78.         int oldCap = (oldTab == null) ? 0 : oldTab.length;
  79.         int oldThr = threshold;
  80.         int newCap, newThr = 0;
  81.         if (oldCap > 0) {
  82.             if (oldCap >= MAXIMUM_CAPACITY) {
  83.                 threshold = Integer.MAX_VALUE;
  84.                 return oldTab;
  85.             }
  86.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  87.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
  88.                 newThr = oldThr << 1; // double threshold
  89.         }
  90.         else if (oldThr > 0) // initial capacity was placed in threshold
  91.             newCap = oldThr;
  92.         else {               // zero initial threshold signifies using defaults
  93.             // 初始化容量为16
  94.             newCap = DEFAULT_INITIAL_CAPACITY;
  95.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  96.         }
  97.         if (newThr == 0) {
  98.             float ft = (float)newCap * loadFactor;
  99.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  100.                       (int)ft : Integer.MAX_VALUE);
  101.         }
  102.         threshold = newThr;
  103.         @SuppressWarnings({"rawtypes","unchecked"})
  104.             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  105.         table = newTab;
  106.         if (oldTab != null) {
  107.             for (int j = 0; j < oldCap; ++j) {
  108.                 Node<K,V> e;
  109.                 if ((e = oldTab[j]) != null) {
  110.                     oldTab[j] = null;
  111.                     if (e.next == null)
  112.                         newTab[e.hash & (newCap - 1)] = e;
  113.                     else if (e instanceof TreeNode)
  114.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  115.                     else { // preserve order
  116.                         Node<K,V> loHead = null, loTail = null;
  117.                         Node<K,V> hiHead = null, hiTail = null;
  118.                         Node<K,V> next;
  119.                         do {
  120.                             next = e.next;
  121.                             if ((e.hash & oldCap) == 0) {
  122.                                 if (loTail == null)
  123.                                     loHead = e;
  124.                                 else
  125.                                     loTail.next = e;
  126.                                 loTail = e;
  127.                             }
  128.                             else {
  129.                                 if (hiTail == null)
  130.                                     hiHead = e;
  131.                                 else
  132.                                     hiTail.next = e;
  133.                                 hiTail = e;
  134.                             }
  135.                         } while ((e = next) != null);
  136.                         if (loTail != null) {
  137.                             loTail.next = null;
  138.                             newTab[j] = loHead;
  139.                         }
  140.                         if (hiTail != null) {
  141.                             hiTail.next = null;
  142.                             newTab[j + oldCap] = hiHead;
  143.                         }
  144.                     }
  145.                 }
  146.             }
  147.         }
  148.         return newTab;
  149.     }
  1. **扩容总结：**<br />1.根据构造初始化判断table是否为空，空参构造则直接初始化扩容为16，否则初始化为合法容量；<br />2.添加元素，通过hashCode()计算hash索引位置；<br />3.根据hash索引，判断索引处是否为空；为空，则直接加入；<br />4.不为空，判断索引处key是否相同；相同，则直接覆盖；<br />5.不相同，判断是红黑树、还是链表；<br />6.红黑树则按照红黑树插入；链表则对链表循环，然后插入。<br />7.后续插入扩容，**容量 * 加载因子 = 阈值，**达到阈值则进行扩容（初始为12）。<br />**8.当单条链表结点大于8，且整个table总结点数大于64，则进行树化。**<br />**9.单链表结点大于8，但table总结点数小于64，则进行数组扩容，不进行树化。**<br />**rehash问题：**<br />每次扩容时，都需要重新分配hash、也就是rehash()。<br />HashMap扩容，每次都是之前的两倍。通过(n -1) & hash时，只是比之前多了一个**bit位**。原结点位置要么是原先的索引位置，要么是“原位置 + 旧容量”。<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/27397677/1653962078073-4732ba6d-e291-4f0d-a932-176d8595c84f.png#clientId=u85a0d0c9-6fcc-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=u51561b84&margin=%5Bobject%20Object%5D&name=image.png&originHeight=568&originWidth=1296&originalType=url&ratio=1&rotation=0&showTitle=false&size=131406&status=done&style=none&taskId=uff3449a8-3a44-4820-8e6a-6d20763dc35&title=)<br />这样的设计，在进行扩容重新分配时，则只需要查看新增bit为是1，还是0即可快速重新分配。

4.HashMap-7&8差异

JDK7：
底层~数组+链表；新增元素~采用头插法（存在死循环）；扩容机制~插入前扩容、hash需要四次扰动；

  1. static int hash(int h) {
  2.     // This function ensures that hashCodes that differ only by
  3.     // constant multiples at each bit position have a bounded
  4.     // number of collisions (approximately 8 at default load factor).
  6.     h ^= (h >>> 20) ^ (h >>> 12);
  7.     return h ^ (h >>> 7) ^ (h >>> 4);
  8. }

JDK8：
底层~数组+链表+红黑树；新增元素~采用尾插法；扩容机制~插入后扩容、hash需要两次扰动；

  1.     static final int hash(Object key) {
  2.         int h;
  3.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  4.     }

5.负载因子为何0.75f？

image.png
作用：负载因子决定了HashMap中数据密度。是一种时间与空间的折衷。
过大：负载因子过大，则会导致数据密度过大、单表链表更长、插入&查询元素需要比较的次数更多；
节省了空间、浪费了时间。
过小：负载因子过小，则会导致数据密度过小、单条链表更短、插入&查询元素需要比较的次数更少；
节省了时间、浪费了空间。

6.树化为何选择红黑树？

二叉查找树、红黑平衡二叉查找树的一种选择问题。
二叉查找树在某种情况下也是一种线性查找，这种线性查找其实和链表是没有区别的。
红黑树是一种平衡二叉树，查询时采用二分查找法，查询更加快速高效。

7.红黑树？

1、根结点总是黑色、其他结点不是黑色就是红色；
2、红结点的子节点必定是黑色，反之不成立；
3、叶子结点均为黑色的空结点；
4、根结点到叶子结点的每条路径，必须包含相同数量的黑色结点。

8.HashMap-数组总为2的幂次方？

HashMap中需要通过取模获取余数运算来降低Hash冲突、采用2的幂次方会更加方便进行取模运算，降低了hash冲突、元素存取更加高效可用。

9.HashTable&HashMap差异？

操作效率：HashMap效率更到；HashTable由于线程安全，则效率较低。
线程安全：HashTable线程安全，通过synchronized锁方法进行修饰。
Null值：HashTable中的key-value均不允许为Null。
底层结构：HashTable中无树化机制。
扩容机制：无初始容量，则HashTable初始值为11。

5.线程安全容器

经典案例：单词统计中，多个线程同时进行统计，使用HashMap存储，结果都不一致。

1.ConHashMap-体系&特点

体系：ConcurrentHashMap implements ConcurrentMap接口 extends Map接口
特点：并发安全容器，底层采用了Synchronized锁对象来保障线程安全。

  1.     final V putVal(K key, V value, boolean onlyIfAbsent) {
  2.         if (key == null || value == null) throw new NullPointerException();
  3.         int hash = spread(key.hashCode());
  4.         int binCount = 0;
  5.         for (Node<K,V>[] tab = table;;) {
  6.             Node<K,V> f; int n, i, fh;
  7.             if (tab == null || (n = tab.length) == 0)
  8.                 tab = initTable();
  9.             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  10.                 if (casTabAt(tab, i, null,
  11.                              new Node<K,V>(hash, key, value, null)))
  12.                     break;                   // no lock when adding to empty bin
  13.             }
  14.             else if ((fh = f.hash) == MOVED)
  15.                 tab = helpTransfer(tab, f);
  16.             else {
  17.                 V oldVal = null;
  18.                 // 此处，添加了锁对象
  19.                 synchronized (f) {
  20.                     if (tabAt(tab, i) == f) {
  21.                         if (fh >= 0) {
  22.                             binCount = 1;
  23.                             for (Node<K,V> e = f;; ++binCount) {
  24.                                 K ek;
  25.                                 if (e.hash == hash &&
  26.                                     ((ek = e.key) == key ||
  27.                                      (ek != null && key.equals(ek)))) {
  28.                                     oldVal = e.val;
  29.                                     if (!onlyIfAbsent)
  30.                                         e.val = value;
  31.                                     break;
  32.                                 }
  33.                                 Node<K,V> pred = e;
  34.                                 if ((e = e.next) == null) {
  35.                                     pred.next = new Node<K,V>(hash, key,
  36.                                                               value, null);
  37.                                     break;
  38.                                 }
  39.                             }
  40.                         }
  41.                         else if (f instanceof TreeBin) {
  42.                             Node<K,V> p;
  43.                             binCount = 2;
  44.                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  45.                                                            value)) != null) {
  46.                                 oldVal = p.val;
  47.                                 if (!onlyIfAbsent)
  48.                                     p.val = value;
  49.                             }
  50.                         }
  51.                     }
  52.                 }
  53.                 if (binCount != 0) {
  54.                     if (binCount >= TREEIFY_THRESHOLD)
  55.                         treeifyBin(tab, i);
  56.                     if (oldVal != null)
  57.                         return oldVal;
  58.                     break;
  59.                 }
  60.             }
  61.         }
  62.         addCount(1L, binCount);
  63.         return null;
  64.     }

2.HashMap循环链表问题？

JDK7中采用了头插法插入元素，头插法中在并发情况下扩容重新分配时，则会出现循环队列问题。
resize()源码

  1. void resize(int newCapacity) {
  2.         Entry[] oldTable = table;
  3.         int oldCapacity = oldTable.length;
  4.         if (oldCapacity == MAXIMUM_CAPACITY) {
  5.             threshold = Integer.MAX_VALUE;
  6.             return;
  7.         }
  9.         // 创建新数组进行扩容
  10.         Entry[] newTable = new Entry[newCapacity];
  11.         transfer(newTable, initHashSeedAsNeeded(newCapacity));
  12.         table = newTable;
  13.         threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
  14.     }
  16. /**
  17.      * Transfers all entries from current table to newTable.
  18.      */
  19.     void transfer(Entry[] newTable, boolean rehash) {
  20.         int newCapacity = newTable.length;
  21.         for (Entry<K,V> e : table) {
  22.             while(null != e) {
  23.                 Entry<K,V> next = e.next;
  24.                 if (rehash) {
  25.                     e.hash = null == e.key ? 0 : hash(e.key);
  26.                 }
  27.                 int i = indexFor(e.hash, newCapacity);
  28.                 e.next = newTable[i];
  29.                 newTable[i] = e;
  30.                 e = next;
  31.             }
  32.         }
  33.     }

先创建新数组、然后按照链表顺序，逐条链表赋值到新数组中。在重新计算链表结点并进行修改的过程中会出现循环链表问题。
过程演示：
1、初始插入元素：顺序为A->B->C
image.png
2、线程T1、T2并发进行扩容。T1、T2同时指向A结点，.next均指向下一个结点B。
image.png
3、此时，线程T2由于阻塞，停止扩容；T1正常进行扩容。
T1扩容之后，顺序为C->B->A
此时：T1中，顺序是由C->B->A的。但在T2中，顺序是A->B的，是相反的，则A和B之间就出现了循环。
image.png

3.ConHashMap-底层实现

Segments数组 + HashEntry数组+链表，采用分段锁保证线程安全。
默认Segments的个数为16.
Java容器 - 图13