集合相关问题

1. Java有哪些集合框架？
   Java的集合框架主要包括两个集合类型的容器：集合（Collection）和图（Map）。Collection存储的是一个元素集合，Map存储的是<key, value>的映射。Collection接口又有3个子类型：List、Set和Queue，再下面是一些抽象类，最后是具体实现类，常用的有ArrayList、LinkedList、List、LinkedHashSet、HashMap、LinkedHashMap。
2. 介绍一下List接口？
   List接口存储的是一个有序的集合，可以准确的控制每个元素插入的位置，能够通过索引访问List中的元素，List是能存储同一类型的对象，但可以有重复。
3. 介绍一下Set接口？
   Set接口大致与List一致，区别是Set存储的是不重复的元素，而且是无序的。

HashMap

1. 介绍HashMap的实现？
   https://blog.csdn.net/qq_40118851/article/details/82804510
   HashMap是通过数组+链表组成。Entry数组是HashMap的主干，每一个Entry包含一个Key-Value的映射。链表是为了解决Hash冲突，插入操作时，如果定位到数组的Entry已经存在链表，则遍历链表，如果存在相同的节点，则更新该节点，否则在链表末新增节点；对于查找操作，仍需遍历链表，时间复杂度为O(n)。如果定位到的Entry不包含链表，则直接返回Value，时间复杂度为O(1)。所以链表的长度越短，HashMap的性能越好。
   HashMap的结构

2. HashMap存储位置的确定流程？

   
   

3. 为什么HashMap的长度一定是2的次幂？
   a. 扩容后的数组长度为原数组的2倍，在计算新数组中的存储位置时可以保证length-1的低位全为1，这样在计算h&(length-1)的时候，只要保证最左位差异为0，就能保证的到的新数组索引和老数组索引一致，大大减少了原数组中已经散列良好的Entry的位置调换。

   
   避免改变Entry之间的位置
   

   b. 在计算h&(length-1)的时候，h的高位不会对结果产生影响。数组的长度为2的次幂，可以保证length-1的低位全为1，那么要定位到相同的位置，h的低位只能有一种组合，降低哈希冲突的几率。

   
   h的高位不会对结果产生影响
   c. 如果length-1的低位不全为1，那么会增加哈希冲突的几率，而且数组的一部分位置会用不上。
4. HashMap扩容？
   当size大于阀值的时候进行扩容，扩容需要新建一个size为原来两倍的数组，并将原来数组里面的元素传输过去。在多线程情况下，会造成闭合链表，从而导致CPU 100%。
   JDK8中，HashMap的底层数据结构变为数组+链表+红黑树，当链表长度大于8时，会将链表变为红黑树，以空间换时间，将查询时间复杂度变为O(logn)。
5. 为什么JDK8中HashMap不是线程安全的？
   多个线程对HashMap插入或更新同一个元素时，只会保存最后一个线程的结果。
   JDK8中解决了多线程扩容HashMap会造成循环链表的情况，但是元素不是volatile的，线程不会即时地将更新的元素刷到主内存中，其他线程读取时会读到旧的数据。
6. HashMap的get()方法？
   首先使用Key对象的HashCode找到数组中的Buket位置，然后判断Buket中是链表还是红黑树，并进行相应的查找，使用equals()方法找到正确的键值对。
7. 什么时候需要重写equals()和hashCode()?
   当Key为对象时必须重写hashCode()和equals()方法。默认的hashCode()方法使用对象在内存中的地址作为对象的hash值，当两个具有相同意义的对象进行比较时，地址不同会导致计算出的hash值不同。重写equals()保证两个对象具有相同的意义。
   重写了equals()方法后，一般要重写hashCode()方法，保证相同意义的对象具有相同的hash值。
8. 同步HashMap？
   使用Collections.synchorizeMap(hashMap)或者ConcurrentHashMap
9. HashMap和HashTable？

ConcurrentHashMap

1. 分段锁机制？
   ConcurrentHashMap中保存了一个Segment数组，即将ConcurrentHashMap分为多段，在执行put操作的时候，先通过hash算法定位到哪一个Segment，然后将该Segment加锁即可。
   HashMap要实现线程安全，则要用过Collections.synchorize(hashMap)来实现，在进行操作时会锁住整个HashMap，效率低下。

2. 数据结构？
   JDK7:
   ConcurrentHashMap定义了一个Segment<K, V>[]数组实现分段存储，每个Segment保存了一个HashEntry<K, V>[]数组，HashEntry为一个链表。Segment继承了ReentrantLock对每个分段进行加锁。

   
   ConcurrentHashMap数据结构
   

   JDK8:
   使用与HashMap一样的数据结构：数组+链表+红黑树。包含一个Table数组，其类型为一个Node数组，Node继承自Map.Entry<K, V>的链表，当链表长度大于8时转为红黑树，红黑树size小于6时转为链表。
   HashEnrty的数据类型：

static final class HashEntry<K,V> {  
     final K key;  
     final int hash;  
     volatile V value;  
     final HashEntry<K,V> next;  
 } 

3. get操作？
   JDK7和JDK8类似：先用hash算法定位到Segment，然后定位HashEntry，不加锁，采用UNSAFE.getObjectVolatile()，保证每次获得最新的数据。
4. put操作？
   JDK7:
   先通过hash算法定位Segment，如果Segment为空，则并发安全得创建Segment；如果不为空，则对Segment上锁，然后通过Hash算法定位到对应的HashEntry，接着遍历整个链表，如果查询到key值，插入即可；如果没有查询到，则调用rehash()对Segment扩容为原来的2倍，然后插入。插入以后Segment的count属性加1。
   JDK8:
   计算key的hash值，并获取对应的Node节点，有几种情况：
   1). table为空，初始化table，然后再次获取Node的位置；
   2). table不为空，但是没有找到key对应的Node节点，直接插入一个新的节点，不用加锁；
   3). table不为空，key对应的节点也不为空，但需要扩容，则扩容再插入；
   4). 其他情况，直接插入新的Node节点，需要通过synchronize加锁。
   插入之后要判断对应的Node是否需要改变结构，链表长度大于8升级为红黑树。
   最后调用addCount()记录table中元素的数量。
5. size？
   JDK7:
   一开始不对Segment加锁，直接将所有Segment元素中的count相加，计算两次，如果结果一致则直接返回，如果不一致则将所有的Segment加锁，然后将所有Segment的count相加，再返回。
   JDK8:
   在添加和删除操作时，会通过CAS操作更新ConcurrentHashMap中的baseCount属性值来统计元素个数，但是CAS操作可能失败，因此ConcurrentHashMap还维护了一个CounterCell数组来记录CAS操作失败时的个数。ConcurrentHashMap为baseCount和CountCell的总和。

备注：纯属个人学习