面试题-集合

Collection接口下有哪些实现？

为什么set是无序的，list是有序的

这里的无序和有序，是根据添加到集合中元素的顺序，而不是对数据进行排序。

因为set在添加元素的时候，计算元素的hash值，进行存储。所以set集合中的元素不能有重复，也不能保证内部存储是按元素添加的顺序而存储的。

list是按照添加的顺序进行输出的，所以为有序。

ArrayList 与 LinkedList 区别?

• 是否保证线程安全：都不是线程安全的

• 底层数据结构：ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构

• 插入和删除是否受元素位置的影响：

  • ArrayList：采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响，add(E e)方法，将指定的元素追加到此列表的末尾，时间复杂度就是 O(1)。要是在指定元素位置插入和删除时，时间复杂度为O(n-i)，因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
  • LinkedList：采用链表存储，如果是在头尾插入或者删除元素，时间复杂度为 O(1)。如果要在指定位置删除和插入时，时间复杂度都为O(n) ，因为需要先移动到指定位置再插入。

• 是否支持快速随机访问：LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

• 内存空间占用：ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

使用场景

（1）如果应用程序对数据有较多的随机访问，ArrayList对象要优于LinkedList对象；、

（2）如果应用程序有更多的插入或者删除操作，较少的随机访问，LinkedList对象要优于ArrayList对象；

（3）不过ArrayList的插入，删除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那么ArrayList只需要移动较少的数据，而LinkedList则需要一直查找到列表尾部，反而耗费较多时间，这时ArrayList就比LinkedList要快。

总结：

我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 LinkedList

HashSet和TreeSet

（1）TreeSet的底层是使用TreeMap实现的。HashSet的底层是使用HashMap实现的。

（2）TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0.HashSet是使用hashCode判断的。

（3）TreeSet 是二叉树实现的，Treeset中的数据是自动排好序的，不允许放入null值。HashSet 是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束。

ArrayList扩容机制

ArrayList扩容的核心方法：

/**
     * ArrayList扩容的核心方法。
     */
    private void grow(int minCapacity) {
        // oldCapacity为旧容量，newCapacity为新容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再检查新容量是否超出了ArrayList所定义的最大容量，
        //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
        //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //比较minCapacity和 MAX_ARRAY_SIZE
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

ArrayList的底层是通过数组实现的，底层创建了长度为10的数组，当容量不够时，则扩容为原来的1.5倍。jdk1.7和1.8中的区别主要是在什么时候初始化，jdk1.7：new时就初始化长度为10的数组，1.8：当在add时才进行初始化，分配长度为10的数组。

在jdk1.8的时候，先创建 一个长度为0的数组，当进行add操作的时候，才进行分配长度为10的数组.看下面的代码:

/**
     * 将指定的元素追加到此列表的末尾。
     */
    public boolean add(E e) {
   //添加元素之前，先调用ensureCapacityInternal方法
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //这里看到ArrayList添加元素的实质就相当于为数组赋值
        elementData[size++] = e;
        return true;
    }

//得到最小扩容量
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
              // 获取默认的容量和传入参数的较大值,(默认的容量为10)
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

//判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        //判断容量是否超出10,因为第一次初始化的时候elementData.length已经为10
        if (minCapacity - elementData.length > 0)
            //调用grow方法进行扩容，调用此方法代表已经开始扩容了
            grow(minCapacity);
    }

上述三段代码描述了这样的事情:

