java基础-容器

一、集合基础

1、集合

• Collection接口下，主要用于存放单一元素
• Map接口下，用于存放键值对

2、常见集合的比较

• List 存储的元素是有序的、可重复的。
• Set: 存储的元素不可重复的。
• Queue: 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
• Map: 存储键值对，key 是无序的、不可重复的，value 是无序的、可重复的。
• 适用场景
  • 需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。
  • 我们只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。

二、List

1、ArrayList和数组的区别

• ArrayList内部基于动态数组实现，使用更加方便
• ArrayList会动态扩容1.5倍或缩容，数组创建不可改变长度
• ArrayList只能存储对象（包装类），数组可以存储基本数据类型和对象
• ArrayList支持插入、删除、遍历等操作，数组只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。
• ArrayList创建时不需要指定大小，数组创建必须指定长度

2、ArrayList和vector的比较

• ArrayList是List的主要实现类，底层使用Object[]存储，适合频繁查找，线程不安全
• Vector是List的古早实现类，底层使用Object[]，线程安全

3、Vector和Stack的比较

• 都是线程安全，都是使用synchronized关键字进行同步处理
• Stack基础Vector，是先进后出的栈，Vector是列表
• Vector和 Stack已经被淘汰，推荐使用并发集合类

4、ArrayList可以添加null吗

• ArrayList中可以存储任何类型的对象，包括 null。但 null 值无意义，且会让代码难以维护

5、ArrayList插入和删除的时间复杂度

• 插入：头部插入：由于需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O(n)。尾部插入：当 ArrayList 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)，因为它只需要在数组末尾添加一个元素即可；当容量已达到极限并且需要扩容时，则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中，然后再执行 O(1) 的操作添加元素。指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O(n)。
• 删除：头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O(n)。尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O(1)。指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

6、LinkedList插入和删除的时间复杂度

• 头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，不过由于有头尾指针，可以从较近的指针出发，因此需要遍历平均 n/4 个元素，时间复杂度为 O(n)。

7、LinkedList为什么不实现RandomAccess接口

• RandomAccess是一个标记接口（未定义方法），用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于 LinkedList 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 RandomAccess 接口。

8、ArrayList和LinkedList的比较

• 是否保证线程安全： ArrayList和LinkedList都是不同步的，也就是不保证线程安全；
• 底层数据结构： ArrayList底层使用的是 Object 数组；LinkedList底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环）
• 插入和删除是否受元素位置的影响：
  • ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 
  • LinkedList采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响，时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素，时间复杂度为 O(n) ，因为需要先移动到指定位置再插入和删除。
• 是否支持快速随机访问： LinkedList不支持高效的随机元素访问，而 ArrayList（实现了 RandomAccess 接口） 支持。快速随机访问就是通过元素的序号快速获取元素对象。
• 内存空间占用： ArrayList的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）

三、Set

1、Comparable和Comparator的比较

• Comparable和Comparator都是Java中用于排序的接口
• Comparable来自java.lang，用compareTo(Object obj)方法来排序
• Comparator来自java.util，用compare(Object o1, Object o2)方法来排序
• 使用
  • 对象实现Comparable接口，重写compareTo方法

  • //自定义比较器
    Collections.sort(arrayList, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
    });

2、什么是无序和不可重复

• 无序性不等于随机性 ，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。
• 不可重复性是指添加的元素按照 equals() 判断时 ，返回 false，需要同时重写 equals() 方法和 hashCode() 方法。

3、HashSet、LinkedHashSet和TreeSet的比较

• HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，保证元素唯一，线程不安全。
• HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
• 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。

四、Queue

1、Queue和Deque的比较

• Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出规则。Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

• Queue 接口	抛出异常	返回特殊值
  插入队尾	add(E e)	offer(E e)
  删除队首	remove()	poll()
  查询队首元素	element()	peek()

• Deque 是双端队列，在队列的两端均可以插入或删除元素。Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

• Deque 接口	抛出异常	返回特殊值
  插入队首	addFirst(E e)	offerFirst(E e)
  插入队尾	addLast(E e)	offerLast(E e)
  删除队首	removeFirst()	pollFirst()
  删除队尾	removeLast()	pollLast()
  查询队首元素	getFirst()	peekFirst()
  查询队尾元素	getLast()	peekLast()

