校招笔记（一）_Java_集合

我的校招记录：校招笔记（零）_写在前面，以下是校招笔记总目录。

		备注
算法能力（“刷题”）	这部分就是耗时间多练习，Leetcode-Top100 是很好的选择。	补充练习：codeTop
计算机基础(上)（“八股”）	校招笔记（一）__Java_Java入门	C++后端后续更新
	校招笔记（一）__Java_面对对象
	校招笔记（一）__Java_集合
	校招笔记（一）__Java_多线程
	校招笔记（一）__Java_锁
	校招笔记（一）__Java_JVM
计算机基础(下)（“八股”）	校招笔记（二）__计算机基础_Linux&Git
	校招笔记（三）__计算机基础_计算机网络
	校招笔记（四）__计算机基础_操作系统
	校招笔记（五）__计算机基础_MySQL
	校招笔记（六）__计算机基础_Redis
	校招笔记（七）__计算机基础_数据结构
	校招笔记（八）__计算机基础_场景&智力题
	校招笔记（九）__计算机基础_相关补充
项目&实习	主要是怎么准备项目，后续更新

1.3 集合

1.3.1 集合类

1.请说明Java集合类框架的基本接口有哪些？

Collection：代表一组对象，每一个对象都是它的子元素。
Set：不包含重复元素的Collection。
List：有顺序的collection，并且可以包含重复元素。
Map：可以把键(key)映射到值(value)的对象，键不能重复。

2.（补充：举例说明）说说什么是fail-fast？

fail-fast 机制是 Java 集合（Collection）中的一种错误快速反馈机制。当多个线程对同一个集合的内容进行操作时，就可能会产生 fail-fast 事件。

例如：当某一个线程 A 通过 iterator 去遍历某集合的过程中，若该集合的内容被其他线程所改变了，那么线程 A 访问集合时，就会抛出 ConcurrentModifificationException 异常，产生 fail-fast 事件。这里的操作主要是指 add、remove 和 clear，对集合元素个数进行修改。

3.请说明List、Map、Set三个接口区分？

重复元素：List以特定索引来存取元素，可以有重复元素；Map以键值对映射，不能有重复key；Set元素不能重复
继承collection： List、Set继承于collection；Map和前二者明显区分，不继承collection
实现方式： List是线性结构的容器，典型实现有ArrayList 、LinkedList、Vector； Map、Set都有基于哈希存储和排序树的两种实现版本，前者实现有 HashMap和Hashtable ，后者有HashSet

4.请讲讲你所知道的常用集合类以及主要方法？

最常用的集合类是List 和 Map。

List：典型实现有ArrayList 、LinkedList、Vector ，大小可变，适合用于按数值索引元素类型；
Map：其中每个键映射到一个值，实现有 HashMap和Hashtable 。

1.3.2 Map & Set

1.请你介绍一下map的分类和常见的情况？

java为数据结构中的映射定义了一个接口java.util.Map ，它有四个实现类,分别是HashMap、 Hashtable、 LinkedHashMap、和TreeMap.

Hashmap ：根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。
- 遍历：访问快，遍历时取得的数据随机
- 线程：不支持线程同步（但可以用Collections的synchronizedMap 实现同步）
- key和记录：HashMap允许键和值是null
Hashtable ：和Hashmap类似，是其子类。但其：
线程：支持线程同步，也导致写入比较慢（一个时候只能一个线程写入）
key和记录：不允许记录的键或者值为空；
LinkedHashMap ：HashMap的一个子类，保存了记录插入顺序：
遍历：遍历先得到的记录是先插入、一般情况比HashMap慢。
TreeMap ：实现SortMap接口，默认是按键值的升序排序，
遍历：当用遍历TreeMap时，得到的记录是排过序的
- 线程：线程安全

一般情况下，我们用的最多的是HashMap, 在Map 中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。如果需要输出的顺序和输入的相同,那么用LinkedHashMap 可以实现,它还可以按读取顺序来排列。

1.1 TreeMap的底层实现？

TreeMap实现了SotredMap接口，它是有序的集合。而且是一个红黑树结构，每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器，则根据key执行自然排序。这点会在接下来的代码中做说明，如果指定了比较器则按照比较器来进行排序。

自然排序：TreeMap的所有key必须实现Comparable接口，所有的key都是同一个类的对象
定制排序：创建TreeMap对象传入了一个Comparator对象，该对象负责对TreeMap中所有的key进行排序，采用定制排序不要求Map的key实现Comparable接口。等下面分析到比较方法的时候在分析这两种比较有何不同。

2.请问HashMap和Hashtable区别？

共同点：都实现Map接口
不同点：
1. 对Null key 和Null value的支持：HashMap允许键和值是null，而Hashtable不允许键或者值是null；
2. 线程安全：Hashtable是同步的线程安全，而HashMap不是；
3. 初始容量大小和每次扩充容量大小不同：（1）创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16，之后每次扩充，容量变为原来的2倍；（2）创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小，也就是说 HashMap 总是使用2的幂作为哈希表的大小；
4. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表⻓度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有转换为红黑树这样的机制；
5. 继承父类：HashMap是继承自AbstractMap类，而Hashtable是继承自Dictionary类。

3.请问Map接口实现：HashMap、Hashtable和ConcurrentHashMap区别？

都是key-value存储形式。

底层数据结构：HashMap与ConcurrentHashMap底层数据结构相似（数组+链表+红黑树），Hashtable没有红黑树；
线程安全：Hashtable的synchronized修饰在方法，是对象级的加锁，同一时间只有一个线程能对数据进行操作；ConcurrentHashMap使用了修饰具体对象的synchronized（锁一个桶）和CAS机制，实现了更细粒度的锁；
地址计算：

HashMap使用key.hashCode() ^ (key.hashCode() >>> 16)；-
- Hashtable使用(key.hashCode() & 0x7fffffff) % tab.length()
ConcurrentHashMap使用(key.hashCode() ^ (key.hashCode() >>> 16)) & 0x7fffffff。

4.说一说红黑树特征？

紧接上个问题，面试官很有可能会问红黑树。

每个节点是黑色是红色
根节点和叶子节点是黑色
红色节点不能相邻
从一个节点到子孙节点路径上相同数目的黑节点

5. hashmap的基本原理，扩容方式（rehash）？

很棒的一篇文章：https://www.jianshu.com/p/dde9b12343c1

更棒的一篇文章：https://zhuanlan.zhihu.com/p/81587796

HashMap定义

HashMap继承了Map端口，实现了Serializable等接口。存储HashMap的是一个Entry[]数组，Entry是一个单向链表：

所以我们说HashMap实现的是一个数组+链表 。
1
2
3
4
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
transient Entry<K,V>[] table;

Entry类

Entry在HashMap中实现为一个静态内部类，封装了key和value，还有类型为Entry的next指向下一个Entry引用。

static class Entry<K,V> implements Map.Entry<K,V> {
       final K key;
       V value;
       Entry<K,V> next;
       int hash;

图解HashMap

根据前面所知，我们可以得到HashMap的实现如下（默认初始化容量为16）：

put方法实现

输入的key根据hash(key) 计算出hash值

public V put(K key, V value) {
       // 对key为null的处理
       if (key == null)
           return putForNullKey(value);
       // 根据key算出hash值
       int hash = hash(key);

hash方法如下（JDK1.8版本）

下面这段代码也叫扰动函数 ，参考：JDK 源码中 HashMap 的 hash 方法原理是什么？

混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位异或
// >>>⽆符号右移，忽略符号位，空位都以0补⻬
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

相⽐于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差⼀点点，因为毕竟扰动了 4 次。

Object类HashCode实现

详细源码分析参考：Java Object.hashCode()返回的是对象内存地址？

JDK8 的默认hashCode的计算方法是通过和当前线程有关的一个随机数+三个确定值，运用Marsaglia’s xorshift scheme随机数算法得到的一个随机数。

可以通过在JVM启动参数中添加-XX:hashCode=4，改变默认的hashCode计算方式：
- hashCode == 0 ：返回一个Park-Miller伪随机数生成器生成的随机数，OpenJdk 6 &7的默认实现；
- hashCode == 1：此类方案将对象的内存地址，做移位运算后与一个随机数进行异或得到结果；
- hashCode == 2：此类方案返回固定的1；
- hashCode == 3：此类方案返回一个自增序列的当前值；
- hashCode == 4：此类方案返回当前对象的内存地址。

根据indexFor(hash, table.length) ，计算在table中下标

key.hashcode得到hash → 经过高低16异或扰动得到行hash → indexFor计算下标
indexFor() 实际就是hash值取余：hash%(table.lenght-1) 。但在具体实现中通过位运算实现：
1
2
3
static int indexFor(int h, int length) {
return h & (length-1);
}
- 计算原理。顺便说一下，这也正好解释了为什么HashMap的数组长度要取2的整次幂。因为这样（数组长度-1）正好相当于一个低位掩码。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。
  1
  2
  3
  4
  10100101 11000100 00100101
  & 00000000 00000000 00001111 （16）
  ------------------------------------------
  00000000 00000000 000000101
- 位运算要求length 一定是偶数。length-1则一定是奇数。这样h & (length-1)进行位运算出现的结果可奇可偶，不会一直是偶数，浪费奇数空间。而length为2的幂次，可以保证length一定是偶数，这也是扩容为什么要求一定是2的幂次。

遍历table中下标为i的Entry单向链表，找是否有相同的key已经在HashMap中，如果有，就替换value为最新的值；没有就直接插入。所以HashMap中只能存储唯一的key。

int i = indexFor(hash, table.length);
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
           // 先判断hash值是否一样，如果一样，再判断key是否一样
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;
           }
       }

