Java集合 • FXJ Wiki

Java 集合概览#

似乎我在 java 集合部分中的源码分析部分，了解的不够？但是时间不多了！需要加把劲了！

Java 集合概览#

由两大接口派生而来：一个是 Collection 接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于 Collection 接口，下面又有三个主要的子接口：List、Set 、 Queue。

这里只列举了主要的继承派生关系，并没有列举所有关系。

List

ArrayList：Object[] 数组。详细可以查看：ArrayList 源码分析。
Vector：Object[] 数组。
LinkedList：双向链表 (JDK 1.6 之前为循环链表，JDK 1.7 取消了循环)。详细可以查看：LinkedList 源码分析。

Set

HashSet (无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素。
LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。
TreeSet (有序，唯一): 红黑树 (自平衡的排序二叉树)。

Queue

PriorityQueue: Object[] 数组来实现小顶堆。详细可以查看：PriorityQueue 源码分析。
DelayQueue: PriorityQueue。详细可以查看：DelayQueue 源码分析。
ArrayDeque: 可扩容动态双向数组。

Map

HashMap：JDK 1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK 1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。详细可以查看：HashMap 源码分析。
LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：LinkedHashMap 源码分析
Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。
TreeMap：红黑树（自平衡的排序二叉树）。

一些较为重点的问题#

加*的代表是重点！总的来说：ArrayList ，LinkedList， HashMap，ConcurrentHashMap 为重点！其他的了解即可。

ArrayList 底层的实现原理是什么#

ArrayList 底层是用动态的数组实现的
ArrayList 初始容量为 0，当第一次添加数据的时候才会初始化容量为 10
ArrayList 在进行扩容的时候是原来容量的 1.5 倍，每次扩容都需要拷贝数组
ArrayList 在添加数据的时候
- 确保数组已使用长度(size)加 1 之后足够存下下一个数据
- 计算数组的容量，如果当前数组民使用长度+1 后的大于当前的数组长度，则调用 grow 方法扩容（原来的 1.5倍）
- 确保新增的数据有地方存储之后，则将新元素添加到位于 size 的位置上。
- 返回添加成功布尔值。

new ArrayList(10) list 扩容几次？0 次

如何实现数组和 List 之间的转换#

数组转 List ，使用 JDK 中 java.util.Arrays 工具类的 asList 方法
List 转数组，使用 List 的 toArray 方法。无参 toArray 方法返回 Object 数组，传入初始化长度的数组对象，返回该对象数组

面试官再问:

用 Arrays.asList 转 List 后，如果修改了数组内容，list 受影响吗? -> 受影响
List 用 toArray 转数组后，如果修改了 List 内容，数组受影响吗? -> 不受影响答：
Arrays.asList 转换 list 之后，如果修改了数组的内容，list 会受影响因为它的底层使用的 Arrays 类中的一个内部类 ArrayList 来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址
list 用了 toArray 转数组后，如果修改了 list 内容，数组不会影响，当调用了 toArray 以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使 list 修改了以后，数组也不受影响

ArrayList 和 LinkedList 的区别是什么?(*)#

ArrayList 与 LinkedList 区别?

HashMap 的底层实现(*)#

HashMap 的底层实现

JDK 1.7 和 1.8 的 HashMap 有什么区别？

HashMap 的 put 操作具体流程(*)#

流程图：

(重)

判断键值对数组 table 是否为空或为 null，否则执行 resize()进行扩容(初始化)
根据键值 key 计算 hash 值得到数组索引
如果 table[i]==null 条件成立，直接新建节点添加
如果 table[i]!=null
- 判断 table[i]的首个元素是否和 key 一样，如果相同直接覆盖 value
- 判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对
- 遍历 table[i]，链表的尾部插入数据，然后判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现 key 已经存在直接覆盖 value
插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold (数组长度*0.75)，如果超过，进行扩容

HashMap 的扩容机制是什么？#

流程图：

在添加元素或初始化的时候需要调用 resize 方法进行扩容，第一次添加数据初始化数组长度为 16，以后每次每次扩容都是达到了扩容阈值(数组长度*0.75)
每次扩容的时候，都是扩容之前容量的 2 倍(可以保证每次都是 2 的幂);
扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
- 没有 hash 冲突的节点，则直接使用 e.hash &(newCap-1)计算新数组的索引位置
- 如果是红黑树，走红黑树的添加
- 如果是链表，则需要遍历链表，可能需要拆分链表，判断 (e.hash & oldCap) 是否为 0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

HashMap 的寻址算法？#

HashMap JDK 1.7 在多线程下死循环问题#

参考视频：

在 jdk 1.7 的 hashmap 中在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环

比如说，现在有两个线程线程一:读取到当前的 hashmap 数据，数据中一个链表，在准备扩容时，线程二介入线程二:也读取 hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是 AB，扩容后的顺序是 BA，线程二执行结束。

线程一:继续执行的时候就会出现死循环的问题。线程一先将 A 移入新的链表，再将 B 插入到链头，由于另外一个线程的原因，B 的 next 指向了 A，所以 B->A->&,形成循环。当然，JDK 8 将扩容算法做了调整，不再将元素加入链表头(而是保持与扩容前一样的顺序)，尾插法，就避免了 idk 7中死循环的问题。

List 相关常见知识#

ArrayList 和 Array（数组）的区别？#

ArrayList 内部基于动态数组实现，比 Array（静态数组）使用起来更加灵活：

ArrayList 会根据实际存储的元素动态地扩容或缩容，而 Array 被创建之后就不能改变它的长度了。
ArrayList 允许你使用泛型来确保类型安全，Array 则不可以。
ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。Array 可以直接存储基本类型数据，也可以存储对象。
ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 add ()、remove ()等。Array 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。
ArrayList 创建时不需要指定大小，而 Array 创建时必须指定大小。

 // 初始化一个 String 类型的数组
 String[] stringArr = new String[]{"hello", "world", "!"};
 // 修改数组元素的值
 stringArr[0] = "goodbye";
 System.out.println(Arrays.toString(stringArr));// [goodbye, world, !]
 // 删除数组中的元素，需要手动移动后面的元素
 for (int i = 0; i < stringArr.length - 1; i++) {
     stringArr[i] = stringArr[i + 1];
 }
 stringArr[stringArr.length - 1] = null;
 System.out.println(Arrays.toString(stringArr));// [world, !, null]

java

// 初始化一个 String 类型的 ArrayList
 ArrayList<String> stringList = new ArrayList<>(Arrays.asList("hello", "world", "!"));
// 添加元素到 ArrayList 中
 stringList.add("goodbye");
 System.out.println(stringList);// [hello, world, !, goodbye]
 // 修改 ArrayList 中的元素
 stringList.set(0, "hi");
 System.out.println(stringList);// [hi, world, !, goodbye]
 // 删除 ArrayList 中的元素
 stringList.remove(0);
 System.out.println(stringList); // [world, !, goodbye]

java

ArrayList 与 LinkedList 区别?#

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

一般不会使用 LinkedList ，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好。

RandomAccess 接口#

public interface RandomAccess {
}

java

实际上 RandomAccess 接口中什么都没有定义。所以 RandomAccess 接口不过是一个标识罢了。 标识实现这个接口的类具有随机访问功能。

在 binarySearch() 方法中，它要判断传入的 list 是否 RandomAccess 的实例，如果是，调用 indexedBinarySearch()方法，如果不是，那么调用 iteratorBinarySearch()方法

双向链表与双向循环链表#

ArrayList 插入和删除元素的时间复杂度？#

非常好理解，复杂度和想象一样，和数组本质也一样。

插入：

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

删除：

头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O (n)。
尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O (1)。
指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O (n)。

LinkedList 插入和删除元素的时间复杂度？#

LinkList 为双向链表，值得注意。

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

杂项：#

ArrayList 和 Vector 的区别?#

ArrayList 是 List 的主要实现类，底层使用 Object[]存储，适用于频繁的查找工作，线程不安全。
Vector 是 List 的古老实现类，底层使用 Object[] 存储，线程安全。

Vector 和 Stack 的区别?#

Vector 和 Stack 两者都是线程安全的，都是使用 synchronized 关键字进行同步处理。
Stack 继承自 Vector，是一个后进先出的栈，而 Vector 是一个列表。

ArrayList 可以添加 null 值吗？#

ArrayList 中可以存储任何类型的对象，包括 null 值。不过，不建议向 ArrayList 中添加 null 值， null 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。

Map 相关常见知识#

HashMap 和 Hashtable 的区别#

HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过 synchronized 修饰。（保证线程安全使用 ConcurrentHashMap ）；
hashtable 效率略低，基本被淘汰
对 Null key 和 Null value 的支持
- HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；
- Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同
- 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
- 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的 tableSizeFor() 方法保证）
底层数据结构
- JDK 1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间。
- Hashtable 没有这样的机制。
哈希函数的实现：HashMap 对哈希值进行了高位和低位的混合扰动处理以减少冲突，而 Hashtable 直接使用键的 hashCode() 值。

保证了 HashMap 总是使用 2 的幂作为哈希表的大小。

/**
 * Returns a power of two size for the given target capacity.
 * 找到大于或等于 cap 的最小2的幂
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

java

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

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

HashMap 和 HashSet 区别#

HashSet 底层就是基于 HashMap 实现。除了 clone()、writeObject()、readObject() 是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

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() 等方法可以方便地访问和移除元素。

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

public class Person {
    private Integer age;
	//...
    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });
		/*也可以用lambda表达式
		TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
		  int num = person1.getAge() - person2.getAge();
		  return Integer.compare(num, 0);
		});
		*/

        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

java

TreeMap 中的元素已经是按照 Person 的 age 字段的升序来排列了。

相比于 HashMap 来说， TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

HashSet 如何检查重复?#

在 JDK 1.8 中，HashSet 的 add()方法只是简单的调用了 HashMap 的 put()方法，并且判断了一下返回值以确保是否有重复元素。 HashSet 中的源码:

// 返回值：当 set 中没有包含 add 的元素时返回真
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

java

在 HashMap 的 putVal() 方法(put 方法会调用 putVal 方法) 中也能看到如下说明：

// 返回值：如果插入位置没有元素返回null，否则返回上一个元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
...
}

