JAVA_集合

一.体系

• Collection：单列
• list：有序可重复，可以放多个Null
  • Arraylist ；Linkedlist ；Vector
• Set：无序不可重复，只能放一个Null
  • HashSet ；LinkedHashSet ；TreeSet
• Queue:
  • Deque:双端队列 ；BlockingQueue:阻塞队列 ；AbstractQueue:非阻塞队列
• Map：双列，k-v键值对
• HashMap
  • linkedHashMap
• TreeMap
• HashTable
  • Properties

二.ArrayList、LinkedList、Vector三者的异同(使用场景)？

• 同：存储有序可重复的数据 就像数组一样
• 异：

• ArrayList

  • 底层默认创建长度为10的数组：new Object[10]；(数组就需要连续的内存空间)
  • 空间不够自动扩容，扩展为原来 容量*1.5，同时将原有的元素复制到新的数组中
  • jdk1.7：类似饿汉式，new Arraylist()就直接你创建一个数组
  • jdk1.8：类似懒汉式，new Arraylist()还不创建数组,只有使用add()才创建。延迟数组的创建,节省内存
  • 数组结构适合遍历和查找，不适合插入/删除(但可以优化)
  • 线程不安全(效率高)，可以使用Collections工具类变为线程安全，或使用juc

  • Vector

  • 底层默认创建长度为10的数组：new Object[10];

  • 空间不够自动扩容,扩展为原来容量*2，同时将原有的元素复制到新的数组中
  • 线程安全(所有方法synchronized修饰)，但是效率太低，很少使用
  • LinkedList
  • 底层创建一个双向链表 (链表不需要连续的内存空间)
  • 定义了一个Node内部类，里面有prev，element，next属性
  • 链表结构适合插入和删除，遍历和查找比较慢
  • 链表当然不需要扩容
  • 只能使用iterator遍历,不能使用增强for遍历,因为需要get每一个值,遍历所有的元素,效率极低

ArrayList和LinkedList性能对比? 建议使用ArrayList

• LinkedList底层维护一个内部类Node，每次添加新的元素创建一个Node对象，耗费资源。 而且使用不方便(遍历时)
• 对于ArrayList不适合插入/删除的特性，可以进行优化。采用尾插法并指定初始容量可以极大的提升性能,甚至超过LinkedList。
• ArrayList 的空间浪费主要体现在在list列表的结尾预留一定的容量空间； LinkedList 的空间花费则体现在它的每一个元素都需要消耗存储指针节点对象的空间。

如何实现ArrayList和Array的转换?

• Arrays.asList(str)； //转变为list
• list.toArray； //转变为array

三.阻塞队列

这里只说明api的使用

四.HashMap

前提知识：HashCode和equals ，提前说明这两个东西，有助于理解HashMap

hashCode()相同，equals()也一定为true吗？
不是,这两个是配合使用的。

HashCode()是Object提供的一个native的方法，用来获取哈希码
内存中维护一个很大的哈希表,每一个对象存储到内存的时候，都在这个表中进行记录
这个表就相当于一个"记录表",记录着每个对象的地址。

什么是哈希表?

哈希表本质是一个升级版的数组,每一个对象都有一个关键字(k-v中的k),根据内部的"哈希算法"得出一个"哈希码"。
这个哈希码就相当于数组的索引(哈希表没有0,1那样的索引。哈希码就是索引),可以直接通过哈希码找到一个对象。
这样做就是为了提高执行的效率,快速定位对象。因为哈希表的初衷就是升级数组，数组已经很合适查询了，
但是哈希表"更块"。哈希表就是一种数据结构
(哈希表其实就是对数组的索引进行优化,"让索引和关键字(传入的对象)产生关系,从而快速找到对象的位置")

注意点:
    相同的对象一定产生相同的哈希码
    不同的对象也可能产生相同的哈希码 (产生哈希冲突，有对应的解决方案)
    //上面这两条主要是因为哈希算法导致的,正因为这样,才需要用到equals
    equals()被覆盖,hashCode()也必须被覆盖

为什么要有HashCode?(为什么搞一个"记录表")
以HashSet如何检查重复来说明为什么要有HashCode：
对象加入HashSet时,HashSet会计算对象的哈希码,从哈希表中检查是否索引的位置上有值(对象)，
没有:就认为对象不重复,允许添加;
有值:就会调用equals()来判断两个对象是否相等:
        相等：不允许添加
        不相等:说明哈希冲突了,采用对应的解决方案放到其他的位置上,允许添加
