数组与集合区别，用过哪些？

  1. 数组是定长的，集合不是定长的，例如ArrayList是动态数组
  2. 数组存储的是基本数据类型和对象，而集合只能存储对象（这里也可以引申出为什么要有包装类，为了统一集合的操作需要把基本数据类型包装成对象，int变成Integer，但是这样也会有自动拆箱导致的性能问题）
  3. 数组可以随机访问，集合需要通过迭代器或者其他方法访问（其实还是由于包装了）

用过哪些：ArrayList,LinkedList,Vector,HashSet,TreeSet,BlockingQueue,HashMap.TreeMap,LinkedHashMap

说说Java中的集合？

Java的集合类分为两个大类，Collection接口实现的List，Set和Queue，以及Map接口。Collection存储的是单一元素，而Map存储的是键值对。

在Collection接口下：

  1. List是顺序的，主要实现类是ArrayList，底层基于动态数组，LinkedList，底层基于双向链表，Vector，是加了重度锁的有线程安全的顺序数据结构，由于性能一般已经很少用了
  2. Set是集合，存储的元素不能重复：HashSet基于HashMap（有待考究），TreeSet是基于红黑树，按照某种顺序有序的集合。
  3. QUeue是队列，了解较少

在Map接口下：

  1. HashMap：jkd1.7基于Entry+链表的形式，在1.8之后改成Node+链表+红黑树。线程不安全
  2. TreeMap：基于红黑树，可以根据key的大小排序
  3. LinkedHashMap：基于HashMap，但是内部维护了一个双向链表来指定顺序，1.7之前是循环链表，1.8以后是双向链表

Java中的线程安全的集合是什么？

在java.util包下的数据结构，也就是本身设计就是为了线程安全的：

  1. Vector：操作都用了synchronized方法，用copyOnWriteArrayList替代
  2. HashTable：也是加了重度锁的哈希表，性能不如concurrentHashMap

在1.8以后有Concurrent的包出现，带来了很多新的线程安全的集合

  1. ConcurrentHashMap：1.7之前是分段锁，把每个Segment都锁上，默认可以实现16个线程并发（前提是他们访问的这些数据都分布在16个不同的Segment上）。1.8以后是用了Node+链表+红黑树，锁的粒度变小了，只用synchronized锁住头节点，然后如果要添加到话用cas操作，大大减轻了锁的粒度，性能较好
  2. CopyONWriteArrayList：写时复制COW，指的是在写操作的时候赋值一份副本在副本上进行操作，最后再用新数组替换旧的数组，如果期间原数组有操作，就记录下来最后进行变更

Collections和Collection的区别

Collection是一个接口，如上面所述；Collections是一个工具类，提供了一系列静态方法来帮助完成集合的操作，比如sort

Collections还有一个方法可以让HashMap变成线程安全的集合，这个方法是给所有HashMap的方法加上synchronized关键字，这样效率是很低的，所以能用还是用ConcurrentHashMap吧

ArrayList和LinkedList的区别

  1. 底层数据结构不同：ArrayList基于的是动态数组自动扩容，LinkedList基于的是双向链表，都不是线程安全的
  2. 增删改查的时间复杂度不一样，ArrayList可以支持随机查询，但是增删都需要平均一半的时间o(n/2)，双向链表在头尾增删有比较高的效率，但是在中间添加也是有查询的时间复杂度（注意，这里ArrayList实现了RandomAccess接口，表示可以支持随机访问，但是这个接口是空的，仅仅作为一个标记）
  3. 空间占用，ArrayList是连续的数据结构，数据密度大，而LinkedList可以是离散的，由于要存储下一个数据的指针，需要额外的空间，数据密度不大

ArrayList的初始化

ArrayList有两种初始化方式（还有一种是输入集合的，考察的比较少）：

  1. 无参构造方法，初始化为一个默认的DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空数组，并没有分配具体对象，到后面grow操作才会有对象
  2. 有参构造方法，如果输入的长度不为0，直接就new一个Object数组，如果输入的长度为0，初始化为另外一个EMPTY_ELEMENTDATA的空数组

