Java容器基础知识

三、容器

1. list、map、set区别

   • List

     List集合代表一个元素有序、可重复的集合，集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素 。

   • Set

     Set集合不允许包含相同的元素、无序的集合，如果试图把两个相同的元素加入同一个Set集合中，则添加操作失败，add()方法返回false，且新元素不会被加入。

   • Map

     Map是存储键值对（key-value）这样具有映射关系的数集合，Map的key不允许重复，value是允许重复的。

   • Queue

     用于模拟队列这种数据结构，队列通常是指“先进先出”(FIFO，first-in-first-out)的容器。队列的头部是在队列中存放时间最长的元素，队列的尾部是保存在队列中存放时间最短的元素。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。

2. linkedList和arryList区别

   1. ArryList

      底层是数组实现的，是一个动态数组，随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。

      简述扩容机制：

      //https://www.cnblogs.com/baichunyu/p/12965241.html
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      

      将oldCapacity右移一位，其效果相当于oldCapacity/2，我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍。如果扩为1.5倍还不满足需求，直接扩为需求值。

      ArryList 扩容的话一个重要的方法就是grow()方法。当add第一个元素，此时list是空的，length为0，发生一次扩容，此时lenth为10，这是默认容量。当要添加第11个元素时，进入grow方法进行扩容，每次扩容变为原来的1.5倍左右。调用的的是Arrays.copyOf(原数组，新容量)方法。

   2. LinkedList

      底层是一个双向链表，它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。LinkedList可以当作队列和栈使用。

      set()和get()这两个函数都调用了Node<E> node(int index) 函数，该函数会以O(n/2)的性能去获取一个节点，判断index是在前半区间还是后半区间，如果在前半区间就从head搜索，而在后半区间就从tail搜索。而不是一直从头到尾的搜索。如此设计，将节点访问的复杂度由O(n)变为O(n/2)。

   3. 区别

      • ArrayList增删慢，查找快；LinkedList增删快，查找慢
      • 对ArrayList和LinkedList而言，在列表尾部增、删一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素；而对LinkedList而言分配一个内部Entry对象，进行链接。
      • 在ArrayList的中间插入或删除一个元素意味着这个数组中剩余的元素都会被移动，需要重新排序，效率会比较低(目标元素越靠前，效率越低)；而在LinkedList的中间插入或删除一个元素的开销是固定的。
      • ArryList可以通过数组下标高效的增加或删除元素；LinkedList不支持高效的随机元素访问，它需要移动指针依次遍历。
      • ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
      • 可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,使用LinkedList性能会好一些。

   //底层实现
   //https://www.cnblogs.com/baichunyu/p/12965241.html
   