java

即在 JDK 1.8 中，实际上无论 HashSet 中是否已经存在了某元素，HashSet 都会直接插入，只是会在 add() 方法的返回值处告诉我们插入前是否存在相同元素

HashMap 的底层实现#

JDK 1.8 之前 HashMap 底层是数组和链表结合在一起使用也就是链表散列。HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。 ^45b49e

拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。如图：

^8b5a78

HashMap 中的扰动函数（hash 方法）是用来优化哈希值的分布。通过对原始的 hashCode() 进行额外处理，扰动函数可以减小由于糟糕的 hashCode() 实现导致的碰撞，从而提高数据的分布均匀性。

//JDK1.8
	static final int hash(Object key) {
		int h;
	  // key.hashCode()：返回散列值也就是hashcode
	  // ^：按位异或
	  // >>>:无符号右移，忽略符号位，空位都以0补齐
	  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
//JDK.7
	static int hash(int h) {
		// This function ensures that hashCodes that differ only by
		// constant multiples at each bit position have a bounded
		// number of collisions (approximately 8 at default load factor).
	
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

java

JDK 1.8 之后在解决哈希冲突时有了较大的变化(1.7 及其之前为拉链法)，当链表长度大于阈值（默认为 8），且总元素个数超过 64时，将链表转化为红黑树，以减少搜索时间。

HashMap 源码链表到红黑树的转换#

进入 HashMap 源码，然后搜索 treeifyBin 即可看到。

在 putVal 方法中有一段代码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
			   boolean evict) {
		//..
			for (int binCount = 0; ; ++binCount) {
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					//TREEIFY_THRESHOLD = 8
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						//红黑树转换（并不会直接转换成红黑树）
						treeifyBin(tab, hash);
					break;
				}
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		//...
}

java

对于 treeifyBin 方法：需要判断是否真的要转换为红黑树

final void treeifyBin(Node<K,V>[] tab, int hash) {
	int n, index; Node<K,V> e;
	//MIN_TREEIFY_CAPACITY = 64 判断当前数组的长度是否小于 64
	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
		//小于，进行数组扩容
		resize();
	else if ((e = tab[index = (n - 1) & hash]) != null) {
		//转化为红黑树
		TreeNode<K,V> hd = null, tl = null;
		do {
			TreeNode<K,V> p = replacementTreeNode(e, null);
			if (tl == null)
				hd = p;
			else {
				p.prev = tl;
				tl.next = p;
			}
			tl = p;
		} while ((e = e.next) != null);
		if ((tab[index] = hd) != null)
			hd.treeify(tab);
	}
}

java

将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树。

HashMap 多线程操作导致死循环问题#

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

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

HashMap 为什么线程不安全？#

JDK 1.7 及之前版本，在多线程环境下，HashMap 扩容时会造成死循环和数据丢失的问题。

数据丢失这个在 JDK 1.7 和 JDK 1.8 中都存在。

JDK 1.8 后，在 HashMap 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对 HashMap 的 put 操作会导致线程不安全，具体来说会有数据覆盖的风险。

参考 HashMap putVal 的源码

同时进行 put 操作，并且发生了哈希冲突：

同时 put 操作导致 size 的值不正确，进而导致数据覆盖的问题：(这里描述的是很常见的多线程问题)

HashMap 常见的遍历方式#

HashMap 的 7 种遍历方式与性能分析 ↗

大致分为：

迭代器遍历
1. EntrySet
2. KeySet
For Each 遍历 3. EntrySet 4. KeySet

Lambda 遍历-JDK 1.8+

Stream 流遍历-JDK.8+(分为 6.单线程和 7. 多线程)

// 创建并赋值 HashMap
Map<Integer, String> map = new HashMap();
map.put(1, "Java");
map.put(2, "JDK");
map.put(3, "Spring Framework");
map.put(4, "MyBatis framework");
map.put(5, "Java中文社群");

java

// 1遍历 iterator entrySet
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());
}
 