为什么要有两个这个空数组呢，是因为需要区分是否为有参构造函数，在后续的扩容操作中只有DEFAULTCAPACITY_EMPTY_ELEMENTDATA才会分配默认值。这个在后续扩容操作有用处

ArrayList的扩容机制

注意区分数组长度elementData.length和数据量size

  1. 再添加一个元素之前，先检查下一个位置是否存在，进行检查，传入参数是当前数据量+1；检查的目的是为了确定数组长度能否支持下一个数据的添加
  2. 在检查前针对无参构造方法有一个当前需要的最小长度的计算，由于初始化的时候长度没有确定，这个时候需要的最短长度就是默认的10；其余的方法容量计算的结果就是传入参数直接输出（即数据量+1）
  3. 进行检查，如果这个需要的最短长度大于了数组长度，就需要扩容了
  4. 扩容：非0情况下是1.5倍的原长度，如果原长度为0，则新长度为刚刚计算得到的最小长度。

引申问题1:new ArrayList()和new ArrayList(0)第一次扩容的长度是多少，由刚刚的分析可知，有参在最小长度计算得到的长度为0+1=1，无参为10，所以说第一次扩容分别为10和1
引申问题2:new ArrayList(10)在添加一个元素的时候扩容了几次，没有扩容，因为在构造函数里面已经有分配空间，而且1<10，不会触发grow

ArrayList是线程安全的吗？如果想用线程安全的List怎么操作

ArrayList不是线程安全的，主要是因为在加入数据的时候++操作不是原子性的，首先先说明加入数据的逻辑，总结为如下：

  1. 先进行上面所述的校验和扩容
  2. 再在当前size的位置添加元素（引发线程安全）
  3. 最后将当前的size+1

有以下三种情况会引发线程安全问题：

  1. 出现null值，线程a添加2位置的元素，此时线程b也同时进来想要添加2位置的元素，线程a添加完成后没有立刻size++，线程b也存到当前位置，最后两个都size++，此时size为4，2的位置由于重复冲掉了一个数据，3的位置直接就是null。
  2. 出现溢出：当前长度为9，容量是10，两个线程同时在9的时候添加，就会出现溢出
  3. size和put的次数不一样：这个出现的最多，也是因为size++

如何使用线程安全的list：

  1. Collections.synchronizedList(arrayList)，相当于在方法上全部加上synchronized，效率低
  2. CopyOnWriteArrayList：写操作用reentrantlock来保证不会出现上述1和3的线程安全问题，临界区内执行复制，不会影响读操作，存入完成后进行地址替换。虽然这种方法确实是线程安全的，但是每次写操作都要进行上锁和复制数组，在写多读少的情况下肯定是不好的。只适用于读多写少
  3. Vector：效率更低，已经淘汰

LinkedList的机制

双向链表，查询数据的复杂度为o(n)，在首尾添加数据的复杂度为o(1)

HashMap的数据结构

HashMap的结构经历了大的改版，在jkd1.7HashMap是基于Entry数组的，哈希冲突用拉链法解决，就形成了Entry数组+链表的结构；在jkd1.8以后，拉链超过一定的数量转化成查询效率更高的红黑树，形成了Entry数组+链表+红黑树的结构

解决哈希冲突的方法（复习）：

  1. 拉链法：把冲突的都还是放在原来的位置
  2. 开放选址法：线性探测法（顺序往后面找），二次探测（1，4，9这样找）
  3. 再散列法：把冲突的再进行散列
  4. 哈希桶扩容：减小碰撞的可能性

HashMap的put过程

  1. 首先会判断是否初始化，如果没有初始化（比如空参构造方法）就resize
  2. 按照hash方法计算哈希值，这个哈希值的计算是通过hashcode和高位的异或运算得出，融合了高位和低位信息的hash函数，效果会更好
  3. 与当前Entry数组进行取余操作，这里的取余是位运算，hash&(n-1)，hashmap规定n必须是2的整数倍，也就是说n-1为最高位为0，其余都是1的二进制数，与hash进行与运算就能得到余数，位运算比%的效率高
  4. 得到了应该存储的Entry号，判断这个Entry上有没有别的元素，如果没有就直接写上去（这里还要判断是不是一个key，如果是一个key的话需要替换值）
  5. 如果有别的元素，首先判断是不是红黑树的节点，如果是红黑树的节点就走红黑树的添加逻辑
  6. 如果不是红黑树，是链表，在查找的过程中还需要看key是否重复，如果是重复的还需要覆盖v，如果没有重复的key就添加到表尾（尾插法，这也是1.8与1.7的一个区别，1.7的尾插会出现一些并发安全问题）
  7. 如果加入之后大于红黑树的阈值，还需要转换成红黑树
  8. 最后检查size，如果大了就需要resize