如果是第一次put上面for循环不会执行，而是addEntry方法直接把key和value封装成Entry，然后加入到table中的实现。
1
2
3
modCount++;
addEntry(hash, key, value, i);
return null;
这涉及到HashMap的扩容机制。

扩容机制

当HashMap中存储的元素个数达到扩容的阀值，那如何进行扩容？

⚠️ 在jdk1.8版本以后，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

我们再来看看addEntry方法中的扩容相关代码：

扩容就是通过resize()方法创建一个长度为原来2倍的新table ；
resize()方法内部通过遍历的方式，将老table的数据，重新计算hash并存储到新table的适当位置，最后使用新的table，并重新计HashMap的扩容阀值。

  void resize(int newCapacity) {   //传入新的容量
     Entry[] oldTable = table;    //引用扩容前的Entry数组
      int oldCapacity = oldTable.length;         
      if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
          threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
          return;
      }
      //初始化一个新的Entry数组
     Entry[] newTable = new Entry[newCapacity];
     //！！将数据转移到新的Entry数组里
     transfer(newTable);     
     //HashMap的table属性引用新的Entry数组
     table = newTable;  
     //修改阈值
     threshold = (int)(newCapacity * loadFactor);
13 }

transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里：

void transfer(Entry[] newTable) {
     //src引用了旧的Entry数组
      Entry[] src = table;                   
      int newCapacity = newTable.length;
      for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
          Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
          if (e != null) {
              src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
              do {
                  Entry<K,V> next = e.next;
                  //！！重新计算每个元素在数组中的位置
                  int i = indexFor(e.hash, newCapacity); 
                 e.next = newTable[i]; //标记[1]
                 newTable[i] = e; //将元素放在数组上
                 e = next; //访问下一个Entry链上元素
            } while (e != null);
          }
     }
 }

newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式。下来的三个步骤是哈希桶数组 resize成4，然后所有的Node重新rehash的过程。

get方法实现

用key的hash值算出key对应的Entry所在链表在在table的下标，然后遍历下标即可。

5.1 为什么HashMap默认链表长度超过8转为红黑树，而不是6、7或9？

在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，概率仅为 0.00000006。源码中注释如下：
1
2
3
4
5
6
7
8
9
10
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
这是一个小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。
特别的，默认是链表长度达到 8 就转成红黑树，而当长度降到 6 就转换回去，这体现了时间和空间平衡的思想。长度较小时，使用链表空间占用少，时间也不会长（因为链表短）。

5.2 HashMap 多线程操作导致死循环问题？

总结： HashMap之所以在并发下的扩容造成死循环，是因为，多个线程并发进行时，因为一个线程先期完成了扩容，将原的链表重新散列到自己的表中，并且链表变成了倒序，后一个线程再扩容时，又进行自己的散列，再次将倒序链表变为正序链表，于是形成了一个环形链表。

void transfer(Entry[] newTable) {
     //src引用了旧的Entry数组
      Entry[] src = table;                   
      int newCapacity = newTable.length;
      for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
          Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
          if (e != null) {
              src[j] = null;
             do {
                  Entry<K,V> next = e.next;
                  //！！重新计算每个元素在数组中的位置
               int i = indexFor(e.hash, newCapacity); 
               e.next = newTable[i]; //标记[1]
               newTable[i] = e;    //将元素放在数组上
                e = next;    //访问下一个Entry链上的元素
            } while (e != null);
          }
     }
 }

map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。
设置断点让线程1和线程2同时debug到transfer方法的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行；然后放开线程2的的断点，让线程2进行resize。结果如下图。
注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的新链表。
线程一被调度回来执行，先是执行 newTalbe[i] = e，然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)，环形链表就这样出现了。

5.3 说说HashMap的put方法？

根据key值计算在数组中的位置：

如果定位到的数组位置没有元素就直接插入；
如果定位到的数组位置有元素，遍历以这个元素为头结点的链表，依次和插入的 key 比较，如果 hash值&equals对象相同就直接覆盖，不同就采用头插法插入元素。

//table[i]的位置已经存在元素，遍历链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {    
    Object k;    

    //调用 equals 方法判断key是否相等，若相等，该key对应的键值对已经存在，用新的value取代旧的value
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {    
        V oldValue = e.value;    
        e.value = value;    
        e.recordAccess(this);    
        return oldValue;    
    }    
}

5.4 说说HashMap的get方法？

根据key值计算在数组中的位置：

遍历链表或者在红黑树，比较key来获取value

5.5 【百度】rehash扩容时机？在插入前还是插入后？

rehash过程在put函数中，其大致扩容时机如下：

计算hash，定位到桶；且遍历桶外挂链表，如果有相同key则覆盖；

public V put(K key, V value) {
        if (key == null)  // 【百度】怎么处理key或value为NULL的情况？
            return putForNullKey(value);
        int hash = hash(key);//计算键的hash值
        int i = indexFor(hash, table.length);//通过hash值对应到桶位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {//顺序遍历桶外挂的单链表
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {/
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);//遍历单链表完毕，没有找到与键相对的Entry，需新建一个Entry
        return null;
    }

【如果没有找到相同key，说明要插入一个新entry】 ，执行addEntry，插入前先验证下是否扩容；

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);//将容量扩容为原来的2倍
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);//扩容后的，该hash值对应的新的桶位置
        }

        createEntry(hash, key, value, bucketIndex);//在指定的桶位置上，创建一个新的Entry
    }

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);//链表的头插法插入新建的Entry
        size++;//更新size
    }

因此总结扩容时机如下：

在执行put时，如果遍历指定桶外挂链表没有找到相同key的节点时，说明需要新建一个entry，这个时候在插入前验证下是否要扩容。

5.6 hashmap在1.7版本之前为什么使用头插法？

1.7版本之前采用头插法，1.8之后采用尾插法。

头插法会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题；而尾插法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题。

既然有多线程并发问题，那为什么1.8之前还要使用头插法？

局部性原理：最近访问过的数据下次大概率会再次访问，把刚访问过的元素放在链表最前面可以直接被查询到，减少查找次数
不是为了适应多线程而设计：　只有在并发情况下，头插法才会出现链表成环的问题，多线程情况下，HashMap 本就非线程安全，这就相当于你在它的规则之外出了问题。

5.7 为什么 HashMap 的负载因子设置成 0.75，而不是 1 也不是 0.5？

在 HashMap 中，临界值（threshold） = 负载因子（loadFactor） * 容量（capacity）。

那么如何能有效的避免哈希碰撞呢？

我们先反向思维一下，你认为什么情况会导致 HashMap 的哈希碰撞比较多？

无外乎两种情况：

容量太小。容量小，碰撞的概率就高了。狼多肉少，就会发生争抢。
hash 算法不够好。算法不合理，就可能都分到同一个或几个桶中。分配不均，也会发生争抢。

为了避免哈希碰撞，HashMap 需要在合适的时候进行扩容。那就是当其中的元素个数达到临界值的时候（等全满了再扩容，那么在此之前容量太少，导致碰撞的概率过高），而这个临界值前面说过和 loadFactor 有关，换句话说，设置一个合理的 loadFactor，可以有效的避免哈希冲突。

JVM中原话：

一般来说，默认的负载因子 (0.75) 在时间和空间成本之间提供了很好的权衡。更高的值减少了空间开销，但增加了查找成本(反映在 HashMap 类的大多数操作中，包括 get 和 put)。

另一方面，为了保证负载因子（loadFactor） * 容量（capacity）的结果是一个整数，这个值是 0.75(3/4) 比较合理，因为这个数和任何 2 的幂乘积结果都是整数。

5.8 Hashmap 怎么处理key和value为null的情况？

6. Hashtable 源码分析

参考：Java集合之Hashtable源码解析

构造函数

和HashMap还是挺相似的，但是默认初始容量是11（HashMap是16）。