• 首先,当我们进行add第一个元素的时候,elementData.length 为 0 （因为还是一个空的 list）,因为执行了 ensureCapacityInternal() 方法 ，所以 minCapacity 此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。进入该方法时,旧容量为0,右移一位扩容后,也为0,因此第一个if条件成立,所以新容量就为10,此时elementData.length(容量扩容成 10 了。

• 当 add 第 2 个元素时，minCapacity 为 2，此时 e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入 （执行）grow(minCapacity) 方法。
• 直到添加第 11 个元素，minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 方法进行扩容。旧容量为10,新容量为15,第一个if和第二个if都不成立,因此新容量为15.

其中hugeCapacity() 方法:如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。

System.arraycopy()和Arrays.copyOf()`方法

联系：

看两者源代码可以发现 copyOf()内部实际调用了 System.arraycopy() 方法

区别：

arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组。

comparable 和 Comparator 的区别

• comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序
• comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序

定制排序的用法

// 定制排序的用法
        Collections.sort(arrayList, new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

重写 compareTo 方法实现按年龄来排序,并且类中要实现Comparable

/**
     * T重写compareTo方法实现按年龄来排序
     */
    @Override
    public int compareTo(Person o) {
        if (this.age > o.getAge()) {
            return 1;
        }
        if (this.age < o.getAge()) {
            return -1;
        }
        return 0;
    }

hashmap和hashtable的区别

• hashmap不是线程安全的,hashtable是线程安全的
• hashmao的效率比hashtable高
• hashmap的初始容量为16,扩容为原来的2倍,hashtable初始容量为11,扩容为原来的2n+1
• hashmap允许键值为空，但hashtable不允许
• hashmap继承的是AbstratMap类，但hashtable继承的是Dictionary

HashMap和TreeMap的区别

TreeMap可以对map中的key进行排序。

TreeMap不可以有null的key

HashMap的底层是Array，所以HashMap在添加，查找，删除等方法上面速度会非常快。而TreeMap的底层是一个Tree结构，所以速度会比较慢。

另外HashMap因为要保存一个Array，所以会造成空间的浪费，而TreeMap只保存要保持的节点，所以占用的空间比较小。

HashSet 如何检查重复?

当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

在 JDK1.8 中，HashSet的add()方法只是简单的调用了HashMap的put()方法，并且判断了一下返回值以确保是否有重复元素。直接看一下HashSet中的源码：

// Returns: true if this set did not already contain the specified element
// 返回值：当 set 中没有包含 add 的元素时返回真
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

// Returns : previous value, or null if none
// 返回值：如果插入位置没有元素返回null，否则返回上一个元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
...
}

也就是说，在 JDK1.8 中，实际上无论HashSet中是否已经存在了某元素，HashSet都会直接插入，只是会在add()方法的返回值处告诉我们插入前是否存在相同元素。

hashmap底层实现

hashmap线程不安全，效率高，可以存储null的key和value。

HashMap的底层： 数组+链表 （jdk7及之前） 数组+链表+红黑树 （jdk 8）

底层实现：

​ jdk 1.7:在实例化之后，底层创建了长度为16的一维数组Node[]。

​ jdk1.8时，实例化时初始容量为0，当执行put操作时，才扩容到16的一维数组Entry[] table

​ 对于hashmap的put操作：首先对key1计算hash值，此hash值表示在entry中的位置，如果此位置上的数据为空，则直接添加成功。

​ 如果此位置上的数据不为空，说明该位置上存在一个链表，里面包含一个或多个数据，比较key1与他们的hash值

​ 如果key1的hash值与该链表中所有元素的值都不相等，则直接添加成功

​ 如果key1的hash值与链表中已经存在的某一个key2数据的hash值相等，则使用equals方法继续进行比较

​ 如果key1.equas(key2)返回false，则添加成功

​ 否则如果返回true，则将value2替换为value1

在上述添加的过程中，会出现容量不够，扩容问题，

扩容问题：

​ 当超出临界值（初始容量×填充因子=16×0.75=12）时，进行扩容，扩容为原来的2倍，并将原有的数据复制过来。

jdk8 相较于jdk7在底层实现方面的不同：

1. new HashMap():底层没有创建一个长度为16的数组
2. jdk 8底层的数组是：Node[],而非Entry[]
3. 首次调用``put()`方法时，底层创建长度为16的数组
4. jdk7底层结构只有：数组+链表。jdk8中底层结构：数组+链表+红黑树。
   4.1 形成链表时，七上八下（jdk7:新的元素指向旧的元素。jdk8：旧的元素指向新的元素）
   4.2 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所数据改为使用红黑树存储。

为什么jdk8从头插法改变为尾插法

当HashMap达到扩容的条件时候，会把HashMap中的每个元素，重新进行运算Hash值，jdk7通过头插法打入到扩容后的数组中。

解决了头插法在rehash时导致死循环的问题。

扩容时transfer代码如下：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;//这里记做第一步
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];//这里记做第二步
            newTable[i] = e;//这里记做第三步
            e = next;//这里记做第四部
        }
    }
}

如下所示的hashmap, 有两个元素, 它们的key分别是1和3, 假设再增加一个元素时会触发扩容操作

假设线程1扩容时, 执行完transfer()中的Entry<K,V> next = e.next;被挂起, 此时e指向1, next指向3, 如下图所示