这样做主要为了避免多次equals比较,提高效率。

HashSet底层就是创建一个HashMap,所以直接对hashMap进行解释

底层实现：

• jdk7：数组+链表
• new HashMap()；//创建一个长度为16的数组
• jdk8：数组+链表+红黑树 (改为红黑树为了加快查询的速度)
• new HashMap()；//类似于懒汉式，还没有创建数组，当调用put()时创建长度为16的数组
• 只有当链表高度>8且数组长度>64,就把链表改为红黑树。数组长度

put添加过程(如何保证不重复)

• 添加的过程和上面hashSet使用哈希表添加的过程一样，只是哈希冲突问题采用七上八下。
• 注意：发现hashCode相同，equals相同，不是不允许添加，而是覆盖之前的元素
• 七上八下：遇到哈希冲突时
• jdk7是把新元素放在数组上，旧元素放在链表上，指向旧元素
• jdk8是把新元素放在链表上，旧元素指向新元素

扩容机制

• 数组超过临界值(临界值0.75) 扩展为原来的2倍， 将旧的元素复制到新的数组中，重新计算hash，按照列表/红黑树的方式排序起来

源码中重要的常量

• DEFAULT_INITIAL_CAPACITY：默认数组容量16
• MAXIMUM_CAPACITY：最大的容量2^30
• DEFAULT_LOAD_FACTOR：默认的加载因子0.75(一个经过科学计算的数)临界值=容量0.75 比如160.75=12 容量达到12时,考虑扩容
• TREEIFY_THRESHOLD：链表转化为红黑树的 链表最低高度8
• MIN_TREEIFY_CAPACITY： 链表转化为红黑树的 数组最小长度64
• UNTREEIFY_THRESHOLD：红黑树转回链表的 数组长度6

开发中你是怎么使用hashMap?

• 根据实际业务指定hashMap的长度,因为这样可以避免多次扩容，提高性能
• HashMap
• 注意：new HashMap<>(7)；//这种我们自定义长度的hashmap，在创建数组的时候,长度经过tableSizeFor(initialCapacity)方法变为大于指定长度的最低二次幂数，
• 比如1就变为2；7就变为8；11就变为16 等，所以上述是创建了一个长度为8的数组

Hashmap为什么不安全?

• jdk 1.7 hashmap底层使用数组 + 链表，当扩容时会调用transfer函数 ，在对table进行扩 容，需要将原来的数据复制到newtable中，采用头插法，会将链表反转，这个过程可能会导致死循环和数据丢失，也有可能造成数据覆盖
• jdk 1.8中 hashmap底层使用数组 + 链表 + 红黑树，采用尾插法，优化了死循环和数据丢失的 问题，但是还是会有数据覆盖的问题

HashMap和HashTable的区别?

• 底层不同
• HashMap：初始化16，扩容2倍
• HashTable：初始化11，扩容2倍+1
• HashMap线程不安全，HashTable线程安全(效率低)。 (即使需要线程安全也不用HashTable，而是使用concurrentHashMap，后面解释)
• HashMap可以存储null的k-v;HashTable不能存储null的k-v

五.集合不安全

集合类不安全主要是因为多个线程写入时，就会抛出ConcurrentModificationException

list:  解决线程不安全的方式?

(1)//JDK1.0 就存在了！ 底层使用synchronized 效率低
    List list = new Vector<>();
(2)//使用工具类将普通的转换为线程安全的
    List list1 = Collections.synchronizedList(new ArrayList<>());
(3)//使用CopyOnWriteArrayList(写时复制容器)
    List list2 = new CopyOnWriteArrayList<>();

写入时复制（CopyOnWrite）思想:
    写入时复制（CopyOnWrite，简称COW）思想是计算机程序设计领域中的一种优化策略。
读写分离,写时复制出一个新的数组,完成插入,修改或者移除操作后将新数组赋值给array。
这样做的好处是可以对 CopyOnWrite容器进行并发的读,而不需要加锁,因为当前容器
不会添加任何元素.所以 CopyOnWrite容器 也是一种读写分离的思想,读和写不同的容器。
(增删改方法加锁,查的方法不加锁)