private transient Entry<?,?>[] table;//数组
    private transient int count;//键值对的数量
    private int threshold;//阀值
    private float loadFactor;//加载因子
    private transient int modCount = 0;//修改次数
    public Hashtable(int initialCapacity, float loadFactor) {//下面的三个构造函数都是调用这个函数，来进行相关的初始化
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];//这里是与HashMap的区别之一，HashMap中table
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        initHashSeedAsNeeded(initialCapacity);
    }

    public Hashtable(int initialCapacity) {//指定初始数组长度
        this(initialCapacity, 0.75f);
    }

    public Hashtable() {//从这里可以看出容量的默认值为16，加载因子为0.75f.
        this(11, 0.75f);
    }

    public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }

put方法

和HashMap整体过程依旧很像，但有4点注意：

put方法是加锁synchronized，所以线程安全
Hashtable计算hash值的hash(key)，不允许为null，所以会抛出异常
获取数组散列的下标 (hash & 0x7FFFFFFF) % tab.length 和HashMap hash & length-1 不同
- (hash & 0x7FFFFFFF) % tab.length 是（1）hash & 0x7FFFFFFF 保证hash是正数（2）然后取余
- 相比之下，HashMap是位运算进行了优化，更高效
Hashtable没有链表转红黑树的机制

public synchronized V put(K key, V value) {//这里方法修饰符为synchronized,所以是线程安全的。
        if (value == null) {
            throw new NullPointerException();//value如果为Null,抛出异常
        }
        Entry tab[] = table;
        int hash = hash(key);//hash里面的代码是hashSeed^key.hashcode（）,null.hashCode（）会抛出异常，所以这就解释了Hashtable的key和value不能为null的原因。
        int index = (hash & 0x7FFFFFFF) % tab.length;//获取数组元素下标,先对hash值取正，然后取余。
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }

        modCount++;//修改次数。
        if (count >= threshold) {//键值对的总数大于其阀值
            rehash();//在rehash里进行扩容处理

            tab = table;
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
        Entry<K,V> e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        return null;
    }

rehash方法（扩容）

和HashMap依旧很像，但是扩容每次是 old*2+1 。

get方法

也是相比Hashmap直接加了 synchronized 进行修饰，保证线程安全。

public synchronized V get(Object key) {//没有什么特殊性，就是加了一个synchronized，就是根据index来遍历索引处的单链表。
       Entry tab[] = table;
       int hash = hash(key);
       int index = (hash & 0x7FFFFFFF) % tab.length;
       for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
           if ((e.hash == hash) && e.key.equals(key)) {
               return e.value;
           }
       }
       return null;
   }

6.1 （容易忘）HashMap 和 Hashtable 的区别？

关于null，HashMap允许key和value都可以为null，而Hashtable则不接受key为null或value为null的键值对。
关于线程安全，HashMap是线程不安全的，Hashtable是线程安全的，因为Hashtable的许多操作函数都用synchronized修饰。
Hashtable与HashMap实现的接口不一致，但Hashtable继承Dictionary，而HashMap继承自AbstractMap，即父类不同
默认初始容量不同，扩容大小不同。HashMap的hash数组的默认大小是16，而且一定是2 的指数old*2；Hashtable中hash数组默认大小是11，增加的方式是old*2+1。

6.2 ConcurrentHashMap 和 Hashtable 的区别？

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

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

7. ConcurrentHashMap线程安全的具体实现方式/底层具体实现？

参考：https://www.cnblogs.com/huangjuncong/p/9478505.html

javaGuide

Java7 中 ConcurrentHashMap 使用的分段锁，也就是每一个 Segment 上同时只有一个线程可以操作，每一个 Segment 都是一个类似 HashMap 数组的结构，它可以扩容，它的冲突会转化为链表。但是 Segment 的个数一但初始化就不能改变。

Java8 中的 ConcurrentHashMap 使用的 Synchronized 锁加 CAS 的机制。结构也由 Java7 中的 Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树，Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表。

JDK 1.7 实现

Java 7 中 ConcurrentHashMap 的存储结构如下图。

存储结构

ConcurrentHashMap 为了提高本身的并发能力，在内部采用了一个叫做 Segment 的结构，一个 Segment 其实就是一个类 HashTable 的结构，Segment 内部维护了一个链表数组。

两次Hash。ConcurrentHashMap 定位一个元素的过程需要进行两次Hash操作，第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部。

因此，这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长，但是带来的好处是写操作的时候可以只对元素所在的 Segment 进行操作即可，不会影响到其他的 Segment。

1. ConcurrentHashMap的成员变量和构造函数

ConcurrentHashMap扩容：元素数量增加导致ConrruentHashMap需要扩容，ConcurrentHashMap不会增加Segment的数量，而只会增加Segment中链表数组的容量大小。需要对整个ConcurrentHashMap做rehash，而只需要对Segment里面的元素做一次rehash就可以了。

核心初始化函数逻辑如下：

2的指数是为了可以使用移位操作加快hash计算过程。

计算出Segment的数量ssize，是不大于concurrencyLevel的最大的2的指数

int ssize = 1;
while (ssize < concurrencyLevel) {
          ++sshift; 
           ssize <<= 1;
}

根据intialCapacity确定Segment的容量的大小，每一个Segment的容量大小也是2的指数

int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
      ++c;
      int cap = MIN_SEGMENT_TABLE_CAPACITY;
      while (cap < c)
            cap <<= 1;

下面是完整代码：

segmentShift 偏移量，这个值为【容量 = 2 的N次方】中的 N，在后面 Put 时计算位置时会用到 。默认是 32 - sshift = 28

segmentMask，默认是 ssize - 1 = 16 -1 = 15

// 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 默认segment层级
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// segment最小容量
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
// 一个segment最大容量
static final int MAX_SEGMENTS = 1 << 16;
// 锁之前重试次数
static final int RETRIES_BEFORE_LOCK = 2;

// 构造函数：无参
public ConcurrentHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}
// 构造函数：指定初始容量
public ConcurrentHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}
// 构造函数：指定初始容量，负载因子
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
}
// 构造函数：指定初始容量，负载因子，并发级别
public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (concurrencyLevel > MAX_SEGMENTS)
            concurrencyLevel = MAX_SEGMENTS;
        // 找到两种大小的最匹配参数
        int sshift = 0;
        // segment数组的长度是由concurrentLevel计算来的，segment数组的长度是2的N次方，
        // 默认concurrencyLevel = 16, 所以ssize在默认情况下也是16,此时 sshift = 4
        // sshift相当于ssize从1向左移的次数
        int ssize = 1;
        while (ssize < concurrencyLevel) {
            ++sshift; 
            ssize <<= 1;
        }
        // 段偏移量，默认值情况下此时segmentShift = 28
        this.segmentShift = 32 - sshift;
        // 散列算法的掩码，默认值情况下segmentMask = 15
        this.segmentMask = ssize - 1;

        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

        int c = initialCapacity / ssize;
        if (c * ssize < initialCapacity)
            ++c;
        int cap = MIN_SEGMENT_TABLE_CAPACITY;
        while (cap < c)
            cap <<= 1;
        // create segments and segments[0]
        Segment<K,V> s0 =
            new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                             (HashEntry<K,V>[])new HashEntry[cap]);
        // 创建ssize长度的Segment数组
        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
        this.segments = ss;
 }

2.来查看具体代码定义，Segment的成员变量：

Segment 继承于 ReentrantLock，不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理。

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    transient volatile int count;    //Segment中元素的数量
    transient int modCount;      //对table的大小造成影响的操作的数量(比如put或者remove操作)
    transient int threshold;    //阈值,Segment里面元素的数量超过这个值那么就会对Segment进行扩容
    final float loadFactor;   //负载因子,用于确定threshold
    transient volatile HashEntry<K,V>[] table;    //链表数组,数组中的每一个元素代表了一个链表的头部
}

3. 继续查看HashEntry组成：

和 HashMap 非常类似，唯一的区别就是其中的核心数据如 value ，以及链表都是 volatile 修饰的，保证了获取时的可见性。

    　/**
 * ConcurrentHashMap列表Entry。注意，这不会作为用户可见的Map.Entry导出。
 */
static final class HashEntry<K,V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K,V> next;
    
    HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    
    // 设置具有volatile写语义的next字段。
  final void setNext(HashEntry<K,V> n) {
      UNSAFE.putOrderedObject(this, nextOffset, n);
    }
    // 下面不太重要，略。

put() 方法实现

相比Hashtable，1.7版本concurrentHashmap的更加细粒度，只有定位到段，才会锁住。也就是段锁！

而Hashtable直接锁住整个方法。

计算key的hash值 ;
根据hash值，segmentShift，segmentMask定位到哪个Segment；
如果指定位置的 Segment 为空，则初始化这个 Segment；
在对应的 Segment 中进行具体的 put。

public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key);
    // hash 值无符号右移 28位（初始化时获得），然后与 segmentMask=15 做与运算
    // 其实也就是把高4位与segmentMask（1111）做与运算
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
        // 如果查找到的 Segment 为空，初始化
        s = ensureSegment(j);
    return s.put(key, hash, value, false);
}