2、ArrayDeque和LinkedList的比较

• ArrayDeque和LinkedList都是先Deque接口，都具有队列功能
• ArrayDeque基于可变长数组和双指针实现，LinkedList基于链表实现
• ArrayDeque不支持存储null，LinkedList支持
• ArrayDeque插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢
• 从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈

3、PriorityQueue

• 优先队列，元素出队顺序是与优先级相关，总是优先级最高的元素先出队。
• PriorityQueue利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
• PriorityQueue通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
• PriorityQueue是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
• PriorityQueue默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。
• PriorityQueue在面试中可能更多的会出现在手撕算法的时候，典型例题包括堆排序、求第 K 大的数、带权图的遍历等，所以需要会熟练使用才行

4、BlockingQueue

• 阻塞队列接口，继承于Queue，支持当队列没有元素时一直阻塞，直到有元素；还支持如果队列已满，一直等到队列可以放入新元素时再放入。
• 常用于生产者-消费者模型中，生产者线程会向队列中添加数据，而消费者线程会从队列中取出数据进行处理。

• public interface BlockingQueue<E> extends Queue<E> {// ...
  }

• 实现类

  • ArrayBlockingQueue:使用数组实现的有界阻塞队列。在创建时需要指定容量大小，并支持公平和非公平两种方式的锁访问机制。

  • LinkedBlockingQueue:使用单向链表实现的可选有界阻塞队列。在创建时可以指定容量大小，如果不指定则默认为Integer.MAX_VALUE。和ArrayBlockingQueue不同的是， 它仅支持非公平锁访问机制。

  • PriorityBlockingQueue:支持优先级排序的无界阻塞队列。元素必须实现Comparable接口或者在构造函数中传入Comparator对象，并且不能插入 null 元素。

  • SynchronousQueue:同步队列，是一种不存储元素的阻塞队列。每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作。因此，SynchronousQueue通常用于线程之间的直接传递数据。

  • DelayQueuq:延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队

5、ArrayBlockingQueue比较LinkedBlockingQueue

• 是JUC中常用的两种阻塞队列实现，都是线程安全的。
• 底层实现：ArrayBlockingQueue基于数组实现，而 LinkedBlockingQueue基于链表实现。
• 是否有界：ArrayBlockingQueue是有界队列，必须在创建时指定容量大小。LinkedBlockingQueue创建时可以不指定容量大小，默认是Integer.MAX_VALUE，也就是无界的。但也可以指定队列大小，从而成为有界的。
• 锁是否分离： ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁；LinkedBlockingQueue中的锁是分离的，即生产用的是putLock，消费是takeLock，这样可以防止生产者和消费者线程之间的锁争夺。
• 内存占用：ArrayBlockingQueue需要提前分配数组内存，而 LinkedBlockingQueue则是动态分配链表节点内存。这意味着，ArrayBlockingQueue在创建时就会占用一定的内存空间，且往往申请的内存比实际所用的内存更大，而LinkedBlockingQueue则是根据元素的增加而逐渐占用内存空间。

6、什么叫做阻塞队列的有界和无界

• 阻塞队列是特殊的队列
  • 当队列为空的时候，获取队列中元素的消费者线程会被阻塞，同时唤醒生产者线程。
  • 当队列满了的时候，向队列中添加元素的生产者线程被阻塞，同时唤醒消费者线程。
• 其中，阻塞队列中能够容纳的元素个数，通常情况下是有界的，比如我们实例化一个ArrayBlockingList，可以在构造方法中传入一个整型的数字，表示这个基于数组的阻塞队列中能够容纳的元素个数。这种就是有界队列。
  • 而无界队列，就是没有设置固定大小的队列，像LinkedBlockingQueue，它的默认队列长度是Integer.Max_Value。无界队列存在比较大的潜在风险，如果在并发量较大的情况下，线程池中可以几乎无限制的添加任务，容易导致内存溢出的问题、
  • 场景：线程池中，通过阻塞队列来实现线程任务的生产和消费功能。

