Java——集合框架_数组_链表

Collections 是一个包装类，包含了很多静态方法、不能被实例化，而是作为工具类利用，比如供应的排序方法：Collections.sort(list);供应的反转方法：Collections.reverse(list)。

相同点：三者都实现 List 接口，都是有序凑集。
前两个底层采取 Object[] elementData 数组。
LinkedList双向链表(JDK1.6之前为循环链表，JDK1.7取消了循环)。

不同点：

fail-fast是一种可能触发的机制，实际上ArrayList 的线程安全仍旧没有担保，如果碰着多线程场景，可以通过如下方案担保线程安全：

1.利用Vector代替ArrayList。
（不推举，Vector是一个历史遗留类）

2.利用Collections.synchronizedList 方法将其转换成线程安全的容器后再利用。
List<String> syncList = Collections.synchronizedList(arraylist)。

3.利用CopyOnWriteArrayList代替ArrayList。

4.在利用 ArrayList 时，运用程序通过同步机制去掌握 ArrayList 的读写。

list 的遍历办法选择：

双向链表： 包含两个指针，一个prev指向前一个节点，一个next指向后一个节点。

双向循环链表： 末了一个节点的 next 指向head，而 head 的prev指向末了一个节点，构成一个环。

1.3.3HashSet 如何担保 key 不重复

通过 HashSet 的 add 方法实现可知，其掩护了一个 HashMap 来实现元素的添加；我们知道，HashMap 作为双列凑集，它的键是不能够重复的，HashMap 针对 hashCode 相同且 equals 比较值相同的时候实行的是更新操作，以是 Hashmap 中的 key 是唯一的，也决定了 hashset 元素值也是唯一的。

HashSet 底层便是基于 HashMap 实现的（除了个别方法自己实现，其他调用 hashmap 的）。
HashMap 利用键(Key)打算 hashcode，HashSet 利用成员工具来打算 hashcode 值。

1、List,Set 都是继续自 Collection 接口

2、特点区分：

List 特点：元素有序不唯一。
可以插入多个 null 元素。
list 方法常用的实现类有：ArrayList、LinkedList 和 Vector。

Set 特点：元素无序唯一，重复元素会覆盖掉，只许可插入一个 null 元素（元素虽无序，但元素在 set 中的位置是有该元素的 HashCode 决定的，其位置实在是固定的；加入 Set 的 Object 必须定义 equals()方法 ，其余 list 支持 for 循环，也便是通过下标来遍历，也可以用迭代器，但是 set 只能用迭代，由于无序，无法用下标来取得想要的值。
）Set 方法中常用的实现类有: HashSet、LinkedHashSet以及 TreeSet。

3、Set 和 List 效率比拟：

Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。

List：和数组类似，List 可以动态增长，查找元素效率高，插入删除元素效率低，由于会引起其他元素位置改变。

推举 Iterator.remove()