Segment 中进行具体的 put的源码如下：

判断元素个数是否超过了阈值或者segment中数组的长度超过了MAXIMUM_CAPACITY，如果满足条件则rehash扩容！

由于 Segment 继承了 ReentrantLock，所以 Segment 内部可以很方便的获取锁，put 流程就用到了这个功能。

tryLock() 获取锁，获取不到使用scanAndLockForPut方法继续获取；

这里面的第一步中的 scanAndLockForPut 操作这里没有介绍，这个方法做的操作就是不断的自旋 tryLock() 获取锁。当自旋次数大于指定次数时，使用 lock() 阻塞获取锁。
计算 put 的数据要放入的 index 位置，然后获取这个位置上的 HashEntry ；
遍历 put 新元素，为什么要遍历？因为这里获取的 HashEntry 可能是一个空元素，也可能是链表已存在，所以要区别对待；

如果这个位置上的 HashEntry 不存在：
1. 如果当前容量大于扩容阀值，小于最大容量，进行扩容。
2. 直接头插法插入。
如果这个位置上的 HashEntry 存在：
1. 判断链表当前元素 Key 和 hash 值是否和要 put 的 key 和 hash 值一致，一致则替换值
2. 不一致，获取链表下一个节点，直到发现相同进行值替换，或者链表表里完毕没有相同的。
  1. 如果当前容量大于扩容阀值，小于最大容量，进行扩容。
  2. 直接链表头插法插入。
如果要插入的位置之前已经存在，替换后返回旧值，否则返回 null。

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    // 获取 ReentrantLock 独占锁，获取不到，scanAndLockForPut 获取。
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        // 计算要put的数据位置
        int index = (tab.length - 1) & hash;
        // CAS 获取 index 坐标的值
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                // 检查是否 key 已经存在，如果存在，则遍历链表寻找位置，找到后替换 value
                K k;
                if ((k = e.key) == key ||
                    (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                e = e.next;
            }
            else {
                // first 有值没说明 index 位置已经有值了，有冲突，链表头插法。
                if (node != null)
                    node.setNext(first);
                else
                    node = new HashEntry<K,V>(hash, key, value, first);
                int c = count + 1;
                // 容量大于扩容阀值，小于最大容量，进行扩容
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);
                else
                    // index 位置赋值 node，node 可能是一个元素，也可能是一个链表的表头
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        unlock();
    }
    return oldValue;
}

扩容 rehash

rehash在put()内部被触发。

ConcurrentHashMap 的扩容只会扩容到原来的两倍。老数组里的数据移动到新的数组时，位置要么不变，要么变为 index+ oldSize，参数里的 node 会在扩容之后使用链表头插法插入到指定位置。

1	int idx = e.hash & sizeMask; // 新位置计算

private void rehash(HashEntry<K,V> node) {
    HashEntry<K,V>[] oldTable = table;
    // 老容量
    int oldCapacity = oldTable.length;
    // 新容量，扩大两倍
    int newCapacity = oldCapacity << 1;
    // 新的扩容阀值 
    threshold = (int)(newCapacity * loadFactor);
    // 创建新的数组
    HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];
    // 新的掩码，默认2扩容后是4，-1是3，二进制就是11。
    int sizeMask = newCapacity - 1;
    for (int i = 0; i < oldCapacity ; i++) {
        // 遍历老数组
        HashEntry<K,V> e = oldTable[i];
        if (e != null) {
            HashEntry<K,V> next = e.next;
            // 计算新的位置，新的位置只可能是不变或者是：老的位置+老的容量。
            int idx = e.hash & sizeMask;
            if (next == null)   //  Single node on list
                // 如果当前位置还不是链表，只是一个元素，直接赋值
                newTable[idx] = e;
            else { // Reuse consecutive sequence at same slot
                // 如果是链表了
                HashEntry<K,V> lastRun = e;
                int lastIdx = idx;
                // 新的位置只可能是不变或者是：老的位置+老的容量。
                // 遍历结束后，lastRun 后面的元素位置都是相同的
                for (HashEntry<K,V> last = next; last != null; last = last.next) {
                    int k = last.hash & sizeMask;
                    if (k != lastIdx) {
                        lastIdx = k;
                        lastRun = last;
                    }
                }
                // ，lastRun 后面的元素位置都是相同的，直接作为链表赋值到新位置。
                newTable[lastIdx] = lastRun;
                // Clone remaining nodes
                for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
                    // 遍历剩余元素，头插法到指定 k 位置。
                    V v = p.value;
                    int h = p.hash;
                    int k = h & sizeMask;
                    HashEntry<K,V> n = newTable[k];
                    newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
                }
            }
        }
    }
    // 头插法插入新的节点
    int nodeIndex = node.hash & sizeMask; // add the new node
    node.setNext(newTable[nodeIndex]);
    newTable[nodeIndex] = node;
    table = newTable;
}

get方法

注意，Hashtable 会使用Synchronized进行修饰，所以不支持并发。但是ConcurrentHashmap 没有使用同步机制：

1.7版本 。使用unsafe方法（）等方式直接操作来保证并发处理的安全性，使用的是硬件的安全机制。

1.8版本。没有使用同步，也没有使用unsafe方式。所以是并发的。

到这里就很简单了，get 方法只需要两步即可。

计算得到segment的位置 u
CAS方式获取segment数组对象 segment[u]
计算HashEntry数组的下标 i
CAS方式获取HashEntry[i]，即数组首节点

public V get(Object key) {
    Segment<K,V> s; // manually integrate access methods to reduce overhead
    HashEntry<K,V>[] tab;
    int h = hash(key);
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    // 计算得到 key 的存放位置
    if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
        (tab = s.table) != null) {
        for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
             e != null; e = e.next) {
            // 如果是链表，遍历查找到相同 key 的 value。
            K k;
            if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                return e.value;
        }
    }
    return null;
}

JDK 1.8 实现

1.8版本分析，建议参考：https://www.cnblogs.com/zerotomax/p/8687425.html 。

可以发现 Java8 的 ConcurrentHashMap 相对于 Java7 来说变化比较大，不再是之前的 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。当冲突链表达到一定长度时，链表会转换成红黑树。

和JDK1.8的HashMap是很相似 , 抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。

存储结构和属性

private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final int DEFAULT_CAPACITY = 16; // hashmap也是16
static final int TREEIFY_THRESHOLD = 8; // 超过8扩容
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64; // 超过64红黑树
static final int MOVED     = -1; // 表示正在转移
static final int TREEBIN   = -2; // 表示已经转换成树
static final int RESERVED  = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; 

// Node数组存储元素
transient volatile Node<K,V>[] table;//默认没初始化的数组，用来保存元素
private transient volatile Node<K,V>[] nextTable;//转移的时候用的数组

/**
     * 用来控制表初始化和扩容的，默认值为0，当在初始化的时候指定了大小，这会将这个大小保存在sizeCtl中，大小为数组的0.75
     * 当为负的时候，说明表正在初始化或扩张，
     *     -1表示初始化
     *     -(1+n) n:表示活动的扩张线程
     */
private transient volatile int sizeCtl;

在ConcurrentHashMap中使用了unSafe方法，通过直接操作内存的方式来保证并发处理的安全性，使用的是硬件的安全机制。

/*
     * 用来返回节点数组的指定位置的节点的原子操作
     */
    @SuppressWarnings("unchecked")
    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }

    /*
     * cas原子操作，在指定位置设定值
     */
    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }
    /*
     * 原子操作，在指定位置设定值
     */
    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }

初始化

//空的构造
public ConcurrentHashMapDebug() {
    }
//如果在实例化对象的时候指定了容量，则初始化sizeCtl
public ConcurrentHashMapDebug(int initialCapacity) {
      if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }
//当出入一个Map的时候，先设定sizeCtl为默认容量，在添加元素
public ConcurrentHashMapDebug(Map<? extends K, ? extends V> m) {
        this.sizeCtl = DEFAULT_CAPACITY;
        putAll(m);
    }

put方法

1
2
3

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

再来看putVal ：

可以发现相比HashTable直接对方法进行加锁synchronized / 1.7版本的ConcurrentHashMap 进入的开头尝试获取锁，1.8版本的ConcurrentHashMap 锁更加细粒度化。

只有：（1）table不为初始化（2）定位到table位置i不存在元素（此时会用CAS方式进行添加）（3）数组也没有在进行扩张（MOVED=-1）

此时才会进行synchronized 添加元素（不会锁住rehash方法，最后才判断是否扩容）。