3. HashMap和ConcurrentHashMap实现原理以及区别

   1. HashMap

      • put（）和resize（）

        jdk1.7 及以前，HashMap 由数组+链表组成，从 jdk1.8 起，HashMap 是由数组+链表/红黑树组成。那么HashMap常用的就是put、get方法了，我先从put方法讲起。put中核心的就是putval()，putval()中有一个hash()这个方法，这个方法的话就是对key进行哈希hash()处理，首先调用hashCode()获得key的hashcode值h，在让它异或上 h无符号右移 16 位的结果（就是除以16取余），这样做的目的是为了让 key 的 hash 值的高 16 位也参与运算，来降低hash冲突的概率。如果直接用原始的HashCode计算的话：(n - 1) & hash，正常 HashCode 的 size 不会太大，高 16 位参与不到计算位置的运算里。
        根据hash算法得到hash值来确定在数组的索引位置，如果该位置没元素的话，则直接将该键值对存放在该位置处，如果该位置已经有数据了，判断该位置的node节点的key与put进来的对象的key是否一样，是则直接替换掉，就是覆盖原来的value。否则的话就遍历链表，找到了一样的元素就做替换操作，没有的就插入链表，jdk1.7这里采用的是头插法。在jdk1.8的中话，采用尾插法，另外它会在插入节点后判断链表的长度是否大于8，当链表长度大于8，但数组桶的长度<64时，只会发生扩容，当链表长度大于8，并且数组桶的长度>64时，才会发生树化。还有就是在确定了数组下标，准备put对象之前，会进行一次判断是树还是链表。最后，它会对size也就是实际存在的键值对数量进行判断，当它>threshold阈值时，也会进行resize()扩容。这里谈到了一个方法扩容resize()，扩容的规则的话，就是将原来的table的size大小做一次左移一位的运算的结果作为新table size大小，左移一位的也就是扩大成原来的两倍，将原来的数组对象放入新扩容的数组中。这里的话我就拿1.8来说明，通过(e.hash & oldCap) == 0来判断是否需要移位；在扩容以后，原来的如果高位是0的，那么在迁移到新的表中结果依旧是在同样的位置，如果是高位是 1 ，那么迁移后的元素在桶中的位置就是 原来的桶长度 + 原来的元素的位置。

        例子：设原来散列表的长度是16，length - 1转成二进制是 0 1111，现在假设有一个 A 和 B 两个 Node 的 key 的 hash 值分别为：0 1111、1 1111，A 和 0 1111取与 结果是：0 1111 & 0 1111 = 0 1111，下标是15， 同样 B 1 1111 & 0 1111 = 0 1111，这个时候是在原来的桶中的，现在散列表扩容后长度变成了 32 ，32 - 1 = 31 = 1 1111，此时再来计算 A 和 B 的在新的散列表中的位置，A ：0 1111 & 1 1111 = 0 1111 = 15，也就是说 A 在迁移到新的桶中的下标位置还是 15 ，再来看下 B ：1 1111 & 1 1111 = 1 1111 = 31，即 B 在新的散列表中的位置为 原来的散列表的长度（16）+ 原来的下标的位置（15） = 新的下标的位置（31），这就是迁移后元素存放的特点。

      • get（）

        get()方法的核心方法就是getNode()方法了，getNode()的实现逻辑的话就是，也是先对key进行hash()获得数组的下标索引，如果该数组的元素就是想要的(hash值和key与传进来的一致)，直接返回该元素，否则的话就进行一次判断是树还是链表，然后再进行遍历查找，找到想要的node节点。

      • 补充

        1. 链表转成红黑树的数据结构来把时间复杂度从O（n）变成O（logN）提高了效率
        2. 链地址法解决hash冲突，在每个数组元素上都一个链表结构，当数据被hash()后，得到数组下标，把数据放在对应下标元素的链表上。
        3. 1.7环形原因：Resize包含扩容和ReHash两个步骤，ReHash在并发的情况下可能会形成链表环。因为在调整大小过程中，存储在某个桶位置中的链表元素次序会反过来，而多线程情况下可能某个线程翻转完链表，另外一个线程又开始翻转，造成环形。
        4. 死循环原因？HashMap在并发执行put操作时会引起死循环，是因为多线程会导致HashMap的Entry链表形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取Entry。
        5. 为什么 (n - 1) & hash，能够获取下标？数组的长度一定是 2 的次幂，假设长度是 16 即 10000，也就是说不管怎么说，最高位都是1其余的都是0，然后n-1 就是最高位是 0 其余都是 1即01111，那么这个时候是不是 n-1 的范围就是 0-15，因为数组的下标是从0开始的，所以不管hash是什么值，最后的结果一定是在数组的长度范围之内。
        6. 通过对key的hashCode()(此本地方法仅是为了获取hashcode值)进行hash()，并计算下标( (n-1) & hash)，从而获得buckets的位置。如果产生碰撞(链地址法解决)，则利用key.equals()方法去链表或树中去查找对应的节点。
        7. 长度为8？通过泊松分布发现8（k）个键值对同时存在于同一个桶的概率只有0.00000006，比8大的话更是小于千万分之1。链表长度过长，查询效率低下；过短，易发生树化，而树化需要不小的开销，不能常发生。
        8. 负载因子0.75？空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率。
        9. 阈值 threshold 一般为 capacity * loadFactory

   2. concurrentHashMap

      1. JDK1.7

         在jdk1.7中的话，是由 Segment 数组、HashEntry 数组结构组成，Segment是一种可重入锁（ReentrantLock），Segment结构和hashMap类似是数组+链表结构；每个HashEntry是一个链表结构的元素。它使用锁分段的技术来保证线程安全。分段锁的话就是将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，这样的话能够实现并发访问。

         get()：高效在于get过程不需要加锁，因为将要使用的共享变量定义为volatile，保证可见性，拿到最新值。

         put()：必须加锁，首先定位到Segment，然后再Segment里进行插入操作，分为2步骤，1判断Segment里的HashEntry数组是否需要扩容，2再定位添加元素的位置

      2. JDK1.8

         采用了数组+链表+红黑树的实现方式来设计，并发控制使⽤ synchronized 和 CAS 来操作。

         CAS原理：CAS操作包含三个操作数，内存位置的值（V）、预期原值（A）和新值（B）。只有当内存位置的值与预期原值相匹配，那么处理器会自动将该位置更新为新值。否则处理器不做任何操作。是一个非阻塞的轻量级的乐观锁。

         缺点：

         1. ABA问题 A-B-A CAS检查时发现值是没有变化的 解决办法加版本号 1A-2B-3A
         2. 循环时间长开销大 自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销
         3. 只能保证一个共享变量的原子操作。当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i＝2,j=a，合并一下ij=2a，然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作。

         补充：

         1. Hashtable中采用的锁机制是一次锁住整个hash表，从而在同一时刻只能由一个线程对其进行操作；而ConcurrentHashMap中则是一次锁住一个桶。
         2. synchronized 只锁定当前链表或红⿊⼆叉树的⾸节点，这样只要 hash 不冲突，就不会产⽣并发，效率⼜提升 N 倍。

   参考连接：

   //源码分析   
   https://mp.weixin.qq.com/s/jQX4hUKA0ac18njGAn1FQw
   https://blog.csdn.net/qq_40574571/article/details/97612100  
   https://zhuanlan.zhihu.com/p/78079598
   https://blog.csdn.net/qq_42049365/article/details/108313874
   https://www.html.cn/qa/other/20391.html
   //红黑树
   https://cloud.tencent.com/developer/article/1350922  
   //长度为8？通过泊松分布发现8（k）个键值对同时存在于同一个桶的概率只有0.00000006，比8大的话更是小于千万分之1
   https://zhuanlan.zhihu.com/p/263523069  
   //负载因子  时间与空间上的一个权衡
   https://zhuanlan.zhihu.com/p/103449454 
   

   concurrentMap
   https://www.jianshu.com/p/95d8d42fb8ac
   https://www.html.cn/qa/other/20391.html