// 2遍历 iterator keySet
Iterator<Integer> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
	Integer key = iterator.next();
	System.out.println(key);
	System.out.println(map.get(key));
}

 // 3遍历 foreach entrySet
for (Map.Entry<Integer, String> entry : map.entrySet()) {
	System.out.println(entry.getKey());
	System.out.println(entry.getValue());
}

// 4遍历 foreach  keySet
for (Integer key : map.keySet()) {
	System.out.println(key);
	System.out.println(map.get(key));
}

// 5遍历 lambda
map.forEach((key, value) -> {
	System.out.println(key);
	System.out.println(value);
});

// 6遍历 Streams API 单线程
map.entrySet().stream().forEach((entry) -> {
	System.out.println(entry.getKey());
	System.out.println(entry.getValue());
});

// 7遍历 Streams API 多线程
map.entrySet().parallelStream().forEach((entry) -> {
	System.out.println(entry.getKey());
	System.out.println(entry.getValue());
});

java

对于 HashMap 遍历的性能分析：

存在阻塞时 parallelStream 性能最高, 非阻塞时 parallelStream 性能最低。

当遍历不存在阻塞时, parallelStream 的性能是最低的：

Benchmark               Mode  Cnt     Score      Error  Units
Test.entrySet           avgt    5   288.651 ±   10.536  ns/op
Test.keySet             avgt    5   584.594 ±   21.431  ns/op
Test.lambda             avgt    5   221.791 ±   10.198  ns/op
Test.parallelStream     avgt    5  6919.163 ± 1116.139  ns/op