/*
     * 当添加一对键值对的时候，首先会去判断保存这些键值对的数组是不是初始化了，
     * 如果没有的话就初始化数组
     *  然后通过计算hash值来确定放在数组的哪个位置
     * 如果这个位置为空则直接添加，如果不为空的话，则取出这个节点来
     * 如果取出来的节点的hash值是MOVED(-1)的话，则表示当前正在对这个数组进行扩容，复制到新的数组，则当前线程也去帮助复制
     * 最后一种情况就是，如果这个节点，不为空，也不在扩容，则通过synchronized来加锁，进行添加操作
     *    然后判断当前取出的节点位置存放的是链表还是树
     *    如果是链表的话，则遍历整个链表，直到取出来的节点的key来个要放的key进行比较，如果key相等，并且key的hash值也相等的话，
     *          则说明是同一个key，则覆盖掉value，否则的话则添加到链表的末尾
     *    如果是树的话，则调用putTreeVal方法把这个元素添加到树中去
     *  最后在添加完成之后，会判断在该节点处共有多少个节点（注意是添加前的个数），如果达到8个以上了的话，
     *  则调用treeifyBin方法来尝试将处的链表转为树，或者扩容数组
     */

final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();//K,V都不能为空，否则的话跑出异常
        int hash = spread(key.hashCode());    //取得key的hash值
        int binCount = 0;    //用来计算在这个节点总共有多少个元素，用来控制扩容或者转移为树
        for (Node<K,V>[] tab = table;;) {    //
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)    
                tab = initTable();    //第一次put的时候table没有初始化，则初始化table
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {    //通过哈希计算出一个表中的位置因为n是数组的长度，所以(n-1)&hash肯定不会出现数组越界
                if (casTabAt(tab, i, null,        //如果这个位置没有元素的话，则通过cas的方式尝试添加，注意这个时候是没有加锁的
                             new Node<K,V>(hash, key, value, null)))        //创建一个Node添加到数组中区，null表示的是下一个节点为空
                    break;                   // no lock when adding to empty bin
            }
            /*
             * 如果检测到某个节点的hash值是MOVED，则表示正在进行数组扩张的数据复制阶段，
             * 则当前线程也会参与去复制，通过允许多线程复制的功能，一次来减少数组的复制所带来的性能损失
             */
            else if ((fh = f.hash) == MOVED)    
                tab = helpTransfer(tab, f);
            else {
                /*
                 * 如果在这个位置有元素的话，就采用synchronized的方式加锁，
                 *     如果是链表的话(hash大于0)，就对这个链表的所有元素进行遍历，
                 *         如果找到了key和key的hash值都一样的节点，则把它的值替换到
                 *         如果没找到的话，则添加在链表的最后面
                 *  否则，是树的话，则调用putTreeVal方法添加到树中去
                 *  
                 *  在添加完之后，会对该节点上关联的的数目进行判断，
                 *  如果在8个以上的话，则会调用treeifyBin方法，来尝试转化为树，或者是扩容
                 */
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {        //再次取出要存储的位置的元素，跟前面取出来的比较
                        if (fh >= 0) {                //取出来的元素的hash值大于0，当转换为树之后，hash值为-2
                            binCount = 1;            
                            for (Node<K,V> e = f;; ++binCount) {    //遍历这个链表
                                K ek;
                                if (e.hash == hash &&        //要存的元素的hash，key跟要存储的位置的节点的相同的时候，替换掉该节点的value即可
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)        //当使用putIfAbsent的时候，只有在这个key没有设置值得时候才设置
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {    //如果不是同样的hash，同样的key的时候，则判断该节点的下一个节点是否为空，
                                    pred.next = new Node<K,V>(hash, key,        //为空的话把这个要加入的节点设置为当前节点的下一个节点
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {    //表示已经转化成红黑树类型了
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,    //调用putTreeVal方法，将该元素添加到树中去
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)    //当在同一个节点的数目达到8个的时候，则扩张数组或将给节点的数据转为tree
                        treeifyBin(tab, i);    
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);    //计数，可能也会触发扩容
        return null;
    }

扩容transfer

扩容主要是通过transfer方法来进行的。

只有在往map中添加元素的时候，在某一个节点的数目已经超过了8个，调用treeifyBin() 触发数组的扩容/转换为数；

使用**addCount()**添加元素数组元素，会进行判断达到了sizeCtl的数量的时候，则会调用transfer方法来进行扩容

treeifyBin()

某一个节点的数目已经超过了8个，执行treeifyBin() 。

当需要扩容的时候，调用的时候tryPresize方法

（1）tryPresize方法并没有加锁，允许多个线程进入，如果数组正在扩张，则当前线程也去帮助扩容使用transfer方法

（2）transfer比较复杂还没有详细看，它里面使用的synchronized 进行单个节点处理扩容（查看上面看transfer源码）
否则synchronized进行链表转换为树

/*
     * 当数组长度小于64的时候，扩张数组长度一倍，否则的话把链表转为树
     */
    private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n, sc;
        if (tab != null) {
                System.out.println("treeifyBin方\t==>数组长："+tab.length);
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)    //MIN_TREEIFY_CAPACITY 64
                tryPresize(n << 1);        // 数组扩容
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                synchronized (b) {    //使用synchronized同步器，将该节点出的链表转为树
                    if (tabAt(tab, index) == b) {
                        TreeNode<K,V> hd = null, tl = null;    //hd：树的头(head)
                        for (Node<K,V> e = b; e != null; e = e.next) {
                            TreeNode<K,V> p =
                                new TreeNode<K,V>(e.hash, e.key, e.val,
                                                  null, null);
                            if ((p.prev = tl) == null)        //把Node组成的链表，转化为TreeNode的链表，头结点任然放在相同的位置
                                hd = p;    //设置head
                            else
                                tl.next = p;
                            tl = p;
                        }
                        setTabAt(tab, index, new TreeBin<K,V>(hd));//把TreeNode的链表放入容器TreeBin中
                    }
                }
            }
        }
    }

addCount()

addCount也主要是调用transfer，这里主要还是寄一下transfer的源码。

/**
     * Moves and/or copies the nodes in each bin to new table. See
     * above for explanation.
     * 把数组中的节点复制到新的数组的相同位置，或者移动到扩张部分的相同位置
     * 在这里首先会计算一个步长，表示一个线程处理的数组长度，用来控制对CPU的使用，
     * 每个CPU最少处理16个长度的数组元素,也就是说，如果一个数组的长度只有16，那只有一个线程会对其进行扩容的复制移动操作
     * 扩容的时候会一直遍历，知道复制完所有节点，没处理一个节点的时候会在链表的头部设置一个fwd节点，这样其他线程就会跳过他，
     * 复制后在新数组中的链表不是绝对的反序的
     */
    private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        int n = tab.length, stride;
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)    //MIN_TRANSFER_STRIDE 用来控制不要占用太多CPU
            stride = MIN_TRANSFER_STRIDE; // subdivide range    //MIN_TRANSFER_STRIDE=16
        /*
         * 如果复制的目标nextTab为null的话，则初始化一个table两倍长的nextTab
         * 此时nextTable被设置值了(在初始情况下是为null的)
         * 因为如果有一个线程开始了表的扩张的时候，其他线程也会进来帮忙扩张，
         * 而只是第一个开始扩张的线程需要初始化下目标数组
         */
        if (nextTab == null) {            // initiating
            try {
                @SuppressWarnings("unchecked")
                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {      // try to cope with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            nextTable = nextTab;
            transferIndex = n;
        }
        int nextn = nextTab.length;
        /*
         * 创建一个fwd节点，这个是用来控制并发的，当一个节点为空或已经被转移之后，就设置为fwd节点
         * 这是一个空的标志节点
         */
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        boolean advance = true;    //是否继续向前查找的标志位
        boolean finishing = false; // to ensure sweep(清扫) before committing nextTab,在完成之前重新在扫描一遍数组，看看有没完成的没
        for (int i = 0, bound = 0;;) {
            Node<K,V> f; int fh;
            while (advance) {
                int nextIndex, nextBound;
                if (--i >= bound || finishing) {
                    advance = false;
                }
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false;
                }
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            if (i < 0 || i >= n || i + n >= nextn) {
                int sc;
                if (finishing) {        //已经完成转移
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);    //设置sizeCtl为扩容后的0.75
                    return;
                }
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) {
                            return;
                    }
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            else if ((f = tabAt(tab, i)) == null)            //数组中把null的元素设置为ForwardingNode节点(hash值为MOVED[-1])
                advance = casTabAt(tab, i, null, fwd);
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            else {
                synchronized (f) {                //加锁操作
                    if (tabAt(tab, i) == f) {
                        Node<K,V> ln, hn;
                        if (fh >= 0) {        //该节点的hash值大于等于0，说明是一个Node节点
                                /*
                                 * 因为n的值为数组的长度，且是power(2,x)的，所以，在&操作的结果只可能是0或者n
                                 * 根据这个规则
                                 *         0-->  放在新表的相同位置
                                 *         n-->  放在新表的（n+原来位置）
                                 */
                            int runBit = fh & n; 
                            Node<K,V> lastRun = f;
                            /*
                             * lastRun 表示的是需要复制的最后一个节点
                             * 每当新节点的hash&n -> b 发生变化的时候，就把runBit设置为这个结果b
                             * 这样for循环之后，runBit的值就是最后不变的hash&n的值
                             * 而lastRun的值就是最后一次导致hash&n 发生变化的节点(假设为p节点)
                             * 为什么要这么做呢？因为p节点后面的节点的hash&n 值跟p节点是一样的，
                             * 所以在复制到新的table的时候，它肯定还是跟p节点在同一个位置
                             * 在复制完p节点之后，p节点的next节点还是指向它原来的节点，就不需要进行复制了，自己就被带过去了
                             * 这也就导致了一个问题就是复制后的链表的顺序并不一定是原来的倒序
                             */
                            for (Node<K,V> p = f.next; p != null; p = p.next) {
                                int b = p.hash & n;    //n的值为扩张前的数组的长度
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            else {
                                hn = lastRun;
                                ln = null;
                            }
                            /*
                             * 构造两个链表，顺序大部分和原来是反的
                             * 分别放到原来的位置和新增加的长度的相同位置(i/n+i)
                             */
                            for (Node<K,V> p = f; p != lastRun; p = p.next) {
                                int ph = p.hash; K pk = p.key; V pv = p.val;
                                if ((ph & n) == 0)
                                        /*
                                         * 假设runBit的值为0，
                                         * 则第一次进入这个设置的时候相当于把旧的序列的最后一次发生hash变化的节点(该节点后面可能还有hash计算后同为0的节点)设置到旧的table的第一个hash计算后为0的节点下一个节点
                                         * 并且把自己返回，然后在下次进来的时候把它自己设置为后面节点的下一个节点
                                         */
                                    ln = new Node<K,V>(ph, pk, pv, ln);
                                else
                                        /*
                                         * 假设runBit的值不为0，
                                         * 则第一次进入这个设置的时候相当于把旧的序列的最后一次发生hash变化的节点(该节点后面可能还有hash计算后同不为0的节点)设置到旧的table的第一个hash计算后不为0的节点下一个节点
                                         * 并且把自己返回，然后在下次进来的时候把它自己设置为后面节点的下一个节点
                                         */
                                    hn = new Node<K,V>(ph, pk, pv, hn);    
                            }
                            setTabAt(nextTab, i, ln);    
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                        else if (f instanceof TreeBin) {    //否则的话是一个树节点
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> lo = null, loTail = null;
                            TreeNode<K,V> hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            for (Node<K,V> e = t.first; e != null; e = e.next) {
                                int h = e.hash;
                                TreeNode<K,V> p = new TreeNode<K,V>
                                    (h, e.key, e.val, null, null);
                                if ((h & n) == 0) {
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                else {
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            /*
                             * 在复制完树节点之后，判断该节点处构成的树还有几个节点，
                             * 如果≤6个的话，就转回为一个链表
                             */
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                (hc != 0) ? new TreeBin<K,V>(lo) : t;
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new TreeBin<K,V>(hi) : t;
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }

get方法

get操作中，根本没有使用同步机制，也没有使用unsafe方法，所以读（get）操作是支持并发操作的。

/*
     * 相比put方法，get就很单纯了，支持并发操作，
     * 当key为null的时候回抛出NullPointerException的异常
     * get操作通过首先计算key的hash值来确定该元素放在数组的哪个位置
     * 然后遍历该位置的所有节点
     * 如果不存在的话返回null
     */
    public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

7.1 你知道 ConcurrentHashMap 的工作原理吗？

Java7 中 ConcurrentHashMap 使用的分段锁，也就是每一个 Segment 上同时只有一个线程可以操作，每一个 Segment 都是一个类似 HashMap 数组的结构，它可以扩容，它的冲突会转化为链表。但是 Segment 的个数一但初始化就不能改变。
- 主要采用锁机制，在对某个Segment进行操作时，将该Segment锁定，不允许对其进行非查询操作
Java8 中的 ConcurrentHashMap 使用的 Synchronized 锁加 CAS 的机制。结构也由 Java7 中的 Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树，Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表。
- CAS无锁算法，这种乐观操作在完成前进行判断，如果符合预期结果才给予执行

7.2 请问ConcurrentHashMap中变量使用final和volatile修饰有什么用呢？其中链表是final的next属性，那么发生删除某个元素，如何实现的？

ConcurrentHashMap被final修饰的变量，（部分）如下：

// 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 默认segment层级
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// segment最小容量
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
// 一个segment最大容量
static final int MAX_SEGMENTS = 1 << 16;
// 锁之前重试次数
static final int RETRIES_BEFORE_LOCK = 2;

HashEntry中被volatile修饰的部分变量如下：

static final class HashEntry<K,V> {
       final int hash;
       final K key;
       volatile V value;  // 保证可见性
       volatile HashEntry<K,V> next;

使用final。用来实现不变模式（immutable），他是多线程安全里最简单的一种保障方式。因为你拿他没有办法，想改变它也没有机会。不变模式主要通过final关键字来限定的。在JMM中final关键字还有特殊的语义。Final域使得确保初始化安全性（initialization safety）成为可能，初始化安全性让不可变形对象不需要同步就能自由地被访问和共享。
使用volatile。保证某个变量内存的改变对其他线程即时可见，在配合CAS可以实现不加锁对并发操作的支持。

7.3 HashTable与ConcurrentHashMap有什么区别，描述锁分段技术。

锁机制。所有访问HashTable的线程都必须竞争同一把锁，效率更低；ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。
底层数据结构。 1.8之后很相似，都是数组+链表/红黑树； 1.8之前，ConcurrentHashMap是Segement数组 + HashEntry数组 + 链表。

7.4 （阿里·淘特）ConcurrentHashMap1.8为什么不使用分段锁？

先说分段锁的优点：

保证在操作不同段 map 的时候可以并发执行；操作同段 map 的时候，进行锁的竞争和等待。这相对于直接对整个map同步synchronized是有优势的。

但是分段锁也有一些不可忽视的缺点：

分成很多段时会比较浪费内存空间(不连续，碎片化)；
操作map时竞争同一个分段锁的概率非常小（段散列比较好的时候）时，分段锁反而会造成更新等操作的长时间等待；
当某个段很大时，分段锁的性能会下降。

综上考虑1.8不再使用分段锁。

7.5 为什么1.8中 get() 方法不加锁？

因为链表每个节点的val和next都使用volatile修饰，保证了可见性。

7.6 为什么1.8不使用lock而是使用sync？

因为sync加入锁升级机制（jdk1.6之后），已经优化的不错了；
lock通过reentranclock实现，reentranlock是通过AQS实现，需要增加额外内存开销（CLH双向队列）。

7.7 ConcurrenthashMap使用的时候有可能出现不安全的情况？

参考：https://blog.csdn.net/luzhensmart/article/details/108133560

查了一些资料后发现，原来ConcurrentHashMap的线程安全指的是，它的【每个方法】单独调用（即原子操作）都是线程安全的，但是代码总体的互斥性并不受控制。以上面的代码为例，最后一行中的：

public void run() {
        for (int i = 0; i < 100; i++) {
            this.addup();
        }
    }
 
    private void addup() {
        if (!map.containsKey(KEY)) {
            map.put(KEY, 1);
        } else {
            map.put(KEY, map.get(KEY) + 1);
        }
    }

在上面一个线程内部进行了100次加法，但是其实加1在线程内部本身也并不是原子操作。

实际上并不是原子操作，它包含了三步：

map.get
加1
map.put

是由于在上面的代码中，map本身是一个共享变量。当线程A执行map.get的时候，其它线程可能正在执行map.put，这样一来当线程A执行到map.put的时候，线程A的值就已经是脏数据了，然后脏数据覆盖了真值，导致线程不安全。

8. HashMap 和 HashSet区别？

如果你看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了clone() 、 writeObject() 、 readObject() 是 HashSet ⾃⼰不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashMap	HashSet
实现了Map接⼝	实现Set接⼝
存储键值对	仅存储对象
调⽤ `put()` 向map中添加元素	调⽤ `add()` ⽅法向Set中添加元素
HashMap使⽤键（Key）计算Hashcode：`int hash = hash(key);`	HashSet使⽤成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()⽅法⽤来判断对象的相等性。

9. 说说HashSet的基本原理？

底层结构

HashSet底层原理完全就是包装了一下HashMap ，只不过存储的时候value是默认存储了一个Object的静态常量，取的时候也是只返回key，所以看起来就像List一样。

初始化

private transient HashMap<E,Object> map;
  
public HashSet() {
    map = new HashMap<>();
}
  
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
  
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
  
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

add()方法

可以看到这三个方法都是直接调用的HashMap的实现。

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
  
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
  
public boolean contains(Object o) {
    return map.containsKey(o);
}

add其实就是调用HashMap的put方法，那么如何保证唯一性？

如果哈希值和key都一样，就会直接拿新值覆盖旧值，而HashSet就是利用这个特性来保证唯一性。

其实和HashMap就是一样的。

1 2	if (p.hash == hash && ((k = p.key) == key \|\| (key != null && key.equals(k)))) e = p;

contains方法（~~Get()方法~~ ）

hashset没有get方法，因为没有意义：不需要获取某个键值对应的value。

具体实现直接调用hashmap的containsKey()方法：

过程和hashmap的get方法过程差不多，返回为null则是不存在。
1
2
3
public boolean contains(Object o) {
return map.containsKey(o);
}

9. 1 HashSet如何检查重复？

把对象加⼊ HashSet 时，HashSet先计算对象的hashcode 值；
根据hashcode值计算出要加⼊的位置，同时也会与其他加⼊的对象的hashcode值作⽐教；
如果没有相符的hashcode，HashSet会假设对象没有重复出现；
如果发现有相同hashcode值的对象，这时会调用 equals() 方法来检查hashcode相等的对象是否真的相同，如果两者相同，HashSet就不会让加⼊操作成功。

9.2 【新】contains()方法在HashSet和ArrayList的实现区别？

Arraylist

因为底层是object数组，判断某个对象是否存在，其实是通过遍历来进行判断的。

 public boolean contains(Object o) {
        return indexOf(o) >= 0;//#1
    }

/* 返回指定元素在列表中第一次出现的索引，如果该列表不包含该元素，则返回-1。*/

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

Hashset

Hashset是hash值 && 遍历链表equals() 都相等，来判断的。

1 2	if (p.hash == hash && ((k = p.key) == key \|\| (key != null && key.equals(k)))) e = p;

10. comparable 和 Comparator的区别？

参考：https://www.cnblogs.com/xujian2014/p/5215082.html

Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。
例如Person类，实现Comparable接口，使得所有Person类对象可以按照各自年龄大小进行排序。
1
2
3
4
5
@Override
public int compareTo(Person p)
{
return this.age-p.getAge();
}
Comparator是比较器，我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。
Person类没有实现Comparable接口，该如何比较大小呢？我们可以新建一个类，让其实现Comparator接口，从而构造一个“比较器"。
1
2
3
4
5
@Override
public int compare(Person o1, Person o2)
{
return o1.getAge()-o2.getAge();
}
Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。。

11. 如何选用集合?

需要存储键值对：

Map接口的集合
- 需要排序时选择TreeMap
- 不需要排序时就选择HashMap
- 需要保证线程安全就选⽤ConcurrentHashMap

只需要存储元素，实现collection接口的集合，又分为：

需要保证元素唯一–Set接口的集合
- HashSet
不需要元素唯一–List接口结合
- 查找比较多：ArrayList
- 增删比较多：LinkedList

1.3.3 List

1.用过 ArrayList 吗？说一下它有什么特点？

自动扩容：当加入数据达到一定程度后，会实行自动扩容，即扩大数组大小；
底层实现：底层是使用数组实现，add(int,o)，添加到某个位置，那么可能会挪动大量的数组元素，并且可能会触发扩容机制；
线程不安全

2. ArrayList 与 Vector 区别呢?为什么要用Arraylist取代Vector呢？

线程安全： Vector线程安全，ArrayList 不是；
Vector耗时：Vector 类的所有方法都是同步的。可以由两个线程安全地访问⼀个Vector对象、但是⼀个线程访问Vector的话代码要在同步操作上耗费大量的时间。

3. Array & ArrayList不同点?

Array可以包含基本类型和对象类型，ArrayList只能包含对象类型 ；
Array大小是固定的，ArrayList的大小是动态变化的；
ArrayList提供了更多的方法和特性: addAll()，removeAll()，iterator()。

4. Arraylist 与 LinkedList 区别?

索引/插入：ArrayList按序号索引，索引快插入慢；LinkedList不是，索引慢，插入快；
内存方面： Arraylist 是线性连续存储，内存利用更低；LinkedList 是链表，内存利用更高（将内存零散空间串联），但也更占有内存（每个节点存储了两个引用）；
线程安全： ArrayList 和 LinkedList 都是不同步的，也就是都不保证线程安全；
底层数据结构： Arraylist 底层使用的是 Object数组； LinkedList 底层使用的是双向链表 数据结构；

JDK1.6之前为循环链表，JDK1.7取消了循环。

5. 【源码解读】说说ArrayList的扩容机制吧？为什么是扩容1.5倍？默认大小是多少。

逐源码分析扩容机制

先把回答写在下面：

ArrayList/vector默认大小都是10，但vectot扩容是2倍。

1. 扩容机制：

使用无参构造函数创建的数组长度为0，当第一次add后数组长度为10 ；如果继续add超过10后，也就是不满足minCapacity（最小需要容量） - elementData.length > 0 会触发扩容机制。将新容量更新为旧容量的1.5倍，若还是小于最小需要容量，那么就把【最小需要容量当作数组的新容量】。

最后检查设置的新容量是否大于最大容量MAX_ARRAY_SIZE ，进入hugeCapacity() :

如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8 。

2. 为什么是1.5倍？

因为，int newCapacity = oldCapacity + (oldCapacity >> 1)，所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！ 奇偶不同。

比如：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数。

ArrayList总览

ArrayList继承于AbstractList ，实现了List,RandomAccess,Cloneable,java.io.Serializable 这些接口。
1
2
3
4
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

}
- RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问；
- ArrayList 实现了Cloneable 接口 ，即覆盖了函数clone()，能被克隆；
- ArrayList 实现了 java.io.Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输。
ArrayList 核心源码解读（先耐心看一遍）

直接点击上面链接逐源码分析扩容机制查看。

【重点】JDK8 扩容机制解读

从构造函数说起

（JDK8）ArrayList 有三种方式来初始化 :

以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。
jdk8中的ArrayList的对象的创建类似于单例的懒汉式。JDK8的内存优化也值得我们在平时开发中学习。

 /**
  * 默认初始容量大小
  */
 private static final int DEFAULT_CAPACITY = 10;
     
 /**
  * 空数组（用于空实例）。
  */
 private static final Object[] EMPTY_ELEMENTDATA = {};
     
  //用于默认大小空实例的共享空数组实例。
   //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
     
 /**
  * 保存ArrayList数据的数组
  */
 transient Object[] elementData; // non-private to simplify nested class access
     
 /**
  * ArrayList 所包含的元素个数
  */
 private int size;
     
 /**
     
 /**
  * 带初始容量参数的构造函数。（用户自己指定容量）
  */
 public ArrayList(int initialCapacity) {
     if (initialCapacity > 0) {//初始容量大于0
         //创建initialCapacity大小的数组
         this.elementData = new Object[initialCapacity];
     } else if (initialCapacity == 0) {//初始容量等于0
         //创建空数组
         this.elementData = EMPTY_ELEMENTDATA;
     } else {//初始容量小于0，抛出异常
         throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
     }
 }
     
     
/**
 *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
 *如果指定的集合为null，throws NullPointerException。
 */
  public ArrayList(Collection<? extends E> c) {
     elementData = c.toArray();
     if ((size = elementData.length) != 0) {
         // c.toArray might (incorrectly) not return Object[] (see 6260652)
         if (elementData.getClass() != Object[].class)
             elementData = Arrays.copyOf(elementData, size, Object[].class);
     } else {
         // replace with empty array.
         this.elementData = EMPTY_ELEMENTDATA;
     }
 }

再看add方法

这里以无参构造函数创建的 ArrayList 为例分析。

JDK11 移除了 ensureCapacityInternal() 和 ensureExplicitCapacity() 方法

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

再看 ensureCapacityInternal() 方法

第2步（JDK7）可以看到 add 方法首先调用了ensureCapacityInternal(size + 1) 。

当要 add 进第 1 个元素时，minCapacity 为 1，在 Math.max()方法比较后，minCapacity 为 10。
然后开始调用 ensureExplicitCapacity() 方法

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

调用 ensureCapacityInternal() 进入ensureExplicitCapacity()这个方法

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //调用grow方法进行扩容，调用此方法代表已经开始扩容了
            grow(minCapacity);
    }

我们来仔细分析一下：

当我们要 add 进第 1 个元素到 ArrayList 时，elementData.length 为 0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法，所以 minCapacity 此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。
当 add 第 2 个元素时，minCapacity 为 2，此时 elementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入（执行）grow(minCapacity) 方法。
添加第 3、4···到第 9 个元素时，依然不会执行 grow 方法，数组容量都为 10。

直到添加第 10 个元素，minCapacity < elementData.length不成立。进入 grow 方法进行扩容。

elementData.length（实际容量）>= minCapacity（最小需要容量） , 执行 grow()

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！ 奇偶不同，比如：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数。

将新容量更新为旧容量的1.5倍，若还是小于最小需要容量，那么就把【最小需要容量当作数组的新容量】。

最后检查设置的新容量是否大于最大容量MAX_ARRAY_SIZE ，进入hugeCapacity() :
- 如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8 。

/**
    * 要分配的最大数组大小
    */
   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
     
   /**
    * ArrayList扩容的核心方法grow。
    */
   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;
      // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
      //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
       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);

设置完新容量 newCapacity ，进行Arrays.copyOf

Arrays的copyOf()方法传回的数组是新的数组对象，改变传回数组中的元素值，不会影响原来的数组。
- 第二个自变量指定要建立的新数组长度，如果新数组的长度超过原数组的长度，则保留数组默认值，例如：
使用 Arrays.copyOf()方法主要是为了给原有数组扩容。

contains()方法

就是遍历数组看是否存在该元素。

 public boolean contains(Object o) {
        return indexOf(o) >= 0;//#1
    }

/* 返回指定元素在列表中第一次出现的索引，如果该列表不包含该元素，则返回-1。*/

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

5.1 多线程操作ArrayList会出现什么错误？

从ArrayList的（1）添加元素（add/addAll）和（2）获取元素（get）两个角度来说：

多线程添加元素

假设此时minCapacity（最小需要容量）= 10 ，此时数组容量是10。A,B两个线程各需要添加若干元素，同时判断此时不需要扩容，后续可能就会发生数组越界。
多线程获取元素

一个线程正在修改某个元素，另外一个线程此时正在读，那么读到的就是修改前的元素，也就是脏数据。

5.2 arraylist可以存多少数据？

Integer.MAX_VALUE = 2147483647 。

arraylist底层是一个数组对象：Object[] arr = new Object[10]，数组的大小只能设置int类型。所以能存储2147483647 字节数据。

6. 说一下LinkedList底层原理？

参考：Java集合系列之三：LinkedList底层原理

LinkedList实现了List接口和Deque接口的，底层的双端链表结构使它支持高效的插入和删除操作，也具有队列的特性，非线程安全的。

相比ArrayList要简单很多，主要是双向链表那些操作。

底层结构

核心属性、构造方法和Node定义如下。

public class LinkedList<E>extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;   //LinkedList中存放的元素个数

    transient Node<E> first;  //头节点
    
    transient Node<E> last;   //尾节点

    //构造方法，创建一个空的列表
    public LinkedList() {}

    //将一个指定的集合添加到LinkedList中，先完成初始化，在调用添加操作
    public LinkedList(Collection<? extends E> c)     {
        this();
        addAll(c);
    }

// Node节点    
private static class Node<E> {
     E item;
     Node<E> next;
     Node<E> prev;

     Node(Node<E> prev, E element, Node<E> next) {
         this.item = element;
         this.next = next;
         this.prev = prev;
     }
 }

add() 方法

朴实无华的双向链表尾插法。获得当前最后一个节点最为当前节点的前置节点，同样把当前节点设置为前置节点的后置节点，然后把当前节点作为最后一个节点，因为只需要创建一个节点与前一个节点建立前后关系即可，时间复杂度是O(1)。

public boolean add(E e) {
    linkLast(e);
    return true;
}
  
void linkLast(E e) {
    // 获得当前最后一个节点作为前置节点，可能为空
    final Node<E> l = last;
    // 初始化当前节点
    final Node<E> newNode = new Node<>(l, e, null);
    // 把当前节点作为最后的节点
    last = newNode;
    // 第一次添加设置为第一个节点
    if (l == null)
        first = newNode;
    else
        // 把当前节点设置为前置节点的后置节点
        l.next = newNode;
    size++;
    modCount++;
}

add(int index,E e)

按索引插入元素，首先判断是不是第一个添加的元素，如果是的话，直接使用add()方法添加就可以了，如果不是则需要根据索引来遍历寻找链表上对应位置。
- 这里用了个小技巧，判断索引是在前半段还是在后半段，从短的那头开始遍历，找到之后，新建一个节点，建立新的前置节点和后置节点的关系。时间复杂度是O(n)，n为size/2。

get(int index)方法

get()方法是用的上面介绍过的node()方法，时间复杂度是O(n)，n为size/2。

 public E get(int index) {
     // 判断数组越界
     checkElementIndex(index);
     // 遍历寻找节点
     return node(index).item;
 }

// 获得被插入索引上的元素
Node<E> node(int index) {
// assert isElementIndex(index);
// 如果索引是在链表的前半段
if (index < (size >> 1)) {
    // 获得第一个节点
    Node<E> x = first;
    // 往后找到插入索引位置上的节点
    for (int i = 0; i < index; i++)
        x = x.next;
    return x;
}
// 如果索引是在链表的前半段
else {
    // 获得最后个节点
    Node<E> x = last;
    // 往前找到插入索引位置上的节点
    for (int i = size - 1; i > index; i--)
        x = x.prev;
    return x;
}

1.3.4 迭代器

1.请简单说明一下什么是迭代器？

Iterator提供了统一遍历操作集合元素的统一接口, Collection接口实现Iterable接口。

每个集合都通过实现Iterable接口中iterator()方法返回Iterator接口的实例, 然后对集合的元素进行迭代操作；
在迭代元素的时候不能通过集合的方法删除元素, 否则会抛出ConcurrentModificationException 异常. 但是可以通过Iterator接口中的remove()方法进行删除。

2.请你说说Iterator和ListIterator的区别？

遍历类型：Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List；
遍历方向：Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向；
功能区别：ListIterator实现了Iterator接口，并包含其他的功能

校招笔记（一）_Java_集合

1.3 集合

1.3.1 集合类

1.请说明Java集合类框架的基本接口有哪些？

2.（补充：举例说明）说说什么是fail-fast？

3.请说明List、Map、Set三个接口区分？

4.请讲讲你所知道的常用集合类以及主要方法？

1.3.2 Map & Set

1.请你介绍一下map的分类和常见的情况？

1.1 TreeMap的底层实现？

2.请问HashMap和Hashtable区别？

3.请问Map接口实现：HashMap、Hashtable和ConcurrentHashMap区别？

4.说一说红黑树特征？

5. hashmap的基本原理，扩容方式（rehash）？

5.1 为什么HashMap默认链表长度超过8转为红黑树，而不是6、7或9？

5.2 HashMap 多线程操作导致死循环问题？

5.3 说说HashMap的put方法？

5.4 说说HashMap的get方法？

5.5 【百度】rehash扩容时机？在插入前还是插入后？

5.6 hashmap在1.7版本之前为什么使用头插法？

5.7 为什么 HashMap 的负载因子设置成 0.75，而不是 1 也不是 0.5？

5.8 Hashmap 怎么处理key和value为null的情况？

6. Hashtable 源码分析

6.1 （容易忘）HashMap 和 Hashtable 的区别 ？

6.2 ConcurrentHashMap 和 Hashtable 的区别 ？

7. ConcurrentHashMap线程安全的具体实现方式/底层具体实现 ？

7.1 你知道 ConcurrentHashMap 的工作原理吗？

7.2 请问ConcurrentHashMap中变量使用final和volatile修饰有什么用呢？其中链表是final的next属性，那么发生删除某个元素，如何实现的？

7.3 HashTable与ConcurrentHashMap有什么区别，描述锁分段技术。

7.4 （阿里·淘特）ConcurrentHashMap1.8为什么不使用分段锁？

7.5 为什么1.8中 get() 方法不加锁？

7.6 为什么1.8不使用lock而是使用sync？

7.7 ConcurrenthashMap使用的时候有可能出现不安全的情况？

8. HashMap 和 HashSet区别 ？

9. 说说HashSet的基本原理？

9. 1 HashSet如何检查重复 ？

9.2 【新】contains()方法在HashSet和ArrayList的实现区别？

10. comparable 和 Comparator的区别？

11. 如何选用集合?

1.3.3 List

1.用过 ArrayList 吗？说一下它有什么特点？

2. ArrayList 与 Vector 区别呢?为什么要用Arraylist取代Vector呢？

3. Array & ArrayList不同点?

4. Arraylist 与 LinkedList 区别?

5. 【源码解读】说说ArrayList的扩容机制吧 ？为什么是扩容1.5倍？默认大小是多少。

5.1 多线程操作ArrayList会出现什么错误？

5.2 arraylist可以存多少数据？

6. 说一下LinkedList底层原理？

1.3.4 迭代器

1.请简单说明一下什么是迭代器？

2.请你说说Iterator和ListIterator的区别？

目 录

royhuang's blog

6.1 （容易忘）HashMap 和 Hashtable 的区别？

6.2 ConcurrentHashMap 和 Hashtable 的区别？

7. ConcurrentHashMap线程安全的具体实现方式/底层具体实现？

8. HashMap 和 HashSet区别？

9. 1 HashSet如何检查重复？

5. 【源码解读】说说ArrayList的扩容机制吧？为什么是扩容1.5倍？默认大小是多少。

目录