假设1和3在新的数组中仍然发生哈希碰撞, 假设线程2完成了扩容, 那么此时哈希表的样子如下图所示
可以发现, 由于使用了头插法, 所以3变成了头结点

回到线程1, e指向的是1, next指向的是3, 继续向下执行
当执行完e.next = newTable[i];便出现了循环链表, 其中,newTable[i]是3

put()方法

1. 如果定位到的数组位置没有元素 就直接插入。
2. 如果定位到的数组位置有元素就和要插入的 key 比较，如果 key 相同就直接覆盖，如果 key 不相同，就判断 p 是否是一个树节点，如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素（处理hash冲突）
    else {
        Node<K,V> e; K k;
        // 判断table[i]中的元素是否与插入的key一样，若相同那就直接使用插入的值p替换掉旧的值e。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
        // 判断插入的是否是红黑树节点
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 不是红黑树节点则说明为链表结点
        else {
            // 在链表最末插入结点
            for (int binCount = 0; ; ++binCount) {
                // 到达链表的尾部
                if ((e = p.next) == null) {
                    // 在尾部插入新结点
                    p.next = newNode(hash, key, value, null);
                    // 结点数量达到阈值(默认为 8 )，执行 treeifyBin 方法
                    // 这个方法会根据 HashMap 数组来决定是否转换为红黑树。
                    // 只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是对数组扩容。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) {
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

get()方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != 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) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

• 首先查找是否与数组的元素相等,如果相等则返回.

• 如果不相等,并且数组中的某个位置不止一个节点,则判断是否是树,如果是树,则调用方法在树中get.

• 如果不是树,则在链表中get.

resize()方法

进行的是扩容操作,会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。

HashMap的遍历方式

• 迭代器EntrySet

  public class HashMapTest {
      public static void main(String[] args) {
          // 创建并赋值 HashMap
          Map<Integer, String> map = new HashMap();
          map.put(1, "Java");
          map.put(2, "JDK");
          map.put(3, "Spring Framework");
          map.put(4, "MyBatis framework");
          map.put(5, "Java中文社群");
          // 遍历
          Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
          while (iterator.hasNext()) {
              Map.Entry<Integer, String> entry = iterator.next();
              System.out.println(entry.getKey());
              System.out.println(entry.getValue());
          }
      }
  }

• 迭代器KeySet

  public class HashMapTest {
      public static void main(String[] args) {
          // 创建并赋值 HashMap
          Map<Integer, String> map = new HashMap();
          map.put(1, "Java");
          map.put(2, "JDK");
          map.put(3, "Spring Framework");
          map.put(4, "MyBatis framework");
          map.put(5, "Java中文社群");
          // 遍历
          Iterator<Integer> iterator = map.keySet().iterator();
          while (iterator.hasNext()) {
              Integer key = iterator.next();
              System.out.println(key);
              System.out.println(map.get(key));
          }
      }
  }

• ForEach EntrySet

  for (Map.Entry<Integer, String> entry : map.entrySet()) {
              System.out.println(entry.getKey());
              System.out.println(entry.getValue());
          }

• ForEach KeySet

  for (Integer key : map.keySet()) {
              System.out.println(key);
              System.out.println(map.get(key));
          }

• Lambda

  // 遍历
          map.forEach((key, value) -> {
              System.out.println(key);
              System.out.println(value);
          });

• Stream API

  // 遍历
          map.entrySet().stream().forEach((entry) -> {
              System.out.println(entry.getKey());
              System.out.println(entry.getValue());
          });

总结:

entrySet 的性能比 keySet 的性能高出了一倍之多，因此我们应该尽量使用 entrySet 来实现 Map 集合的遍历。

HashMap初始化时，构造方法传值为10000会发生扩容么

向 HashMap 中存 10000 条数据，初始化时，构造方法传值 10000，会触发扩容吗?

Map<String,String> map = new HashMap<>(10000);

分析源码

在 HashMap 中，提供了一个指定初始容量的构造方法 HashMap(int initialCapacity)，这个方法再通过 DEFAULT_LOAD_FACTOR 调用 HashMap 另一个构造方法，初始化 loadFactor 为 0.75。

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
  	......
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity); //用来触发扩容的阈值的
}

​ 构造方法初始化了两个成员变量 threshold 和 loadFactor，其中 threshold 就是用来存储触发 HashMap 扩容的阈值，也就是说，当 HashMap 存储的数据量达到 threshold 时，就会触发扩容。
  从改造方法中可以看出，threshold 并没有直接使用传入的 initialCapacity 作为扩容阈值，而是通过 tableSizeFor 方法处理后再赋值给 threshold。

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 : n + 1;
}