java

加入阻塞代码 Thread.sleep(10)后, parallelStream 的性能才是最高的:

Benchmark               Mode  Cnt           Score          Error  Units
Test.entrySet           avgt    5  1554828440.000 ± 23657748.653  ns/op
Test.keySet             avgt    5  1550612500.000 ±  6474562.858  ns/op
Test.lambda             avgt    5  1551065180.000 ± 19164407.426  ns/op
Test.parallelStream     avgt    5   186345456.667 ±  3210435.590  ns/op

java

ConcurrentHashMap的底层实现 (和 Hashtable 的区别)#

在实现线程安全的方式上不同。

底层数据结构：
- JDK 1.7 的 ConcurrentHashMap 底层采用分段的数组+链表实现，JDK 1.8 采用的数据结构跟 HashMap 1.8 的结构一样，数组+链表/红黑二叉树。
- JDK 1.8 之前的 HashMap 的底层数据结构类似都是采用数组+链表的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
- Hashtable 采用数组+链表的形式
实现线程安全的方式（重要）：
- 在 JDK 1.7 的时候，ConcurrentHashMap 对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据（下面有示意图），多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
- 到了 JDK 1.8 的时候，ConcurrentHashMap 已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK 1.6 以后 synchronized 锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK 1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
- Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

JDK 1.8 之前的 HashMap 和 HashTable 都是使用的数组+链表的形式下图示意可以结合原笔记中的结构图一起看。