7、ArrayBlockingQueue 原理

• 基于数组结构的阻塞队列，也就是队列元素是存储在一个数组结构里面，并且由于数组有长度限制，为了达到循环生产和循环消费的目的，ArrayBlockingQueue 用到了循环数组。
• 线程的阻塞和唤醒，用到了J.U.C 包里面的ReentrantLock 和Condition。

五、Map

1、HashMap、HashTable、HashSet和TreeMap的比较

• 线程是否安全： HashMap是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。（若要保证线程安全的话就使用 ConcurrentHashMap）；
• 效率：因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；
• 对null值的支持：HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出空指针。
• 初始容量以及扩容：① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（使用tableSizeFor()方法）

• //HashMap
  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;this.threshold = tableSizeFor(initialCapacity);}public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }/*** Returns a power of two size for the given target capacity.*/
  static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;//下一个高于或等于 n 的最小的2的幂n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  }

• 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间（后文中我会结合源码对这一过程进行分析）。Hashtable 没有这样的机制。
• 哈希函数的实现：HashMap 对哈希值进行了高位和低位的混合扰动处理以减少冲突，而 Hashtable 直接使用键的 hashCode() 值。
• HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

  HashMap	HashSet
  实现了 Map 接口	实现 Set 接口
  存储键值对	仅存储对象
  调用 put()向 map 中添加元素	调用 add()方法向 Set 中添加元素
  HashMap 使用键（Key）计算 hashcode	HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以equals()方法用来判断对象的相等性

• 相比于HashMap来说， TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。TreeMap 和HashMap 都继承自AbstractMap ，但TreeMap它还实现了NavigableMap接口和SortedMap 接口。

• 实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。NavigableMap 接口提供了丰富的方法来探索和操作键值对:定向搜索: ceilingEntry(), floorEntry(), higherEntry()和 lowerEntry() 等方法可以用于定位大于等于、小于等于、严格大于、严格小于给定键的最接近的键值对。子集操作: subMap(), headMap()和 tailMap() 方法可以高效地创建原集合的子集视图，而无需复制整个集合。逆序视图:descendingMap() 方法返回一个逆序的 NavigableMap 视图，使得可以反向迭代整个 TreeMap。边界操作: firstEntry(), lastEntry(), pollFirstEntry()和 pollLastEntry() 等方法可以方便地访问和移除元素。这些方法都是基于红黑树数据结构的属性实现的，红黑树保持平衡状态，从而保证了搜索操作的时间复杂度为 O(log n)，这让 TreeMap 成为了处理有序集合搜索问题的强大工具。

• 实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，也可以指定排序的比较器。

2、HashSet如何检查重复

• HashSet的add()方法只是简单的调用了HashMap的put()方法，并且判断了一下返回值以确保是否有重复元素。return map.put(e, PRESENT)==null;
• 加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

3、HashMap底层实现

• 工作过程
  • HashMap在Node静态内部类中存储key-valve 对。HashMap 使用哈希算法，在put和get 方法中，它使用 hashCode()和 equals()方法。当我们通过传递 key-value 调用 put 方法的时候，HashMap 使用hashCode(key)找的索引的位置。Entry存在数组中，所以如果存在entry，则使用equals()方法检查传递的key 是否己经存在，如果存在，覆盖value，如果不存在，它会创建一个新的 entry 然后保存。当我们通过传递key调用get方法时，它再次使用 hashcode()来找到数组中的索引，然后使用 equals()方法找出正确的Entry，然后返回它的值。
  • 关于 HashMap 比较重要的问题是容量、负荷系数和阈值调整。HashMap 默认的初始容量是 16，加载因子是 0.75。阀值是为负荷系数乘以容量，无论何时我们尝试添加一个 entry， 如果 map 的大小比阀值大的时候，HashMap会对 map的内容进行重新哈希，且使用更大的容量。
