常见集合框架底层原理

常见的集合有哪些

• Java集合类主要由两个接口Collection和Map派生出来的，Collection有三个子接口: List、 Set、Queue
  • List代表了有序可重复集合，可直接根据元素的索引来访问
  • Set代表了无序集合，只能根据元素本身来访问
  • Queue是队列集合
  • Map代表的是存储key-value键值对的集合，可根据元素的kye来访问value
• 集合中常见的实现类有ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap等

List、Set、Map的区别

• List 以索引来存取元素，有序的，元素是允许重复的，可以插入多个null

• Set 不能存放重复元素，无序的，只允许一个null

• Map 保存键值对映射

• List 底层实现有数组、链表两种方式，Set、Map 容器有基于哈希存储和红黑树两种方式实现

• Set 基于 Map 实现，Set 里的元素值就是 Map的键值

• 常见的集合框架

  • ArrayList

    • ArrayList采用的是数组去保存元素，而且有序，元素可以重复
    • 插入、删除元素的时间复杂度是O(n)，查找、替换的时间复杂度是O(1)
    • ArrayList初始容量大小为10
    • ArrayList的扩容机制
      • 计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去，默认情况下，新容量扩容至原来容量的1.5倍
    • 问题: 怎么在遍历ArrayList时移除一个元素
      • foreach删除会导致快速失败问题，可以使用迭代器的remove方法

  • LinkedList

    • 采用双向链表结构
    • 元素可重复并且无序
    • 插入、删除时间复杂度O(1)，查找、替换时间复杂度O(n)
    • 问题: 说一下ArrayList和LinkedList的区别
      • 首先它们的底层数据结构不同，ArrayList是基于数组实现的，LikedList是基于链表实现的
      • 由于底层数据结构不同，ArrayList适合随机查找，LinkedList适合删除和添加，他们操作的时间复杂度也不同
      • ArrayList和LinkedList都实现了List接口，但是LinedList还额外实现了Deque接口，所以LinkedList可以当做队列使用

  • HashMap

    • 默认容量16

    • JDK7采用数组 + 链表，利用的是头插法

    • JDK8采用数组 + 链表 + 红黑树，利用的是尾插法

      • 问题: 什么是红黑树

        • 
        • 每个节点非红即黑
        • 根节点总是黑色的
        • 如果节点是红色的，那么它的子节点必须是黑色的，反之不一定
        • 每个叶子节点都是黑色的空节点
        • 从根节点到叶子节点或空子节点的每条路径，必须包含相同数目的黑色节点

      • 问题: 为什么JDK8采用尾插法了而不是继续用头插法

        • https://www.processon.com/view/link/62f890e10791297750986114
        • 多线程情况下，扩容的时候可能会导致产生循环链表，导致后面再去头插法无法插入，从而死循环造成CPU满载
        • 举例
          • 两步骤: 数组扩容和数据重新头插入
          • 线程1: 扩容前A->B 扩容之后B->A，此时CPU将时间片给线程2
          • 线程1: A->B 完成了数组扩容但是没有完成数据重新插入
          • 线程2: B->A 两步都完成了
          • 最终导致A->B、B->A循环指向对方，后面再去头插法就无法插入了

      • 问题: 为什么会采用红黑树

        • 因为链表查询的时候可能因为链表过长降低查询效率，所以采用了红黑树提升查询效率

      • 问题: HashMap的工作原理

        • HashMap底层是hash数组和单向链表实现，数组中的每个元素都是链表，JDK7通过key、value封装Entry对象，JDK8是Node对象，HashMap是通过put方法存储、get方法获取.
        • 存储对象时:
          • 首先通过key通过hash方法计算hash值确定数组下标
          • 如果数组下标位置元素为空，就将key和value封装成Entry对象，在JDK7是Entry对象，在JDK8是Node对象
          • 如果数组下标位置元素不为空
          • 如果是JDK7会先判断是否需要扩容，如果不扩容就会生成Entry对象并且使用头插法添加当当前位置的链表中，此时还会判断对应的key是否存在，如果存在就会更新value
          • 如果是JDK8会先判断Node的类型是红黑树节点还是链表节点
            • 如果是红黑树节点，就将key和value封装成一个红黑树节点添加到红黑树中去，在这个过程中还会判断红黑树中是否存在相同的key，如果存在就更新value
            • 如果是链表节点，就将key和value封装成一个链表节点添加到链表的尾部，因为尾插法需要遍历整个链表，此时也会去判断是否存在相同的key，如果存在就更新vlaue，当遍历完整个链表之后会得到整个链表的长度，会判断是否超过8并且数组长度超过64，如果超过了就会将链表转换成红黑树
            • 将key和value封装成Node放到红黑树或链表中去，再判断是否需要进行扩容，如果不需要就结束
        • 获取对象时:
          • 通过hash方法计算key的hash值从而确定元素所在链表的数组下标
          • 顺序遍历数组，通过equals方法查找key数值相同的元素

    • hashcode通过字符串算出ascll码进行取模算出哈希表的下标

      • 问题: 如何解决hash冲突的
        • 如果发生了hash冲突，采用链表解决

    • 问题： 扩容因子为什么是0.75

      • 一般来说，默认的负载因子提供了一个很好的时间和空间成本的平衡

    • 问题: JDK7中的HashMap与JDK8中的HashMap的区别

      • JDK7采用的是数组 + 链表，JDK8中新增了红黑树，JDK8是通过数组 + 链表 + 红黑树来实现的
      • JDK7采用的是头插法，JDK8采用的是尾插法
      • JDK8中因为使用了红黑树保证了插入和查询的效率，所以实际上JDK8中的Hash算法实现的复杂度降低了
      • JDK8中数组扩容的条件也发生了变化，只会判断当前元素个数是否超过了阈值，而不再判断当前put进来的元素对应的数组下标位置是否有值
      • JDK7中是先扩容再添加元素，JDK8中是先添加元素再扩容

    • 问题: JDK8中的HashMap链表转变为红黑树的条件是什么

      • 链表中的元素为8个或超过8个
      • 同时还要满足当前数组的长度大于等于64才会把链表转变为红黑树
        • 因为链表转变为红黑树主要是为了解决链表过长产生的查询效率慢的问题，而如果需要解决这个问题，也可以通过数组扩容，把链表缩短就行，所以数组长度还不太长的时候，可以先通过数组扩容来解决链表过长的问题

    • 问题: HashMap的扩容流程

      • HashMap的扩容指的就是数组的扩容，因为数组占用的是连续内存空间，所以数组的扩容其实只能新开一个新的数组，然后把老数组上的元素转移到新数组上面来，这样才是数组的扩容
      • 在HashMap中也是一样，先新建一个2倍数组大小的数组
      • 然后遍历老数组上的每一个位置，如果这个位置上是一个链表，就把这个链表上的元素转移到新数组上去
      • 在这个过程中就需要遍历链表，当然JDK7和JDK8在这个实现时是不一样的
        • JDK7就是简单的遍历链表上的每一个元素，然后按照每个元素的hashcode结合新数组的长度重新计算一个下标，而重新得到的这个数组下标是不一样的，这样子就达到了一种效果，就是扩容之后，某个链表会变短,这也就是扩容的目的，缩短链表长度,提高了查询效率
        • JDK8中，因为涉及到红黑树，这个其实比较复杂，JDK8中其实还会用到一个双向链表来维护红黑树中的元素，所以JDK8中在转移某个位置上的元素时，会去判断如果这个位置是一个红黑树，那么会遍历该位置的双向链表，遍历双向链表统计哪些元素在扩容之后还是原位置，哪些元素在扩容之后在新位置，这样遍历完双向链表之后，就会得到两个子链表，一个放在原下标位置，一个放在新下标位置，如果原下标位置或新下标位置没有元素，那么红黑树就不会拆分，否则就会判断这两个子链表的长度，如果超过8，就转成红黑树放到对应的位置，否则把单链表放到对应的位置
        • 元素转移完之后，再把新数组对象赋值给HashMap的table属性，老数组被回收

    • 问题: HashMap的put流程

      • 如果table没有初始化就先进行初始化过程
      • 使用hash算法计算key的索引
      • 判断索引处有没有存在元素，没有就直接插入
      • 如果索引处存在元素，则遍历插入，有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入
      • 链表的数量大于阈值8，就要转换成红黑树的结构
      • 添加成功后会检查是否需要扩容

    • 流程: HashMap流程

      • https://www.processon.com/view/link/62f8eccf5653bb5e82ca67af

  • ConcurrentHashMap

    • 并发安全的HashMap，比HashTable效率更高

    • JDK7采用ReentrantLock全局加锁解决并发

    • JDK8采用CAS + synchronized并且只对Node节点加锁，锁粒度更细

    • 问题: ConcurrentHashMap是如何保证并发安全的

      • JDK7中是通过 ReentrantLock + CAS + 分段的思想来保证并发安全的
        • 在JDK7的ConcurrentHashMao中首先有一个segment数组，存的是Segment对象，Segment相当于一个小HashMap，Segment内部有一个HashEntry数组也有扩容的阈值，同时Segment继承是ReentrantLock，同时Segment中还提供了get、put等方法，比如Segment的put方法一开始就会加锁，加到锁之后才会把key、value存到Segment中去，然后释放锁
        • 同时在ConcurrentHashMap的put方法中，会通过CAS的方式把一个Segment对象存到Segment数组中，同时因为一个Segment内部存在一个HashEntry数组，所以和HashMap对比来看，相当于分段了，每段里面是一个小HashMap，每段公用一把锁，同时在ConcurrentHashMap的构造方法中可以设置分段的数量，叫做并发级别concurrencyLevel
      • JDK8中ConcurrenHashMap是通过 synchronized + CAS实现的
        • 在JDK8中只有一个数组就是Node数组，Node就是key、value、hashcode封装出来的对象，和HashMap的Entry一样，在JDK8中通过对Node数组的某个下标位置的元素进行同步，达到下标位置的并发安全，同时内部也利用了CAS对数组的某个位置进行并发安全的赋值

    • 问题: JDK8中的ConcurrentHashMap为什么使用synchronized来进行加锁

      • JDK8中使用synchronized加锁时，是对链表头节点和红黑树根节点来加锁的，而ConcurrentHashMap会保证数组中某个位置的元素一定是链表的头结点或红黑树的根节点
      • JDK8中的ConcurrentHashMap在对某个桶进行并发安全控制时，只需要使用synchronized对当前那个位置的数组的元素进行加锁即可，对于每个桶只有获取到了第一个元素的锁才能操作这个桶，不管这个桶是链表还是红黑树
      • JDK7中使用ReentrantLock来加锁，因为JDK7中使用了分段锁，所以对于一个ConcurrentHashMap对象而言，分了几段就得有几个对象锁，而JDK8中使用synchronized关键字来加锁就会更加节省内存，并且JDK8的synchronized与Lock性能基本持平了

    • 问题: JDK8中的ConcurrentHashMap有一个CounterCell，你是如何理解的

      • CounterCell是JDK8中用来统计ConcurrentHashMap中所有元素个数的，在统计ConcurrentHashMap时，不能直接对ConcurrentHashMap加锁然后再去统计，因为这样会影响put等操作，在JDK8中使用的是CounterCell + baseCount来辅助进行统计
      • baseCount是ConcurrentHashMap的一个属性，某个线程在调用ConcurrentHashMap对象的put操作的时候，会先通过CAS去修改baseCount的值，如果CAS修改成功就计数成功，如果CAS修改失败，就会从CountCell数组中随机选一个CounterCell对象，然后利用CAS去修改CountCell对象中的值，因为存在CounterCell数组，所以当某个线程要计数的时候，先尝试CAS去修改baseCount的值，如果没有修改成功，就从CounterCell数组中随机取一个CounterCell对象进行CAS计数，这样在计数时提高了效率
      • 所以ConcurrentHashMap在统计元素个数的时候，就是所有元素的个数 = baseCount + CounterCell中的value

    • 流程: ConcurrentHashMap流程

      • 

  • HashSet

    • 元素不可重复，而且无序
    • 底层采用HashMap实现

  • HashMap常见面试题可参考: https://mp.weixin.qq.com/s/547b1ivm-sAMfMqposrU0Q

  • 问题: 谈一下ThreadLocal

    • ThreadLocal叫线程本地变量，当使用ThradLocal维护变量时，ThreadLocal为每个使用该变量的线程提供独立的变量副本，所以每个线程都可以独立地改变自己的副本，而不会影响其他线程
    • ThreadLocal原理
      • 每个线程都有一个ThreadLocalMap，Map中元素的键为ThreadLocal，而值对应线程的变量副本
    • ThradLocal并不是用来解决共享资源的多线程访问的问题，因为每个线程中的资源只是副本，并不共享，因此ThreadLocal适合作为线程上下文变量，简化线程内传参
    • 问题: ThreadLocal使用场景
      • 每个线程需要有自己单独的实例而且在多个方法中共享实例，也就是同时满足实例在线程间的隔离与方法间的共享，比如每个线程都有自己单独的session，就可以使用ThreadLocal
    • 问题: ThreadLocal内存泄露的原因
      • 问题: 什么是内存泄露
        • 使用的对象(如HashMap)长时间没有及时处理，导致数据越存越多，一直占用老年代空间，时间久了就会触发FullGC，甚至因为老年代达到阈值，回收不完而导致OOM，这就是一种内存泄露
      • 每个ThreadLocal都有一个ThreadLocalMap的内部属性，map的key为ThreadLocal并且定义为弱引用，而value是强引用类型。
      • GC的时候会自动回收key，而value的回收取决于Thread对象的生命周期，一般会通过线程池的方式复用Thread对象来节省资源，这也就导致了Thread对象的生命周期比较长，这样便一直存在一条强引用链(Thread->ThreadLocalMap->Entry->Value)，随着任务的执行，value就有可能越积越多，最终导致OOM内存泄露
      • 解决方法
        • 每次使用完ThreadLocal就remove，手动将对应键值对进行删除，从而避免内存泄露
      • 问题: 怎么实现父子线程之间变量副本的通信
        • ThreadLocal只能作为线程的本地变量副本，但是无法进行父子线程之间的传递
        • InheritableThreadLocal可以进行方法内的父子线程传递
          • InheritableThreadLocal通过重写，getMap和createMap让本地变量保存到了具体线程InheritableThreadLocals变量里面，那么线程在通过InheritableThreadLocal的类实例的set和get方法设置变量时，就会创建当前线程的InheritableThreadLocals变量
          • 当父子线程创建子线程的时候，构造函数会把父线程中InheritableThreadLocals变量里面的本地变量复制一份保存到子线程的InheritableThreadLocals变量里
        • 引申: 当处于线程池中的线程进行父子线程通信时就会失效，这里需要引入第三方框架，使用 TransmittableThreadLocal专注于解决线程池中上下文无法传递的问题
          • 可能产生的问题
            • 线程池中的线程进行创建后会把父线程的上下文设置到新建线程中，但是核心线程是不会被销毁的，换句话说不会新建，则不会刷新上下文
              • 如何解决
                • 先创建线程池，然后通过ttl进行修饰，这样每次调用的时候ttl会进行抓取当前父线程中的上下文刷新到子线程中，不管当前线程是否新建