JDK 1.7#

JDK 1.8 之前的 ConcurrentHashMap：由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 数组中的每个元素包含一个 HashEntry 数组，每个 HashEntry 数组属于链表结构。

即 Segment 数组 + HashEntry 数组 + 链表

首先将数据分为一段一段（这个“段”就是 Segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

Segment 继承了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

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

java

一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。

Segment 的结构和 HashMap (JDK 1.8 之前)类似，是一种数组和链表结构。

一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。也就是说，对同一 Segment 的并发写入会被阻塞，不同 Segment 的写入是可以并发执行的。

JDK 1.8#

JDK 1.8 及其之后的为：Node 数组 + 链表 / 红黑树(与 HashMap JDK1.8 之后的实现相似)

Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。

源码：

static final class TreeBin<K,V> extends Node<K,V> {
        TreeNode<K,V> root;
        volatile TreeNode<K,V> first;
        volatile Thread waiter;
        volatile int lockState;
        // values for lockState
        static final int WRITER = 1; // set while holding write lock
        static final int WAITER = 2; // set when waiting for write lock
        static final int READER = 4; // increment value for setting read lock
		//...
}

java

ConcurrentHashMap 取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。

JDK 1.7 和 JDK1.8 实现的区别#

线程安全实现方式：
- JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。
- JDK 1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。
Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK 1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。
并发度：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。

ConcurrentHashMap 为什么 key 和 value 不能为 null？#

ConcurrentMaps（ConcurrentHashMaps，ConcurrentSkipListMaps）不允许使用 null 的主要原因是，在非并发映射中可能刚好可以容忍的歧义，无法得到容纳。主要原因是，如果 map.get(Key) 返回 null，则无法检测键是否显式地映射到 null 还是未映射键。在非并发映射中，您可以通过 map.contains(Key) 来检查这一点，但在并发映射中，map 可能在调用之间发生变化。

多线程下无法正确判定键值对是否存在（存在其他线程修改的情况），单线程是可以的（不存在其他线程修改的情况）。

如果确实需要在 ConcurrentHashMap 中使用 null 的话，可以使用一个特殊的静态空对象来代替 null。

public static final Object NULL = new Object();

java

ConcurrentHashMap 能保证复合操作的原子性吗？#

复合操作是指由多个基本操作(如 put、get、remove、containsKey 等)组成的操作，例如先判断某个键是否存在 containsKey(key)，然后根据结果进行插入或更新 put(key, value)。

ConcurrentHashMap 是线程安全的，意味着它可以保证多个线程同时对它进行读写操作时，不会出现数据不一致的情况，也不会导致 JDK 1.7 及之前版本的 HashMap 多线程操作导致死循环问题。

但并不意味着它可以保证所有的复合操作都是原子性的

example

对于下面的代码：

// 线程 A
if (!map.containsKey(key)) {
map.put(key, value);
}
// 线程 B
if (!map.containsKey(key)) {
map.put(key, anotherValue);
}

java

如果线程 A 和 B 的执行顺序是这样：

线程 A 判断 map 中不存在 key
线程 B 判断 map 中不存在 key
线程 B 将 (key, anotherValue) 插入 map
线程 A 将 (key, value) 插入 map

那么最终的结果是 (key, value)，而不是预期的 (key, anotherValue)。这就是复合操作的非原子性导致的问题。

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

可以改写为：

// 线程 A
map.putIfAbsent(key, value);
// 线程 B
map.putIfAbsent(key, anotherValue);

//or

// 线程 A
map.computeIfAbsent(key, k -> value);
// 线程 B
map.computeIfAbsent(key, k -> anotherValue);

java

也可以加锁同步，但不建议使用加锁的同步机制，违背了使用 ConcurrentHashMap 的初衷。在使用 ConcurrentHashMap 的时候，尽量使用这些原子性的复合操作方法来保证原子性。

Collections 工具类#

排序
查找,替换操作
同步控制(不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

排序操作：

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个元素整体移到后面

java

查找,替换操作

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)//用新元素替换旧元素

java

同步控制：(别用) Collections 提供了多个 synchronizedXxx()方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。我们知道 HashSet，TreeSet，ArrayList, LinkedList, HashMap, TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。

效率非常低

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

java