set:    底层就是 new hashmap()
(1)//使用工具类将普通的转换为线程安全的
    Set set = Collections.synchronizedSet(new HashSet<>());
(2)//使用CopyOnWriteArraySet
    Set set = new CopyOnWriteArraySet();

map:
(1)//使用hashTable   底层使用synchronized 效率低
    Map map = new Hashtable<>();
(2)//使用工具类将普通的转换为线程安全的
    Map map = Collections.synchronizedMap(new HashMap<>());
(3)//使用ConcurrentHashMap
    Map map = new ConcurrentHashMap<>();

ConcurrentHashMap底层:

• 总体思想：避免加锁,尽可能减小加锁的范围。优化HashMap，对HashMap进行加锁
• jdk7和jdk8有所不同，下面分开讨论

jdk7：

• 采用分段Segment[]+HashEntry
• 每一段Segment通过继承ReentrantLock来进行加锁，所以每次需要加锁的操作锁住的是 一个 segment，这样只要保证每个Segment 是线程安全的，也就实现了全局的线程安全。好多地方也称为每一个segment为”分段锁”。 HashEntry[]其实就是链表，每一个hashEntry就是一个对象(value,next)。 初始容量为16*2 = 32的大数组。
• put()：需要加锁
• 尝试获取Segment的锁，获取不到，scanAndLockForPut()获取自旋锁
• 遍历HashEntry，重复了就覆盖，不重复就创建HashEntry放入Segment中。
• 释放当前Segment锁
• get()：不需要加锁
• 第一次hash定位到Segment的位置
• 然后第二次hash定位到指定的HashEntry的位置，遍历该HashEntry下的链表， 成功就返回，不成功返回null
• HashEntry中的value和指针next都是用volatile修饰，保证可见性，不需要加锁

jdk8：

• 采用数组+链表+红黑树 ，使用Synchronized”和”CAS+volatile+自旋锁来操作
• 将锁的级别控制在了更细粒度的哈希桶数组元素级别，也就是说只需要锁住这个链表头节点(红黑树的根节点)，就不会影响其他的哈希桶数组元素的读写，大大提高了并发度。并且采用大量的位运算，提高效率。初始容量为 16。
• sizeCtl的作用：
• 负数：
  • -1：表示正在初始化
  • -n：表示正在扩容
• 正数：
  • 0表示还没有临界值
  • 其他表示触发扩容的临界值
• put()：
• 获取hash值
• 判断是否初始化，没有初始化就采用CAS+sizeCtl的保证并发，进行初始化，如果一个线程正在初始化，另一个线程进入，判断sizeCtl
• 定位到 Node，拿到首节点 f，判断首节点f
  • 如果为null ，则通过 CAS 的方式尝试添加
  • 如果为f.hash = MOVED = -1，说明其他线程在扩容，参与一起扩容
  • 如果都不满足，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入；
• 如果链表长度达到8，转变为红黑树
• addCount()方法记元素的个数，初步分析使用了CAS
• get()：
• 很简单，就是获得索引位置，遍历链表/红黑树获得值
• transfer()：用来进行协助扩容
• 主要是将扩容任务交给多个线程进行,多个线程主要进行元素的迁移
• addCount()： 记录集合的元素数量,大于临界值进行扩容

与HashMap的区别：

1. 自定义容量时，容量为”大于指定长度的最低二次幂数”。这个和hashMap还有点小区别
2. HashMap指定长度本来是二次幂就不用找大于它的，而concurrentHashMap指定为二次幂还要找比它大的二次幂
3. new HashMap(16)： 创建长度为16的数组
4. new HashMap(12)：创建长度为16的数组
5. new concurrentHashMap(16)： 创建长度为32的数组
6. new concurrentHashMap(12)：创建长度为16的数组
7. hashMap允许接收null值，concurrentHashMap不允许null值 (这里的null指 空key，空value)

8. 为什么concurrentHashMap不能为null的k和v?

   • 因为有两异性，get(key)，不知道是返回value的值为null，还是找到k为null。
   • hashMap可以通过containsKey(key)去除两异性
   • concurrentHashMap用在并发环境下, 无法使用containsKey

寄语：任何你的不足，在你成功的那刻，都会被人说为特色。所以，坚持做你自己，而不是在路上被别人修改的面目全非

Original: https://www.cnblogs.com/monkey-xuan/p/15863680.html
Author: 小猴子_X
Title: JAVA_集合