tableSizeFor 的作用就是寻找大于 cap 的 2 的整数次方，例如如果传入 10，经过 tableSizeFor 处理后返回 16。

还有一个问题，一直在说 threshold 是触发扩容的阈值，即 (initialCapacity * loadFactor)，但是我们再构造方法中使用 tableSizeFor 初始化 threshold，并没有用到 loadFactor，其实这一步被移交给 resize 方法实现了，因为我们并没有在构造方法中初始化哈希表数组，扩容阈值 threshold = initialCapacity * loadFactor，这一步在 resize 中完成。

因此此题的结果是：

  如果我们从外部传递进来 10000 初始化 initialCapacity ，实际上经过 tableSizeFor 方法处理之后，最终 threshold 就会变成 2 的 14 次幂 16384，再在 resize 方法中乘上负载因子 0.75，实际在不触发扩容的前提下，可存储的数据容量是 12288=(16384 * 0.75)，用来存放 10000 条数据，绰绰有余，所以并不会触发扩容。

CurrentHashMap的实现原理

CurrentHashMap主要是由于HashMap并发下不安全所诞生的，不支持key和value为空值。

大量的使用了，volatile，final，CAS来减少锁竞争对于性能的影响。

（1）在jdk1.7中的底层实现：

ConcurrentHashMap采用了数组+Segment+分段锁的方式实现。而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。

内部结构：

分段锁技术：将数据分成一段一段的存储，然后给每一段数据分配一把锁，这样，当一个线程访问其中一段数据的时候，其他段的数据可以同时被其他线程访问，能够实现真正的并发访问，内部图为：

通过观察上图，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。（第一次定位到在哪个segment，第二次定位到元素在哪个链表。）

优缺点：

• 缺点：hash操作的过程比普通hashmap要长

• 优点：对于写操作时只对所在元素的segment加锁，不影响其他segment。因此可以同时支持segment大小数量的写操作，大大的提高了并发能力

（2）在jdk1.8中的底层实现：

参考了jdk1.8中的hashMap的实现，采用了 数组+链表+红黑树的实现方式来设计。内部采用了大量的CAS操作。

介绍CAS：

CAS是compare and swap的缩写，就是我们所说的比较和交换，cas是一种基于锁的操作，而且是乐观锁，在java中分为乐观锁和悲观锁，其中悲观锁是将资源锁住，等获得锁的线程释放锁之后，下一个线程才能访问，而乐观锁采取一种宽泛的态度，不加锁的方式进行处理，比如：给记录加version来获取数据，性能较悲观锁有很大的提升。

每次进行compareAndSwap方法时，需要cas有3个参数

内存地址V，
旧的预期值E，
要修改的新值N

• 当 E == V 时，修改 V 值为 N，返回true
• 当 E != V 时，修改失败，返回false

JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。

画图介绍CAS的操作：

Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。

volatile：使用volatile修饰的变量，就具有可见性，直接修改内存，也就是，一个线程修改的结果，其他线程立刻就能看见，volatile只能让被他修饰内容具有可见性

class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    //... 省略部分代码
}

查找性能为O（logN）

源码分析(JDK1.8)

• 初始化

  /**
   * Initializes table, using the size recorded in sizeCtl.
   */
  private final Node<K,V>[] initTable() {
      Node<K,V>[] tab; int sc;
      while ((tab = table) == null || tab.length == 0) {
          //　如果 sizeCtl < 0 ,说明另外的线程执行CAS 成功，正在进行初始化。
          if ((sc = sizeCtl) < 0)
              // 让出 CPU 使用权
              Thread.yield(); // lost initialization race; just spin
          else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
              try {
                  if ((tab = table) == null || tab.length == 0) {
                      int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                      @SuppressWarnings("unchecked")
                      Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                      table = tab = nt;
                      sc = n - (n >>> 2);
                  }
              } finally {
                  sizeCtl = sc;
              }
              break;
          }
      }
      return tab;
  }

  从源码中可以发现 ConcurrentHashMap 的初始化是通过自旋和 CAS 操作完成的。里面需要注意的是变量 sizeCtl ，它的值决定着当前的初始化状态。

  1. -1 说明正在初始化
  2. -N 说明有N-1个线程正在进行扩容
  3. 表示 table 初始化大小，如果 table 没有初始化
  4. 表示 table 容量，如果 table　已经初始化。