• 原理
  • HashMap 是以 Key-Value的方式进行数据存储的一种数据结构，在1.7中Hashap 的底层数据结构是数组＋链表，使用 Entry 类存储Key 和 Value ;JDK 1.8 中HashMap 的底层数据结构是数组+链表/红黑树，使用 Node类存储Key 和 Value。当然，这里的Entry 和 Node 并没有什么不同。保存自身的hash、 key 和 value、以及下个节点。因为 HashMap 本身所有的位置都为 null，所以在插入元素的时候即 put 操作时，会根据 key 的hash 去计算出一个index 值，也就是这个元素将要插入的位置。
  • 为什么需要链表
    首先，数组的长度是有限的，在有限的数组上使用哈希，那么哈希冲突是不可避免地，很有可能两个元素计算的 index 是相同的。拉链法，也就是把 hash 后值相同的元素放在同一条链表上。
  • 为什么要用红黑树
    当 Hash 沖突严重时，在数组上形成的链表会变的越来越长，由于链表不文持索引，要想在链表中找一个元素就需要遍历一遍链表，那显然效率是比较低的。为此，JDK 8 引入了红黑树，当链表的长度大于8的时候就会转换为红黑树，不过，在转换之前，会先去查看table 数组的长度是否大于 64，如果数组的长度小于 64，会优先选择对数组进行扩容resize，而不是把链表转换成红黑树。退化阈值是6：避免频繁地退化
  • 阈值8：链表O(n)，红黑树O(lgn)，但红黑树占用空间是链表地2倍
  • 新的 Entry/Node 节点在插入链表的时候，是怎么插入的？
    • 1.7采用头插法（多线程环境下可能会造成循环链表问题。）
    • 1.8 采用尾插法
      • 数组容量是有限的，如果数据多次插人并到达一定的数量就会进行数组扩容，也就是resize 方法。什么时候会进行resize 呢？与两个因素有关
        1) Capacity ：HashMap 当前最大容量/长度
        2) LoadFactor ：负载因子，默认值 0.75f
• 初始长度
  • 默认16，其实只有2的次幂都行，16是经验值
  • index = hashCode(key) & (length - 1)，为了保证index值是分布均匀，必须保证length是2的次幂
• 线程不安全：put()没有加锁
  • 使用Collextions.synchronizedMap()方法包装HashMap，对所有地修改操作加synchronized
  • 使用线程安全的HashTable
  • 使用ConcurrentHashMap，JDK7采用数组+链表存储数据，使用分段锁Segment保证线程安全；JDK8采用数组+链表/红黑树存储数据，使用CAS+synchronized保证线程安全
    • 7分段锁，对整个数组分割，锁一小段
    • 8synchronized锁链表或红黑树首节点
• HashMap 什么时候扩容
  • 当HashMap 中元素个数超过临界值时会自动触发扩容，这个临界值有一个计算公式。threashold=loadFactor*capacity。loadFactor 的默认值是0.75，capacity 的默认值是16，也就是元素个数达到12 的时候触发扩容。扩容后的大小是原来的2 倍。
• 负载因子0.75
  • LoadFactor 表示Hash 表中元素的填充程度。值越大，那么触发扩容的元素个数更多，虽然空间利用率比较高，但是hash 冲突的概率会增加。值越小，触发扩容的元素个数就越少，也意味着hash 冲突的概率减少，但是对内存空间的浪费就比较多，而且还会增加扩容的频率。
  • LoadFactor 的设置，本质上就是在冲突的概率以及空间利用率之间的平衡。0.75 这个值的来源，和统计学里面的泊松分布有关。

4、HashMap长度为什么是2的幂次方

• 位运算效率更高：位运算(&)比取余运算(%)更高效。当长度为 2 的幂次方时，hash % length 等价于 hash & (length - 1)。
• 可以更好地保证哈希值的均匀分布：扩容之后，在旧数组元素 hash 值比较均匀的情况下，新数组元素也会被分配的比较均匀，最好的情况是会有一半在新数组的前半部分，一半在新数组后半部分。
• 扩容机制变得简单和高效：扩容后只需检查哈希值高位的变化来决定元素的新位置，要么位置不变（高位为 0），要么就是移动到新位置（高位为 1，原索引位置+原容量）

5、HashMap多线程操作可能死锁

• JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个bucket中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

• 为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下，推荐使用 ConcurrentHashMap 。

6、HashMap线程不安全 