HashMap如何检查重复

主要是靠这一段代码：

1
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
  1. 首先判断两个的hash值，hash值相同说明碰撞了
  2. 再判断key的地址是不是一个，如果是基本数据类型那就是比较本身，如果是字符串或者是对象就比较地址
  3. 再比较内容，如果内容是一个那就是相同的，比如两个不同地址的字符串但是内容都是“abc”，再map这里也是一个

HashMap的resize机制

  1. 首先进行新数组的长度和阈值的计算，如果当前数组有长度和阈值，那就都乘2，如果有阈值但是没有长度（或长度为0，这种情况可能是有参构造函数造成的，在构造函数中只有这个阈值的初始化）就把要最小数组长度设置为阈值（此阈值不是那个乘负载因子的阈值），最后就是无参构造函数的，直接设置最小数组长度为默认的16
1
2
3
4
5
6
7
8
9
10
11
public HashMap(int initialCapacity, float loadFactor) {
     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
     if (initialCapacity > MAXIMUM_CAPACITY)
         initialCapacity = MAXIMUM_CAPACITY;
     if (loadFactor <= 0 || Float.isNaN(loadFactor))
         throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
     this.loadFactor = loadFactor;
     // 初始容量暂时存放到 threshold ，在resize中再赋值给 newCap 进行table初始化
     this.threshold = tableSizeFor(initialCapacity);
 }
  1. 根据最小数组长度和阈值进行扩容，进行新的哈希值计算
  2. 链表上的元素根据e.hash&oldCap，得到高位是0或者1，如果是1就放在新加的数组后面：

  1. 红黑树也根据哈希值按照上述方法进行分裂，小于6个点的退化为链表’

为什么HashMap要用2的整数倍

  1. 位运算的取余操作
  2. 扩容机制巧妙将0，1分开

HashMap怎么样才能不扩容

只要满足大于扩容阈值就行了，如果预计有100个数据要进入hashmap，那就做一个（100/负载因子）+1这么大的数组，这样可以保证不会触发扩容，当然初始化的resize还是有的

HashMap的线程安全问题

并不是安全的，主要会有以下几个问题：

  1. 在jkd1.7，由于是头插法，在数据迁移的过程中可能会出现死循环的问题，有两个数据A->B，线程1和2同时操作当前快照，线程1已经操作了这两个节点变为B->A，线程2的当前节点为A，next为B，此时线程2进行操作，插入A节点，把当前节点换为B，B的next也是A，这样就循环了
  2. 此外还是会有跟ArrayList那种出现索引位置重复，比如当前某个Entry上没有元素，两个hash冲突的就可能会覆盖
  3. 还有size与put操作次数不一致的问题

什么方法解决？

  1. concurrentHashMap：一种基于多段锁的Map
  2. HashTable：直接锁整个表

concurrentHashMap和HashTable的区别

concurrentHashMap在jdk1.7以前是segment+hashEntry+链表构成，给每个segment上锁，默认支持16的并发（前提是每一个线程访问的数据都不在一个segment上）；在jdk1.8以后通过synchronized+cas+node完成了并发控制，直接在hashmap进行锁操作，用synchronized锁住头节点，cas锁住添加操作。HashTable是方法全加synchronized的哈希表，效果肯定是不如cas的

concurrentHashMap什么时候用synchronized什么时候用cas，当Entry是空节点的时候就用自旋锁，当不为空就不用

HashSet

HashSet是基于HashMap的，由于HashMap的特性会替换重复的key，HashSet直接把当前元素作为key，这样就可以达到去重的目的

未完待续。。。。。