public class ListRemove { public static void main(String[] args) { / 总结：1.用for循环遍历 List 删除元素时，须要把稳索引会左移的问题。
2.List删除元素时，为避免陷阱，建议利用迭代器iterator的remove办法--5。
3.List删除元素时，默认按索引删除，而不是工具删除。
/ List<Integer> list = new ArrayList<Integer>(){{ add(1);add(2);add(3);add(3);add(4); }}; System.out.println("原始 list==" + list);// test1(list);// test2(list);// test3(list);// test4(list); test5(list);// test6(list);// test7(list);// test8(list); } // 1、普通 for 循环遍历 List 删除指定元素--缺点！
！
！
相邻有相同元素会漏删 public static void test1(List<Integer> list) { for (int i = 0; i < list.size(); i++) { if (list.get(i) == 3) { list.remove(i); } } System.out.println("情形 1 后 list1==" + list); } // 2、for 循环遍历 List 删除元素时，让索引同步调整--精确！
public static void test2(List<Integer> list) { for (int i = 0; i < list.size(); i++) { if (list.get(i) == 3) { list.remove(i--); } } System.out.println("情形 2 后 list2==" + list); } // 3、倒序遍历 List 删除元素--精确！
public static void test3(List<Integer> list) { for (int i = list.size() - 1; i >= 0; i--) { if (list.get(i) == 3) { list.remove(i); } } System.out.println("情形 3 后 list3==" + list); } // 4.foreach遍历List删除元素--缺点！
！
抛非常：java.util.ConcurrentModificationException / 通过代码我们创造Itr是ArrayList中定义的一个私有内部类， 在next、remove方法中都会调用checkForComodification方法， 该方法的浸染是判断modCount != expectedModCount是否相等， 如果不相等则抛出ConcurrentModificationException 非常。
/ public static void test4(List<Integer> list) { for (Integer i : list) { if (i == 3) { list.remove(i); } } System.out.println("情形 4 后 list4==" + list); } // 5、迭代删除List元素--精确！
// Iterator.remove() 方法会在删除当前迭代工具的同时，会保留原来元素的索引。
// 以是用迭代删除元素是最保险的方法，建议大家利用List过程中须要删除元素时，利用这种办法。
public static void test5(List<Integer> list) { Iterator<Integer> it = list.iterator(); while (it.hasNext()) { if (it.next() == 3) { it.remove(); } } System.out.println("情形 5 后 list5==" + list); } // 6、迭代遍历,用 list.remove(i)方法删除元素--缺点！
！
！
抛出非常：java.util.ConcurrentModificationException， public static void test6(List<Integer> list) { Iterator<Integer> it = list.iterator(); while (it.hasNext()) { Integer value = it.next(); if (value == 3) { list.remove(value); } } System.out.println("情形 6 后 list6==" + list); } // 7、List 删除元素时，把稳 Integer 类型和 int 类型的差异. public static void test7(List<Integer> list) { list.remove(2); System.out.println("情形 7 后 list7==" + list); } // 8、List 删除元素时，把稳 Integer 类型和 int 类型的差异. public static void test8(List<Integer> list) { list.remove(new Integer(2)); System.out.println("情形 8 后 list8==" + list); }}1.3.7ArrayList 扩容机制

以无参数布局方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。
当真正对数组进行添加元素操作时，才真正分配容量。
即向数组中添加第一个元素时，数组容量扩为 10。

ArrayList的序列化不太一样，它利用transient润色存储元素的elementData的数组，transient关键字的浸染是让被润色的成员属性不被序列化。
出于效率的考虑，数组可能长度100，但实际只用了50，剩下的50不用实在不用序列化，这样可以提高序列化和反序列化的效率，还可以节省内存空间。

ArrayList通过两个方法readObject、writeObject自定义序列化和反序列化策略，实际直策应用两个流ObjectOutputStream和ObjectInputStream来进行序列化和反序列化。

类

key/value

底层数据

顺序

线程

Super

HashTable

均不为 null

数组+链表

无序

安全

Dictionary

ConcurrentHashMap

均不为 null

数组+链表(1.7)

数组+链表/红黑树

无序

安全，分段锁

CAS+syn..(1.8)

AbstractMap

TreeMap

key 不为 null，value 可为 null

红黑树

有序

不屈安

AbstractMap

HashMap

key 或 value 都可为 null

key 重复会覆盖 value 许可重复

数组+链表(1.7)

数组+链表/红黑树

无序

不屈安

AbstractMap

LinkedHashMap

key 或 value 都可为 null

key 重复会覆盖 value 许可重复

双向链表

有序

不屈安

AbstractMap

把稳：

事理：HashMap 底层是 hash 数组和单向链表实现，数组是主体，链表紧张为理解决冲突，由 Node 内部类（实现 Map.Entry<K,V>接口）实现，HashMap 通过 put & get 方法存储和获取。

Java 8 中 new HashMap 的时候不会先创建这个数组，而是在第一次添加元素的时候创建。

在 Java 8 之前存储数据的内部类是 Entry< K, V>，之后用 Node< K, V>代替。
代码大体都是一样的。

Node 代码：

static class Node implements Map.Entry { // hash 是通过打算得到的散列值 final int hash; final K key; V value; // 指向另一个 Node，这样 HashMap 可以像链表一样存储数据 Node<K,V> next; ... }

内部变量:

// 默认容量大小 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; // 装载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 转换为二叉树的阀值 static final int TREEIFY_THRESHOLD = 8; // 转换为二叉树的最低阀值 static final int UNTREEIFY_THRESHOLD = 6; // 二叉树最小容量 static final int MIN_TREEIFY_CAPACITY = 64; // 哈希表 transient Node[] table; // 键值对的数量 transient int size; // 记录 HashMap 构造改变次数，与 HashMap 的快速失落败干系 transient int modCount; // 扩容的阈值 int threshold; // 装载因子 final float loadFactor;

HashMap 有两个主要的参数：容量（Capacity）和负载因子（LoadFactor）。

容量（Capacity）：是指 HashMap 中桶的数量，默认的初始值为 16。
容量必须知足是 2 次幂，如果我们指定 initialCapacity 不为 2 次幂时，HashMap 的 tableSizeFor 方法将其转换为大于 n 的最小的 2 的 N 次方数，能担保 n 永久都是 2 次幂。

负载因子（LoadFactor）：也被称为装载因子，LoadFactor 是用来剖断 HashMap 是否扩容的依据，默认值为 0.75f，装载因子的打算公式 = HashMap 存放的 KV 总和（size）/ Capacity。

Capacity 为什么是 2 的幂次⽅

由于当容量为 2 的幂时，会知足一个公式：(n - 1) & hash = hash % n，而&比%具有更高的效率，能担保索引值肯定在 capacity 中，不会超出数组长度。

(n - 1) & hash 实际上是打算出 key 在 tab 中索引位置。

扰动函数浸染及实现

浸染：办理碰撞问题

实现：①利用key.hashCode()打算hash值并赋值给变量h；②将h向右移动16位；③将变量h和向右移16位的h做异或运算（二进制位相同为0，不同为1）。
此时得到经由扰动函数后的hash值。

所谓 “拉链法” 便是：将链表和数组相结合。
也便是说创建一个链表数组，数组中每一格便是一个链表。
若碰着哈希冲突，则将冲突的值加到链表中即可。

/ Returns a power of two size for the given target capacity. /static final int tableSizeFor(int cap) { // cap-1 后，n 的二进制最右一位肯定和 cap 的最右一位不同，即一个为 0，一个为 1，例如 cap=17（00010001），n=cap-1=16（00010000） // 减 1→移位→按位或运算→加1返回 int n = cap - 1; //n = (00010000 | 00001000) = 00011000 n |= n >>> 1; //n = (00011000 | 00000110) = 00011110 n |= n >>> 2; //n = (00011110 | 00000001) = 00011111 n |= n >>> 4; //n = (00011111 | 00000000) = 00011111 n |= n >>> 8; //n = (00011111 | 00000000) = 00011111 n |= n >>> 16; //n = 00011111 = 31 //n = 31 + 1 = 32, 即终极的 cap = 32 = 2 的 (n=5)次方 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}

扩容源码：

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; // now the table is null int oldCap = (oldTab == null) ? 0 : oldTab.length; // so oldCap == 0 / 1、若调用的是带有参数的布局器，oldThr = tableSizeFor(initialCapacity) > 0, 2、若调用的是无参数的布局器，oldThr == 0 / int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { //下面代码不会调用，由于 oldCap == 0 } else if (oldThr > 0) // initial capacity was placed in threshold //若调用的是带有参数的布局器，此时打算的桶数组大小便是 tableSizeFor(initialCapacity) > 0 newCap = oldThr; else {// zero initial threshold signifies using defaults //若调用的是无参数的布局器，newCap == 16, newThr == (int) 16 0.75 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { //到这里如果 newThr 还没有被赋值，就实行下面代码 //为什么到这里 newThr 依然为 0 呢？如果调用带有参数的布局器，那么 threashold 是大于 0 的，那么 //就实行上面的 if(oldThr > 0),将 oldThr 值赋给 newCap，此时 newThr 依然为 0, 而原来的 threshold 也就没有了用途 //这解释之前将一个 2 的幂次方值赋值给 threshold，只是为了赋值给桶数组的默认容量值（newCap = oldThr），赋值完之后， //threashold 就须要重新打算了，下面便是打算过程： float ft = (float)newCap loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //覆盖 threshold threshold = newThr; //开辟空间在这里 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { //这里面的代码不会调用，由于 oldTab == null。
} //返回桶数组的引用 return newTab;}

Put 源码大致思路：

首次 put 步骤：①、分配数组空间；（无参布局默认空间16）②、插入键值对；③、++modCount;

非首次 put 步骤：①、调用 hash(K) 方法打算K的hash值，然后结合数组长度，打算得数组下标；

②、根据hash值找到对应桶位置的第一个元素，判断是否有

a.没有，直接将键值对插入到哈希表中。

b.有，则发生碰撞；

i.key 相同且它们两者 equals 返回 true，则更新键值对；

ii.如果是红黑树，则实行树的插入

iii.如果是链表，有 key 知足相等条件，更换旧值；否则插入 key-value 到链表末了；插入之后如果当前链表长度大于 TREEIFY_THRESHOLD，转换成红黑树构造。

③、判断是否超过阀值，如果超过就要扩容（当容器中的元素个数大于capacity loadfactor时，容器会进行扩容resize为2n）；

把稳：1、JDK 1.7 之前利用头插法、JDK 1.8 利用尾插法

public V put(K key, V value) { // 对 key 进行 hash() return putVal(hash(key), key, value, false, true);}// 扰动函数static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h ››› 16);}//onlyIfAbsent 为 false，解释如果已经存在相同(== 、equals)的 key，则覆盖并返回旧值。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node‹K,V›[] tab; Node‹K,V› p; int n, i; // tab 为空则创建 // 第一次 put 值的时候，会触发下面的 resize()，开辟数组空间 if ((tab = table) == null || (n = tab.length) == 0) // resize()是调度 table 数组大小的，若 table 数组为空或长度为 0，重新调度大小 n = (tab = resize()).length; // (n - 1) & hash 打算出的值是存放数组的位置，若当前位置为空，则直接放入个中 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //第一次调用 put 的时候，下面代码都不会实行 // hash 冲突 Node‹K,V› e; K k; // 如果 hash 相同，并且 key 值也相同，则找到存放位置 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 该链为二叉树，则放入二叉树中 else if (p instanceof TreeNode) e = ((TreeNode‹K,V›)p).putTreeVal(this, tab, hash, key, value); // 存放到链表中 else { for (int binCount = 0; ; ++binCount) { // 遍历链表并将值放到链表末了 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount ›= TREEIFY_THRESHOLD - 1) // -1 for 1st // 如果链表中的值大于 TREEIFY_THRESHOLD - 1，则将链表转换成二叉树 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 表示对付当前 key 早已经存在 if (e != null) { // existing mapping for key V oldValue = e.value; // 如果 onlyIfAbsent 为 false 或则 oldValue 为空，更换原来的值 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // 返回原来的值 return oldValue; } } // HashMap 构造修正次数，紧张用于判断迭代器中 fail-fast ++modCount; // 超过 load factorcurrent capacity，resize if (++size › threshold) resize(); afterNodeInsertion(evict); return null;}

获取工具时，将 K 传给 get() 方法：

①、调用 hash(K) 方法（打算 K 的 hash 值）从而获取该键值所在链表的数组下标；

②、顺序遍历链表，equals()方法查找相同 Node 链表中 K 值对应的 V 值。

hashCode 是定位的，存储位置；equals 是定性的，比较两者是否相等。

get 源码大致思路：

1. bucket 里的第一个节点，直接命中；

2. 如果有冲突，则通过 key.equals(k)去查找对应的 entry

3. 若为树，则在树中通过 key.equals(k)查找，O(logn)；

4. 若为链表，则在链表中通过 key.equals(k)查找，O(n)。

public V get(Object key) { Node‹K,V› e; return (e = getNode(hash(key), key)) == null ? null : e.value;}/ 该方法是 Map.get 方法的详细实现 吸收两个参数 @param hash key 的 hash 值，根据 hash 值在节点数组中寻址，该 hash 值是通过 hash(key) 得到的 @param key key 工具，当存在 hash 碰撞时，要逐个比对是否相等 @return 查找到则返回键值对节点工具，否则返回 null/final Node‹K,V› getNode(int hash, Object key) { Node‹K,V›[] tab; Node‹K,V› first, e; int n; K k; // 声明节点数组工具、链表的第一个节点工具、循环遍历时确当前节点工具、数组长度、节点的键工具 // 节点数组赋值、数组长度赋值、通过位运算得到求模结果确定链表的首节点 if ((tab = table) != null && (n = tab.length) › 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // 首先比对首节点，如果首节点的 hash 值和 key 的 hash 值相同，并且首节点的键工具和 key 相同（地址相同或 equals 相等），则返回该节点 ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 返回顾节点 // 如果首节点比对不相同、那么看看是否存不才一个节点，如果存在的话，可以连续比对，如果不存在就意味着 key 没有匹配的键值对 if ((e = first.next) != null) { // 如果存不才一个节点 e，那么先看看这个首节点是否是个树节点 if (first instanceof TreeNode) // 如果是首节点是树节点，那么遍历树来查找 return ((TreeNode‹K,V›)first).getTreeNode(hash, key); // 如果首节点不是树节点，就解释还是个普通的链表，那么逐个遍历比对即可 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 比对时还是先看 hash 值是否相同、再看地址或 equals return e; // 如果当前节点 e 的键工具和 key 相同，那么返回 e } while ((e = e.next) != null); // 看看是否还有下一个节点，如果有，连续下一轮比对，否则跳出循环 } } return null; // 在比对完了该当比对的树节点 或者全部的链表节点 都没能匹配到 key，那么就返回 null

紧张差异如下：

桶数组是用来存储数据元素，链表是用来办理冲突，红黑树是为了提高查询的效率。

JDK7 中 HashMap 去世循环导致 CPU100%的缘故原由：

HashMap 之以是在并发下扩容会造成去世循环，是由于多个线程并发进行时，一个线程先期完成了扩容，将原的链表重新散列到自己的表中，并且链表变成了倒序，后一个线程再扩容时，又进行自己的散列，再次将倒序链表变为正序链表。
于是形成了一个环形链表，当表中不存在元素时，造成去世循环。
虽然在 JDK1.8 中，改动了这个问题，但是 HashMap 始终存在着其他的线程安全问题。
以是在并发情形下，我们该当利用 HastTable 或者 ConcurrentHashMap 来代替 HashMap。
推举 ConcurrentHashMap。

1.当两个工具的 hashCode 相同会发生什么？

由于 hashCode 相同，不一定便是相等的（equals 方法比较），以是两个工具所在数组的下标相同，"碰撞"就此发生。
又由于 HashMap 利用链表存储工具，这个 Node 会存储到链表中。

2.key 的 hash 的实现

JDK1.8 中，是通过 hashCode()的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，利用位运算替代取模运算，在 table 的长度比较小的情形下，也能担保 hashcode 的高位参与到地址映射的打算当中，避免碰撞，同时不会有太大的开销。

3.key 的 hash 右移 16 位的缘故原由

由于 h 的 int 类型恰好 32 位，右移 16 位恰好为 32bit 的一半，然后再与 h 异或时，就能达到 h 的高 16 位和低 16 位都能参与打算，使打算出的 hash 值更加的分散，且最大努力减少哈希冲突。

5.为什么要用异或运算符？

担保了工具 hashCode 的 32 位值只要有一位发生改变，全体 hash()返回值就会改变。
尽可能的减少碰撞。

6.HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变革？这种变革会带来什么问题？

①、table 数组大小是由 capacity 这个参数确定的，默认是16，也可以布局时传入，最大限定是1<<30；

②、loadFactor是装载因子，紧张目的是用来确认table数组是否须要动态扩展，默认值是0.75，比如table数组大小为16，装载因子为0.75时，threshold便是12，当table的实际大小超过12时，table就须要动态扩容；

③、扩容时，调用 resize() 方法，将 table 长度变为原来的两倍（把稳是 table 长度，而不是 threshold）

④、数据很大的情形下，扩展时将会带来性能的丢失，在性能哀求很高的地方，这种丢失很可能很致命。

7.数组扩容的过程？

创建一个新的数组，其容量为旧数组的两倍，并重新打算旧数组中结点的存储位置。
结点在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小。

8.拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直利用红黑树？

之以是选择红黑树是为理解决二叉查找树的毛病，二叉查找树在分外情形下会变成一条线性构造（这就跟原来利用链表构造一样了，造成很深的问题），遍历查找会非常慢。
而红黑树在插入新数据后可能须要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树便是为了查找数据快，办理链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是须要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，以是当长度大于 8 的时候，会利用红黑树，如果链表长度很短的话，根本不须要引入红黑树，引入反而会慢。

9.红黑树，为什么不用二叉树、平衡树

红黑树实质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的根本上增加了一些规则：

1、每个节点非红即黑

2、根节点永久是玄色的

3、所有的叶子节点都是玄色的（如图中NULL节点）

4、每个赤色节点的两个字节点一定都是玄色；

5、从根节点到叶节点或空子节点的每条路径，必须包含相同数目的玄色节点（即相同的玄色高度）

之以是不用二叉树：

红黑树是一种平衡的二叉树，插入、删除、查找的最坏韶光繁芜度都为 O(logn)，避免了二叉树最坏情形下的O(n)韶光繁芜度。

之以是不用平衡二叉树：

平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，须要旋转的次数更多，也便是说平衡二叉树保持平衡的效率更低，以是平衡二叉树插入和删除的效率比红黑树要低。

10.jdk8 中对 HashMap 做了哪些改变？

在 java 1.8 中，如果链表的长度超过了 8，那么链表将转换为红黑树。
（桶的数量必须大于 64，小于 64 的时候只会扩容）

发生 hash 碰撞时，java 1.7 会在链表的头部插入，而 java 1.8 会在链表的尾部插入

在 java 1.8 中，Entry 被 Node 替代(换了一个马甲)。

11.HashMap，LinkedHashMap，TreeMap 有什么差异？

HashMap 参考其他问题；

LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历时，先取到的记录肯定是先插入的；遍历比 HashMap 慢；

TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器）

12.HashMap & TreeMap & LinkedHashMap 利用场景？

一样平常情形下，利用最多的是 HashMap。

HashMap：在 Map 中插入、删除和定位元素时；

TreeMap：在须要按自然顺序或自定义顺序遍历键的情形下；

LinkedHashMap：在须要输出的顺序和输入的顺序相同的情形下。

13.HashMap 和 HashTable 有什么差异？

相同点：

①、HashMap和Hashtable都实现了Map接口；②、都可以存储key-value数据。

不同点：

①、HashMap 是线程不屈安的，效率高，HashTable 是线程安全的，效率低；

②、HashMap最多只许可一条记录的键为null，许可多条记录的值为null，而 HashTable不许可；

③、HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast 的。

④、HashMap 默认初始化数组的大小为16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1；

⑤、HashMap 须要重新打算 hash 值，而 HashTable 直策应用工具的 hashCode；

14.HashMap遍历的五种最佳方法：

利用 Iterator 遍历 HashMap EntrySet

Iterator < Entry < Integer, String >> iterator = coursesMap.entrySet().iterator();while (iterator.hasNext()) { Entry < Integer, String > entry = iterator.next(); System.out.println(entry.getKey()); System.out.println(entry.getValue());}利用 Iterator 遍历 HashMap KeySet

Iterator < Integer > iterator = coursesMap.keySet().iterator();while (iterator.hasNext()) { Integer key = iterator.next(); System.out.println(key); System.out.println(coursesMap.get(key));}利用 For-each 循环迭代 HashMap

for (Map.Entry < Integer, String > entry: coursesMap.entrySet()) { System.out.println(entry.getKey()); System.out.println(entry.getValue());}利用 Lambda 表达式[4]遍历 HashMap

coursesMap.forEach((key, value) -> { System.out.println(key); System.out.println(value);});利用 Stream API[5] 遍历 HashMap

coursesMap.entrySet().stream().forEach((entry) - > { System.out.println(entry.getKey()); System.out.println(entry.getValue());});1.4.2ConcurrentHashMap

HashMap 是线程不屈安的，而线程安全的 Map 有 HashTable 和 ConcurrentHashMap。

ConcurrentHashMap 先容

①、主要的常量：private transient volatile int sizeCtl;

当为负数时，-1 表示正在初始化，-N 表示 N - 1 个线程正在进行扩容；

当为 0 时，表示 table 还没有初始化；

当为其他正数时，表示初始化或者下一次进行扩容的大小。

②、数据构造：

Node 是存储构造的基本单元，继续 HashMap 中的 Entry，用于存储数据；

TreeNode 继续 Node，但是数据构造换成了二叉树构造，是红黑树的存储构造，用于红黑树中存储数据；

TreeBin 是封装 TreeNode 的容器，供应转换红黑树的一些条件和锁的掌握。

③、存储工具时（put() 方法）： 1.如果没有初始化，就调用 initTable() 方法来进行初始化； 2.如果没有 hash 冲突就直接 CAS 无锁插入； 3.如果须要扩容，就前辈行扩容； 4.如果存在 hash 冲突，就加锁来担保线程安全，两种情形：一种是链脸色势就直接遍历到尾端插入，一种是红黑树就按照红黑树构造插入； 5.如果该链表的数量大于阀值 8，就要先转换成红黑树的构造，break 再一次进入循环 6.如果添加成功就调用 addCount() 方法统计 size，并且检讨是否须要扩容。

④、扩容方法 transfer()：默认容量为 16，扩容时，容量变为原来的两倍。

helpTransfer()：调用多个事情线程一起帮助进行扩容，这样的效率就会更高。

⑤、获取工具时（get()方法）：

1.打算 hash 值，定位到该 table 索引位置，如果是首结点符合就返回；

2.如果碰着扩容时，会调用标记正在扩容结点 ForwardingNode.find()方法，查找该结点，匹配就返回；

3.以上都不符合的话，就往下遍历结点，匹配就返回，否则末了就返回 null。

1.4.2.1 与 HashTable 比较

相同点：

1.HashTable 和 ConcurrentHashMap 的共同特点是不许可 key 和 value 为 null， 而 HashMap 就比较随意，都可以是 null。

2.HashTable 和 ConcurrentHashMap 的操作方法基本一样。
只是底层对锁的利用细节不一样。

3.都是线程安全的。

不同点：

1.HashTable 位于这个 java.util 包下，便是实现了HashMap加上synchronized，属于 fail-fast，不支持并发修正；对所有操作都加 synchronized，包括 get，以是效率低。

2.ConcurrentHashMap 位于 JUC（java.util.concurrent）包下，属于 fail-safe，它许可并发修正，但是无法担保在迭代过程中获取到最新的值；在检索数据时不须要锁，也不支持锁住全体表来阻挡其他线程的访问。

3.ConcurrentHashMap是1.5的产物，是HashTable的替代，比HashTable的扩展性更好。
（是 Java 并发包 java.util.concurrent 中供应的一个线程安全且高效的 HashMap 实现）。
读操作不加锁，由于HashEntry的value变量是volatile的，也能担保读取到最新的值。

4.ConcurrentHashMap在JDK 1.7 中利用分段锁（ReentrantLock + Segment + HashEntry），相称于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。
锁粒度：基于 Segment，包含多个 HashEntry。
JDK 1.8 中利用 CAS + synchronized + Node + 红黑树。
锁粒度：Node（首结点）（实现 Map.Entry<K,V>）。
锁粒度降落了。

HashTable 是利用 synchronize 关键字加锁的事理（便是对工具加锁），一把锁（锁住全体链表构造）处理并发问题，多个线程竞争一把锁，随意马虎壅塞；

1.4.2.2Java7 和 Java8 差异

jdk 版本

1.7

1.8

底层实现

数组+链表

数组+链表/红黑树

数据构造

Segment 数组 + HashEntry 节点

Node 节点

锁

分段锁，默认并发是 16，一旦初始化，Segment 数组大小就固定，后面不能扩容

CAS + synchronized 来担保并发安全性

put 操作

先获取锁，根据 key 的 hash 值定位到 Segment，再根据 key 的 hash 值找到详细的 HashEntry，再进行插入或覆盖，末了开释锁

根据 key 的 hash 值定位到 Node 节点，再判断首节点是否为空，空的话通过 cas 去赋值首节点 ；首节点非空的话，会用 synchronized 去锁住首节点，并判断是是同个首节点，是的话再去操作

开释锁

须要显示调用 unlock()

不须要

1.4.2.3Java7 版本

在 JDK1.7 中，它是由 Segment 数组 + HashEntry 组成 ，数据构造上和 HashMap（1.7）一样，仍旧是数组加链表。
它的一个最紧张特点便是分段锁 ，它默认许可的并发量是 16。
Segment 是 ConcurrentHashMap 中的一个内部类，通过继续了 ReentrantLock 这个可重入锁来进行加锁，以是每次须要加锁的操作锁住的是一个 segment，这样只要担保每个 Segment 是线程安全的，也就实现了全局的线程安全。

Segment 数组长度为 16，不可以扩容Segment[i] 的默认大小为 2，负载因子是 0.75，得出初始阈值为 1.5，也便是往后插入第一个元素不会触发扩容，插入第二个会进行第一次扩容这里初始化了 segment[0]，其他位置还是 null当前 segmentShift 的值为 32 - 4 = 28，segmentMask 为 16 - 1 = 15，姑且把它们翻译为移位数和掩码

put 源码

@SuppressWarnings("unchecked")public V put(K key, V value) { Segment<K,V> s; if (value == null) throw new NullPointerException(); // 1. 打算 key 的 hash 值 int hash = hash(key); // int j = (hash >>> segmentShift) & segmentMask; // 通过 UNSAFE 类去获取这个 Segment if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment // 关键步骤 1 s = ensureSegment(j); // 关键步骤 2 return s.put(key, hash, value, false);}// ensureSegment 方法中，这个方法紧张用来创建和获取 Segment @SuppressWarnings("unchecked")private Segment<K,V> ensureSegment(int k) { final Segment<K,V>[] ss = this.segments; long u = (k << SSHIFT) + SBASE; // raw offset Segment<K,V> seg; if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { Segment<K,V> proto = ss[0]; // use segment 0 as prototype int cap = proto.table.length; float lf = proto.loadFactor; int threshold = (int)(cap lf); HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap]; if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { // recheck Segment<K,V> s = new Segment<K,V>(lf, threshold, tab); // 利用 while 循环，内部用 CAS，当前哨程成功设值或其他线程成功设值后，退出 while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { // 关键步骤 3：利用到了 CAS 锁 if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s)) break; } } } return seg;}final V put(K key, int hash, V value, boolean onlyIfAbsent) { // 步骤 1 HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); V oldValue; try { HashEntry<K,V>[] tab = table; int index = (tab.length - 1) & hash; HashEntry<K,V> first = entryAt(tab, index); for (HashEntry<K,V> e = first;;) { if (e != null) { K k; // 步骤 2 if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { oldValue = e.value; if (!onlyIfAbsent) { e.value = value; ++modCount; } break; } e = e.next; } else { // 步骤 3 if (node != null) node.setNext(first); else node = new HashEntry<K,V>(hash, key, value, first); int c = count + 1; if (c > threshold && tab.length < MAXIMUM_CAPACITY) rehash(node); else setEntryAt(tab, index, node); ++modCount; count = c; oldValue = null; break; } } } finally { // 步骤 4 unlock(); } return oldValue;}

步骤 1：紧张浸染是上锁，tryLock()失落败的话会进入一个自旋获取锁的过程，不断的考试测验，当考试测验的次数大于最大次数 MAX_SCAN_RETRIES 时就调用 lock()获取锁（壅塞锁）

步骤 2：遍历 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等时如果 onlyIfAbsent=false 时覆盖旧的 value。

步骤 3：不为空则须要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否须要扩容。

步骤 4：末了会解除在 1 中所获取当前 Segment 的锁。

get 操作不用锁，事理也一样，根据 key 的 hash 值找到那个 segment，再找到里面的 hashEntry。

虽然 ConcurrentHashMap 办理了并发问题，但是由于数据构造和 1.7 的 HashMap 一样，以是查询效率低。

1.4.2.4Java8 版本

在 JDK1.8 中

1.引入了红黑树，缘故原由：链表查询韶光繁芜度 O(n)，插入韶光繁芜度 O(1)；而红黑树查询和插入韶光繁芜度都是 O(lgn)。
.

2 采取了 CAS + synchronized 来担保并发安全性，放弃原有的 Segment 分段锁 。

Node 节点

// volatile 润色是为了担保变量的可见性，禁止指令重排

put 源码

/ Implementation for put and putIfAbsent /final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 关键点 1 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { V oldVal = null; // 关键点 2 synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null;}

关键点 1：紧张通过 cas 的办法去设置首节点

关键点 2：通过 synchronized 去锁住这个首节点，接着通过 if (tabAt(tab, i) == f)去判断是不是同个首节点是的话再对个中的数据进行操作。

ConcurrentHashMap 在 JDK 1.8 中，为什么要利用内置锁 synchronized 来代替重入锁 ReentrantLock？

①、粒度降落了；

②、JVM 开拓团队没有放弃 synchronized，而且基于 JVM 的 synchronized 优化空间更大，更加自然。

③、在大量的数据操作下，对付 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存。

1.5 常见问题1.5.1fail-fast 和 fail-safe 迭代器的差异

快速失落败（fail-fast）：快速失落败是Java凑集的一种缺点检测机制。

事理：迭代器在遍历时直接访问凑集中的内容，并且在遍历过程中利用一个 modCount 变量。
凑集在被遍历期间如果内容发生变革，就会改变modCount的值。
每当迭代器利用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出非常，终止遍历。

把稳：这里非常的抛出条件是检测到 modCount！
=expectedmodCount 这个条件。
如果凑集发生变革时修正modCount值刚好又设置为了expectedmodCount值，则非常不会抛出。
因此，不能依赖于这个非常是否抛出而进行并发操作的编程，这个非常只建议用于检测并发修正的bug。

场景：java.util包下的凑集类都是快速失落败的，不能在多线程下发生并发修正（迭代过程中被修正），比如ArrayList 类。

安全失落败（fail-safe）

采取安全失落败机制的凑集容器，在遍历时不是直接在凑集内容上访问的，而是先复制原有凑集内容，在拷贝的凑集上进行遍历。
这种遍历基于容器的一个克隆。
因此对容器中的内容修正不影响遍历。

事理：由于迭代时是对原凑集的拷贝进行遍历，以是在遍历过程中对原凑集所作的修正并不能被迭代器检测到，以是不会触发Concurrent Modification Exception。

缺陷：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修正后的内容，即：迭代器遍历的是开始遍历那一刻拿到的凑集拷贝，在遍历期间原凑集发生的修正迭代器是不知道的。

场景：java.util.concurrent包下的容器都是安全失落败，可以在多线程下并发利用，并发修正，比如CopyOnWriteArrayList类。
常见的利用 fail-safe 办法遍历的容器有 ConcurrentHashMap 和 CopyOnWriteArrayList。

1.5.2Java 中线程安全的基本数据构造有哪些

HashTable、ConcurrentHashMap: 哈希表的线程安全版，效率上后者高；Vector、CopyOnWriteArrayList：线程安全版 Arraylist；Stack：线程安全版栈；BlockingQueue 及其子类：线程安全版行列步队。

1.5.3HashMap 和 Hashtable 的差异线程安全：Hashtable 方法 sychonized 润色，线程安全。
建议利用ConcurrentHashMap替代Hashtable。
效率方面：由于 Hashtable 方法被 sychonized 润色，效率比 HashMap 低底层数据构造：HashMap jdk8 当链表长度>=8 并且数组长度>=64 链表会转红黑树，Hashtable 没有这样机制初始容量与扩容：默认初始量：Hashtable 为 11，HashMap 为 16；若指定初始量：Hashtable 用指定的值，HashMap 会扩为 2 的幂次⽅⼤⼩。
扩容：Hashtable 容量变为原来 2n+1 倍，HashMap 变为 2 倍。
对 Null key 与 Null value 支持：HashMap 支持一个 Null key 多个 Null value，Hashtable 不支持 Null key，否则报错空指针非常1.5.4HashMap 并发线程安全问题？

HashMap不是线程安全的。

多线程下扩容去世循环。
JDK1.7 中的 HashMap 利用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的涌现，形成去世循环。
因此，JDK1.8 利用尾插法插入元素，在扩容时会保持链表元素原来的顺序，不会涌现环形链表的问题。
多线程的 put 可能导致元素的丢失。
多线程同时实行 put 操作，如果打算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。
此问题在 JDK 1.7 和 JDK 1.8 中都存在。
put 和 get 并发时，可能导致 get 为 null。
线程 1 实行 put 时，由于元素个数超出 threshold 而导致 rehash，线程 2 此时实行 get，有可能导致这个问题。
这个问题在 JDK 1.7 和 JDK 1.8 中都存在。

办理HashMap线程不屈安方案：1、利用HashTable代替HashMap；2、利用Collections.synchronizedMap；3、利用ConcurrentHashMap代替HashMap。

HashTable 是直接在操作方法上加 synchronized 关键字，锁住全体table数组，粒度比较大；Collections.synchronizedMap 是利用 Collections 凑集工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 工具，内部定义了一个工具锁，方法内通过工具锁实现；ConcurrentHashMap 在jdk1.7中利用分段锁，在jdk1.8中利用CAS+synchronized。
1.5.5hashmap 扩容流程

扩容时多线程操作可能会导致链表成环的涌现，然后调⽤ get ⽅法会去世循环

触发机遇：

1、未初始化，第一次 put 时；

2、大于扩容阈值。

流程：新建 2 倍大小的数组，根据新数组长度对其值重新 hash，寻址。
具体会将原来数组链表拆为高低位链表，低位链表存放扩容后数组下标没变的结点，高位链表存放变了的，然后将高低位链表插入新数组

1.5.6TreeMap

TreeMap 是基于红黑树的一种供应顺序访问的 Map，紧张是担保数据平衡，操作的韶光繁芜度都是 O(logn)；默认按键的升序排序，详细顺序可有指定的 comparator 决定。
TreeMap 键、值都不能为 null；hashtable 也不能为 null。
HashMap和TreeMap 都是非线性安全的，多线程并发情形建议利用ConcurrentHashMap；若既要担保线程安全又要担保顺序，可利用Collections.synchronizedMap()方法转化为线程安全的凑集。

HashMap

TreeMap

Definition

HashMap是基于哈希表的Map接口实现。
底层：哈希表+数组。

TreeMap是基于Tree构造的Map接口的实现。
底层：红黑树。

Interface Implements

HashMap实现Map, Cloneable和Serializable接口。

TreeMap实现NavigableMap, Cloneable和Serializable接口。

空键/值

HashMap许可单个null键和多个null值。

TreeMap不许可利用空键, 但可以具有多个空值。

同质/异质

HashMap许可异构元素, 由于它不对键实行排序。

由于排序, TreeMap许可将齐次值作为键。

Performance

HashMap比TreeMap更快, 由于它为诸如get()和put()之类的基本操作供应了O（1）的恒定时间性能。

与HashMap比较, TreeMap速率较慢, 由于它为大多数操作（如add(), remove()和contains()）供应O（log（n））的性能。
紧张担保数据构造平衡。

扩容

HashMap可以调度初始容量大小和扩容。

TreeMap没有大小设置选项，由于，红黑树构造总是处于平衡状态。

Comparison Method

它利用Object类的equals()方法比较键。
Map类的equals()方法将其覆盖。

它利用compareTo()方法比较键。

Functionality

HashMap类仅包含诸如get(), put(), KeySet()等基本功能。

TreeMap类具有丰富的功能, 由于它包含如下功能：tailMap(), firstKey(), lastKey(), pollFirstEntry(), pollLastEntry()。

元素顺序

HashMap不掩护任何顺序。

元素以自然顺序（升序）排序。

Uses

无序利用HashMap，适用于插入、删除和定位元素。

当我们须要按排序（升序）顺序的键值对时, 应利用TreeMap

1.5.7List中的坑

1.Arrays.asList转换基本类型数组的坑

int[] arr = {1, 2, 3}; List list = Arrays.asList(arr); System.out.println(list.size()); // 1 想要转成的List该当是有三个工具而现在只有一个

源码中asList方法吸收的是一个泛型T类型的参数，T继续Object工具。
通过断点我们可以看到把 int数组 整体作为一个工具,返回了一个 List<int[]>。

办理方案：

方案一：Java8以上，利用Arrays.stream(arr).boxed()将装箱为Integer数组。

List collect = Arrays.stream(arr).boxed().collect(Collectors.toList()); System.out.println(collect.size()); System.out.println(collect.get(0).getClass()); // 3 // class java.lang.Integer

方案二：声明数组的时候，声明类型改为包装类型。

Integer[] integerArr = {1, 2, 3}; List integerList = Arrays.asList(integerArr); System.out.println(integerList.size()); System.out.println(integerList.get(0).getClass()); // 3 // class java.lang.Integer2.Arrays.asList返回的List不支持增删操作

private static void asListAdd(){ String[] arr = {"1", "2", "3"}; List strings = Arrays.asList(arr); // 办理方案：new ArrayList<>(Arrays.asList(arr)); // 修正后iterator.remove()不会抛非常 // List<String> strings = new ArrayList<>(Arrays.asList(arr)); arr[2] = "4"; System.out.println(strings.toString()); Iterator<String> iterator = strings.iterator(); while (iterator.hasNext()){ if ("4".equals(iterator.next())){ iterator.remove(); // 抛java.lang.UnsupportedOperationException } }}

Arrays.asList(arr) 返回的 ArrayList 不是 java.util.ArrayList，而是 Arrays的内部类，它没有实现 AbstractList 中的 add() 和 remove() 方法，以是不支持新增和删除。

3.Arrays.asList返回的List会随原始数组的修正而变革

asList中创建了ArrayList，但是他直接引用了原来的数组工具以是只要原来的数组工具一发生变革，List也随着变革，以是在利用到引用的时候，我们须要特殊的把稳。

办理方案：重新new一个新的 ArrayList 来装返回的 List。

List strings = new ArrayList<>(Arrays.asList(arr));4.ArrayList不当增删操作

详见1.3.6

foreach中操作增删，由于 modCount 会被修正，与第一步保存的数组修正次数不一致，抛出非常ConcurrentModificationException，精确操作：

5.ArrayList的 subList 强转 ArrayList 导致非常

ArrayList的sublist结果不可強转成ArrayList,否则会抛出ClassCastException非常，即java.util.RandomAccesSubList cannot be cast to java. util.ArrayList。

解释: subList 返回的是ArrayList 的内部类SubList, 并不是ArrayList ，而是ArrayList的一个视图，対于SubList子列表的所有操作终极会反响到原列表上。

private static void subListTest(){ List<String> names = new ArrayList<String>() {{ add("one"); add("two"); add("three"); }}; // ArrayList strings = (ArrayList) names.subList(0, 1);// 缺点操作，抛非常 // System.out.println(strings.toString()); // List strings1= names.subList(0, 1); // 此操作不能增删元素 // 办理ConcurrentModificationException非常，用new ArrayList(names.subList(0, 1)) List strings1 = new ArrayList(names.subList(0, 1)); strings.add(0, "ongChange"); System.out.println(strings1.toString()); // [ongChange, one] System.out.println(names.toString()); // [ongChange, one, two, three] names.add("four"); // 缺点操作，导致modCount不一致 System.out.println(strings1.toString()); // 抛java.util.ConcurrentModificationException System.out.println(names.toString());}

办理方案：在操作SubList的时候，new一个新的ArrayList来吸收创建subList结果的拷贝

List strings = new ArrayList(names.subList(0, 1));6.ArrayList的 subList 切片造成OOM

subList所产生的List，实在是对原来List工具的引用，产生的List只是原来List工具的视图，也便是说虽然值切片获取了一小段数据，但是原来的List工具却得不到回收，原来的List工具若是一个很大的工具，就可能导致OOM。
为了方便我们测试，将vm调度一下 -Xms20m -Xmx40m

private static void subListOomTest(){ IntStream.range(0, 1000).forEach(i ->{ List<Integer> collect = IntStream.range(0, 100000).boxed().collect(Collectors.toList()); data.add(collect.subList(0, 1)); });}

循环1000次创建了1000个具有10万个元素的List，由于始终被collect.subList(0, 1)强引用，得不到回收。

办理办法：

办法一：在subList方法返回后，重新利用new ArrayList，来构建一个独立的ArrayList。

List list = new ArrayList<>(collect.subList(0, 1));

办法二：利用Java8的Stream中的skip和limit来达到切片的目的。

List list = collect.stream().skip(0).limit(1).collect(Collectors.toList());

办法三：用一个新的容器来装结果，割断与原始List的关系。

7.LinkedList的插入速率不一定比ArrayList快对付数组，随机元素访问的韶光繁芜度是0(1)，元素插入操作是O(n)；对付链表，随机元素访问的韶光繁芜度是O(n)，元素插入操作是0(1)。

元素插入对付链表来说该当是他的上风，但是它就一定比数组快? 我们实行插入1000w次的操作。

private static void test(){ StopWatch stopWatch = new StopWatch(); int elementCount = 100000; stopWatch.start("ArrayList add"); List<Integer> arrayList = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(ArrayList::new)); // ArrayList插入数据 IntStream.rangeClosed(0, elementCount).forEach(i ->arrayList.add(ThreadLocalRandom.current().nextInt(elementCount), 1)); stopWatch.stop(); stopWatch.start("linkedList add"); List<Integer> linkedList = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(LinkedList::new)); // ArrayList插入数据 IntStream.rangeClosed(0, elementCount).forEach(i -> linkedList.add(ThreadLocalRandom.current().nextInt(elementCount), 1)); stopWatch.stop(); System.out.println(stopWatch.prettyPrint());}StopWatch '': running time = 44507882 ns---------------------------------------------ns % Task name---------------------------------------------043836412 098% elementCount 100 ArrayList add000671470 002% elementCount 100 linkedList addStopWatch '': running time = 196325261 ns---------------------------------------------ns % Task name---------------------------------------------053848980 027% elementCount 10000 ArrayList add142476281 073% elementCount 10000 linkedList addStopWatch '': running time = 26384216979 ns---------------------------------------------ns % Task name---------------------------------------------978501580 004% elementCount 100000 ArrayList add25405715399 096% elementCount 100000 linkedList add

看到在实行插入1万、10完次操作的时候，LinkedList的插入操作韶光是ArrayList的两倍以上。
以是在实际的利用中，如果涉及到头尾工具的操作，可以利用LinkedList数据构造来进行增删的操作，发挥LinkedList的上风。

8.CopyOnWriteArrayList内存占用过多

CopyOnWrite，顾名思义便是写的时候会将共享变量新复制一份出来，这样做的好处是读操作完备无锁。

CopyOnWriteArrayList的add()方法

public boolean add(E e) { // 获取独占锁 final ReentrantLock lock = this.lock; lock.lock(); try { // 获取array Object[] elements = getArray(); // 复制array到新数组，添加元素到新数组 int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len + 1); newElements[len] = e; // 更换数组 setArray(newElements); return true; } finally { // 开释锁 lock.unlock(); }}

CopyOnWriteArrayList 内部掩护了一个数组，成员变量 array 就指向这个内部数组，所有的读操作都是基于新的array工具进行的。

由于上了独占锁，以是如果多个线程调用add()方法只有一个线程会获得到该锁，其他线程被壅塞，知道锁被开释， 由于加了锁，以是全体操作的过程是原子性操作，CopyOnWriteArrayList 会将新的array复制一份，然后在新复制处理的数组上实行增加元素的操作，实行完之后再将复制的结果指向这个新的数组。

由于每次写入的时候都会对数组工具进行复制，复制过程不仅会占用双倍内存，还须要花费 CPU 等资源，以是当列表中的元素比较少的时候，这对内存和 GC 并没有多大影响，但是当列表保存了大量元素的时候，对 CopyOnWriteArrayList 每一次修正，都会重新创建一个大工具，并且原来的大工具也须要回收，这都可能会触发 GC，如果超过老年代的大小则随意马虎触发Full GC，引起运用程序永劫光停顿。

9.CopyOnWriteArrayList是弱同等性的

public Iterator<E> iterator() { return new COWIterator<E>(getArray(), 0);}static final class COWIterator<E> implements ListIterator<E> { / Snapshot of the array / private final Object[] snapshot; / Index of element to be returned by subsequent call to next. / private int cursor; private COWIterator(Object[] elements, int initialCursor) { cursor = initialCursor; snapshot = elements; } public boolean hasNext() { return cursor < snapshot.length; } public boolean hasPrevious() { return cursor > 0; } @SuppressWarnings("unchecked") public E next() { if (! hasNext()) throw new NoSuchElementException(); return (E) snapshot[cursor++]; }}

源码中看到调用iterator方法获取迭代器返回一个COWIterator工具，COWIterator的布局器里紧张是保存了当前的list工具的内容和遍历list时数据的下标。
snapshot是list的快照信息，由于CopyOnWriteArrayList的读写策略中都会利用getArray()来获取一个快照信息，天生一个新的数组。
以是在利用该迭代器元素时，其他线程对该lsit操作是不可见的，由于操作的是两个不同的数组以是造成弱同等性。

private static void CopyOnWriteArrayListTest(){ CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList(); list.add("test1"); list.add("test2"); list.add("test3"); list.add("test4"); Thread thread = new Thread(() -> { System.out.println(">>>> start"); list.add(1, "replaceTest"); list.remove(2); }); // 在启动线程前获取迭代器 Iterator<String> iterator = list.iterator(); thread.start(); try { // 等待线程实行完毕 thread.join(); } catch (InterruptedException e) { e.printStackTrace(); } while (iterator.hasNext()){ System.out.println(iterator.next()); }}>>>> starttest1test2test3test4

上面的demo中在启动线程前获取到了原来list的迭代器，在之后启动新建一个线程，在线程里面修正了第一个元素的值，移除了第二个元素，在实行完子线程之后，遍历了迭代器的元素，创造子线程里面操作的一个都没有生效，这里提现了迭代器弱同等性。

10.CopyOnWriteArrayList的迭代器不支持增编削

private static void CopyOnWriteArrayListTest(){ CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(); list.add("test1"); list.add("test2"); list.add("test3"); list.add("test4"); Iterator<String> iterator = list.iterator(); while (iterator.hasNext()){ if ("test1".equals(iterator.next())){ iterator.remove();// 抛java.lang.UnsupportedOperationException } } System.out.println(list.toString());}

CopyOnWriteArrayList 迭代器是只读的，不支持增删操作CopyOnWriteArrayList迭代器中的 remove()和 add()方法，没有支持增删而是直接抛出了非常，由于迭代器遍历的仅仅是一个快照，而对快照进行增编削是没故意义的。

标签：数组list