• put:

  1. 根据 key 计算出 hashcode 。
  2. 判断是否需要进行初始化。
  3. 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
  4. 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
  5. 如果都不满足，则利用 synchronized 锁写入数据。
  6. 如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法，在 treeifyBin 中会首先判断当前数组长度≥64时才会将链表转换为红黑树

• get:

  1. 根据 hash 值计算位置。
  2. 查找到指定位置，如果头节点就是要找的，直接返回它的 value.
  3. 如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，查找之。
  4. 如果是链表，遍历查找之

ConcurrentHashMap中的size方法

在jdk7中有两种方案计算size，第一种方案他会使用不加锁的模式去尝试多次计算 ConcurrentHashMap 的 size，最多三次，比较前后两次计算的结果，结果一致就认为当前没有元素加入，计算的结果是准确的。 第二种方案是如果第一种方案不符合，他就会给每个 Segment 加上锁，然后计算 ConcurrentHashMap 的 size 返回。

在jdk1.8中：

最大值是 Integer 类型的最大值，但是 Map 的 size 可能超过 MAX_VALUE， 所以还有一个方法 mappingCount()，JDK 的建议使用 mappingCount() 而不是 size()。mappingCount() 的代码如下：

public long mappingCount() {
     long n = sumCount();
     return (n < 0L) ? 0L : n; // ignore transient negative values
 }

无论是 size() 还是 mappingCount(), 计算大小的核心方法都是 sumCount()

JDK1.8 ConCurrentHashMap的大小 size 通过baseCount 和counterCells 两个变量维护：

（1）在没有并发的情况下，使用一个volatile修饰的baseCount 变量即可；

（2）当有并发时，CAS修改 baseCount 失败后，会使用 CounterCell 类，即 创建一个CounterCell对象，设置其volatile修饰的value 属性为 1，并将其放在ConterCells数组的随机位置；

最终在sumCount()方法中通过累加 baseCount和CounterCells数组里每个CounterCell的值 得出Map的总大小Size。

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

• 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
• 实现线程安全的方式（重要）：
  • 在 JDK1.7 的时候，ConcurrentHashMap 对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据（下面有示意图），多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
  • 到了 JDK1.8 的时候，ConcurrentHashMap 已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
  • Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

HashMap为什么线程不安全

• 死循环

  因为扩容的时候采用的是头插法，头插法会将链表的顺序翻转。这就是引起死循环的原因。线程1和线程2同时进行扩容时。例如说线程1和线程2指向了3节点，线程1开始操作，使用头插法将节点7插入到了3节点的前面，也就是3.next=7。线程2为7.next=3。造成了死循环。

• 数据丢失

• 数据覆盖

  A、B两个线程put时，假设计算出的hash值并对数组取余后是同一个位置，那么就会出现这种情况：A发现这个位置可以插入，但在插入前被挂起了，而B也发现可以插入，并且成功了，那么A继续执行后，由于刚刚已经判断过了是可以插入的，因此会直接把B的值给覆盖掉。

ArrayList为什么是线程不安全的

• add元素之后，会出现有些位置的值为null的情况

  private void add(E e, Object[] elementData, int s) {
      if (s == elementData.length)  // 先不看
          elementData = grow();
      elementData[s] = e;
      size = s + 1;
  }

  假设有两个线程A和B都执行了add方法，并假设此时size为3，A添加完元素后(即执行完 elementData[s] = e;)被挂起了，B也添加元素，注意，此时size还是3，这会导致两个问题：A写的被覆盖，size为5，但5的位置为null。

• 数组下标越界

  还是假设A、B两个线程，并设此时数组长度为10，而s为9，那么A和B同时进到if判断都不会扩容，现在A在上面代码标注位置挂起了，而B接着执行添加操作，所以size = 10，A继续执行，此时就出现了数组下标越界错误。

• size大小不是预期的值

  s+1不是原子操作，举个例子，假设现在s = 4，A、B两个线程都去进行s + 1操作，在Java中每个线程是有自己的工作内存的，因此A和B各自都有一份s = 4，然后分别执行s + 1，最后再写会主存。理想情况是A计算s + 1 = 5之后写回主存，然后B再读取，将6写回主存。但事实却是A和B可能同时执行s + 1 = 5然后写会主存，这就导致了size不是我们预期的结果。