• JDK1.7 及之前版本，在多线程环境下，HashMap 扩容时会造成死循环和数据丢失的问题。数据丢失这个在 JDK1.7 和 JDK 1.8 中都存在

7、HashMap常见遍历方式

• 迭代器、for each、Lambda、Stream

  public static void main(String[] args) {//Map<Integer, String> map = new HashMap();
  //entrySet 的性能比 keySet 的性能高出了一倍之多，因此我们应该尽量使用 entrySet  来实现 Map 集合的遍历。// 遍历Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();while (iterator.hasNext()) {Map.Entry<Integer, String> entry = iterator.next();System.out.println(entry.getKey());System.out.println(entry.getValue());Iterator<Integer> iterator = map.keySet().iterator();while (iterator.hasNext()) {Integer key = iterator.next();System.out.println(key);System.out.println(map.get(key));}for (Map.Entry<Integer, String> entry : map.entrySet()) {System.out.println(entry.getKey());System.out.println(entry.getValue());}for (Integer key : map.keySet()) {System.out.println(key);System.out.println(map.get(key));}map.forEach((key, value) -> {System.out.println(key);System.out.println(value);});map.entrySet().stream().forEach((entry) -> {System.out.println(entry.getKey());System.out.println(entry.getValue());});map.entrySet().parallelStream().forEach((entry) -> {System.out.println(entry.getKey());System.out.println(entry.getValue());});}}

六、并发安全集合

1、ConcurrnetHashMap和HashTable的区别

• 区别主要在线程安全的方式上不同
• 底层数据结构： 1.7 ConcurrentHashMap 底层采用 分段的数组+链表 实现，1.8采用数组+链表/红黑树。Hashtable 和 JDK1.8 之前的 HashMap 类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
• 实现线程安全的形式：
  • 1.7ConcurrentHashMap 对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发；
  • 1.8ConcurrentHashMap 已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。
  • Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

2、ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

• 1.7中将数据分为一段一段（Segment）的存储，每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。Segment 继承了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

  static class Segment<K,V> extends ReentrantLock implements Serializable {
  }

  一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。也就是说，对同一 Segment 的并发写入会被阻塞，不同 Segment 的写入是可以并发执行的。

• 1.8中ConcurrentHashMap 取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。Java 8 中，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。

• 1.7和1.8的区别

  • 线程安全实现方式：JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。JDK1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。
  • Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。
  • 并发度：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。
  • 性能优化
    • 在JDK1.8 中，ConcurrentHashMap 锁的粒度是数组中的某一个节点，而在JDK1.7，锁定的是Segment，锁的范围要更大，因此性能上会更低。
    • 当数组长度不够时，ConcurrentHashMap 需要对数组进行扩容，在扩容的实现上，ConcurrentHashMap 引入了多线程并发扩容的机制，简单来说就是多个线程对原始数组进行分片后，每个线程负责一个分片的数据迁移，从而提升了扩容过程中数据迁移的效率。
    • 引入红黑树，降低了数据查询的时间复杂度，红黑树的时间复杂度是O(logn)。
•  如何保证线程安全
  • 1.7实现原理
    • ConcurrentHashMap中的数组设计分为大数组Segment 和小数组HashEntry

      

    • 因为Segment 本身是基于ReentrantLock 重入锁实现的加锁和释放锁的操作，这样就能保证多个线程同时访问ConcurrentHashMap 时，同一时间只能有一个线程能够操作相应的节点，这样就保证了ConcurrentHashMap 的线程安全。
    • 建立在Segment 加锁的基础上的，我们称它为分段锁或者片段锁
  • 1.8实现原理
    • 数组加链表加红黑树的方式优化了ConcurrentHashMap的实现

      

       
      • 它主要是使用了CAS加volatile 或者synchronized 的方式来保证线程安全。
      • 相当于是ConcurrentHashMap 通过对头结点加锁来保证线程安全的。
      • 添加元素时首先会判断容器是否为空，如果为空则使用volatile 加CAS 来初始化，如果容器不为空，则根据存储的元素计算该位置是否为空。如果根据存储的元素计算结果为空则利用CAS 设置该节点；如果根据存储的元素计算不为空，则使用synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树。这样就能保证并发访问时的线程安全了。
  • 总：锁的粒度相比Segment 来说更小了，发生hash冲突和加锁频率也降低了，在并发场景下的操作性能也提高了。当数据量比较大的时候，查询性能也得到了很大的提升。

3、ConcurrentHashMap (JDK1.8)

• 底层基于 CAS + synchronized 实现，所有操作都是线程安全的，允许多个线程同时进行 put、remave 等操作底层数据结构：数组、链表和红黑树的基础上还添加了一个转移节点，在扩容时应用table数组被volatle修饰，其中有一个比较重要的字段，sizeCtl=-1 时代表 table 正在初始化 table 未初始化时，代表需要初始化的大小table 初始化完成，表示table 的容量，默认为 0.75table 大小
• put 过程：key 和value 都是不能为空的，否则会产生空指针昇常，之后会进入自旋（for循环自旋）。如果当前数组为空，那么进行初始化操作，初始化完成后，计算出数组的位置，如果该位置没有值，采用 CAS操作进行添加；如果当前位置是转移节点，那么会调用 helptranster 方法协助扩容；如果当前位置有值，那么用synchronized 加锁，锁住该位置，如果是链表的话，买用的是尾插裝，如果是红黑树，则采用红黑树新增的方法，新增完成后需要判断是否需要扩容，大于 sizect/l的话，那么执行扩容操作
• 初始化过程：在进行初始化操作的时候，会将sizeCtl 利用CAS 操作设置为-1，CAS 成功之后，还会判断数組是否完成初始化，有一个双重检测的过程
• 过程：进入自旋，如果 sizeCtl ＜0，线程礼让（Threadyield0） 等待初始化；否则 CAS 操作将sizeCt 设置为-1,再次检测是否完成了初始化，若没有则执行初始化操作在JDK1.7 采用的是 Segment 分段锁，默认并发度为 16

4、ConcurrneHashMap中key和value不能为null

• ConcurrentHashMap 的 key 和 value 不能为 null 主要是为了避免二义性。null 是一个特殊的值，表示没有对象或没有引用。如果你用 null 作为键，那么你就无法区分这个键是否存在于 ConcurrentHashMap 中，还是根本没有这个键。同样，如果你用 null 作为值，那么你就无法区分这个值是否是真正存储在 ConcurrentHashMap 中的，还是因为找不到对应的键而返回的。拿 get 方法取值来说，返回的结果为 null 存在两种情况：值没有在集合中 ；值本身就是 null。

• 单线程下可以容忍歧义，而多线程下无法容忍

• 为了避免在多线程环境下出现歧义问题。一个线程从ConcurrentHashMap里面去获取key的时候，如果返回的结果是null，那么这个线程无法判断null表示的是确实不存在这个key，还是存在这个key但value为null
• 这种不确定性可以认为是线程安全性问题，而ConcurrentHashMap又是一个线程安全的集合，它是给多线程用的，所以自然不允许key或者value为null。而HashMap中允许为null，因为它不需要考虑线程安全性问题，它是给单线程用的。

5、ConcurrentHashMap能保证符合操作的原子性吗

• ConcurrentHashMap 是线程安全的，可以保证多个线程同时对它进行读写操作时，不会出现数据不一致的情况，也不会导致 JDK1.7 及之前版本的 HashMap 多线程操作导致死循环问题。但是，这并不意味着它可以保证所有的复合操作都是原子性的

• 复合操作是指由多个基本操作(如put、get、remove、containsKey等)组成的操作，例如先判断某个键是否存在containsKey(key)，然后根据结果进行插入或更新put(key, value)。这种操作在执行过程中可能会被其他线程打断，导致结果不符合预期。

• ConcurrentHashMap 提供了一些原子性的复合操作，如 putIfAbsent、compute、computeIfAbsent 、computeIfPresent、merge等。这些方法都可以接受一个函数作为参数，根据给定的 key 和 value 来计算一个新的 value，并且将其更新到 map 中。

6、CopyOnWriteArrayList

• 线程安全的，通过锁＋数组拷贝+volatile 保证线程安全（底层数组被 volatile 修饰）每次进行数组操作，都会把数组拷贝一份出来，在新数组上进行操作，操作之后再赋值回去对数组的操作，一般分为四步：1加锁;2从原数组中拷贝出新数组；3 在新数组上进行操作，并把新数组赋值给原引用；4 解锁；
• 已经加锁了，为什么还需要拷贝新数组？
  • 因为在原数组上进行修改，没有办法触发 volatile 的可见性，需要修改内存地址，即将新拷贝的数组赋值给原引用
• 在进行写操作的时候，是能读的，但是读的数据是老数组的，能保证数组最终的一致性,不能保证实时一致性；
• 存在内存占用问题，写时复制比较影响性能

七、Collentions工具类

1、排序

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面

2、查找,替换操作

int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素

3、同步控制(不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

//效率低
synchronizedCollection(Collection<T>  c) //返回指定 collection 支持的同步（线程安全的）collection。
synchronizedList(List<T> list)//返回指定列表支持的同步（线程安全的）List。
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（线程安全的）Map。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set。

八、使用

1、集合判断空

• 判断所有集合内部的元素是否为空，使用 isEmpty() 方法，而不是 size()==0 的方式

• 这是因为 isEmpty() 方法的可读性更好，并且时间复杂度为 O(1)。绝大部分我们使用的集合的 size() 方法的时间复杂度也是 O(1)，不过，也有很多复杂度不是 O(1) 的，比如ConcurrentHashMap 

2、集合转map

• 在使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合时，一定要注意当 value 为 null 时会抛 NPE 异常。

3、集合遍历

• 不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。
• 通过反编译你会发现 foreach 语法底层其实还是依赖 Iterator 。不过remove/add 操作直接调用的是集合自己的方法，而不是 Iterator 的 remove/add方法
• 这就导致 Iterator 莫名其妙地发现自己有元素被 remove/add ，然后，它就会抛出一个 ConcurrentModificationException 来提示用户发生了并发修改异常。这就是单线程状态下产生的 fail-fast 机制。
• list.removeIf(filter -> filter % 2 == 0); /* 删除list中的所有偶数 */
• 使用普通的 for 循环
• 使用 fail-safe 的集合类。java.util包下面的所有的集合类都是 fail-fast 的，而JUC包下面的所有的类都是 fail-safe 的。

4、集合去重

• 可以利用 Set 元素唯一的特性，可以快速对一个集合进行去重操作，避免使用 List 的 contains() 进行遍历去重或者判断包含操作。
• HashSet 的 contains() 方法底部依赖的 HashMap 的 containsKey() 方法，时间复杂度接近于 O(1)，ArrayList 的 contains() 方法是通过遍历所有元素的方法来做的，时间复杂度接近是 O(n)。

5、集合转数组

• 使用集合转数组的方法，必须使用集合的 toArray(T[] array)，传入的是类型完全一致、长度为 0 的空数组。
• list.toArray(new String[0]);指定返回数组的类型，0 是为了节省空间，只是说明返回的类型

6、数组转集合

• 使用工具类 Arrays.asList() 把数组转换成集合时，不能使用其修改集合相关的方法， 它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。
• Arrays.asList() 方法返回的并不是 java.util.ArrayList ，而是 java.util.Arrays 的一个内部类,这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。

• List list = new ArrayList<>(Arrays.asList("a", "b", "c"));
  Integer [] myArray = { 1, 2, 3 };
  List myList = Arrays.stream(myArray).collect(Collectors.toList());
  //基本类型也可以实现转换（依赖boxed的装箱操作）
  int [] myArray2 = { 1, 2, 3 };
  List myList = Arrays.stream(myArray2).boxed().collect(Collectors.toList());

九、其他

1、jdk7中的map

• hashMap：哈希冲突-->拉链法-->头插法（速度快，尾插法则需要遍历）；多线程环境下，hashmap扩容，可能形成循环链表（头插法-->扩容链表节点反转）；多线程环境中-->modcount修改次数!=预期次数-->快速失败机制-->并发修改异常
• concurrentHashMap：map<--segment[]<--entry[]