Java集合框架常见面试题

剖析⾯试最常⻅问题之 Java 集合框架 集合概述 Java 集合概览 从下图可以看出，在 Java 中除了以 Map 结尾的类之外， 其他类都实现了 Collection 接⼝。 并且，以 Map 结尾的类都实现了 Map 接⼝。 说说 List,Set,Map 三者的区别？ List (对付顺序的好帮⼿)： 存储的元素是有序的、可重复的。 Set (注重独⼀⽆⼆的性质): 存储的元素是⽆序的、不可重复的。 Map (⽤ Key 来搜索的专家): 使⽤键值对（kye-value）存储，类似于数学上的函数 y=f(x)， “x”代表 key，"y"代表 value，Key 是⽆序的、不可重复的，value 是⽆序的、可重复的，每个 键最多映射到⼀个值。 集合框架底层数据结构总结 先来看⼀下 Collection 接⼝下⾯的集合。 List Arraylist ： Object[] 数组 Vector ： Object[] 数组 LinkedList ： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)Set HashSet （⽆序，唯⼀）: 基于 HashMap 实现的，底层采⽤ HashMap 来保存元素 LinkedHashSet ： LinkedHashSet 是 HashSet 的⼦类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现⼀样，不过还是有⼀点点区别的 TreeSet （有序，唯⼀）： 红⿊树(⾃平衡的排序⼆叉树) 再来看看 Map 接⼝下⾯的集合。 Map HashMap ： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主 要为了解决哈希冲突⽽存在的（ “拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较⼤ 的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓ 度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以 减少搜索时间 LinkedHashMap ： LinkedHashMap 继承⾃ HashMap ，所以它的底层仍然是基于拉链式散 列结构即由数组和链表或红⿊树组成。另外， LinkedHashMap 在上⾯结构的基础上，增加了 ⼀条双向链表，使得上⾯的结构可以保持键值对的插⼊顺序。同时通过对链表进⾏相应的操作， 实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》 Hashtable ： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突 ⽽存在的 TreeMap ： 红⿊树（⾃平衡的排序⼆叉树） 如何选⽤集合? 主要根据集合的特点来选⽤，⽐如我们需要根据键值获取到元素值时就选⽤ Map 接⼝下的集合，需 要排序时选择 TreeMap ,不需要排序时就选择 HashMap ,需要保证线程安全就选⽤ ConcurrentHashMap 。 当我们只需要存放元素值时，就选择实现 Collection 接⼝的集合，需要保证元素唯⼀时选择实现 Set 接⼝的集合⽐如 TreeSet 或 HashSet ，不需要就选择实现 List 接⼝的⽐如 ArrayList 或 LinkedList ，然后再根据实现这些接⼝的集合的特点来选⽤。 为什么要使⽤集合？ 当我们需要保存⼀组类型相同的数据的时候，我们应该是⽤⼀个容器来保存，这个容器就是数组，但 是，使⽤数组存储对象具有⼀定的弊端， 因为我们在实际开发中，存储的数据的类型是多种多样的， 于是，就出现了“集合”，集合同样也是⽤来存储多个数据的。 数组的缺点是⼀旦声明之后，⻓度就不可变了；同时，声明数组时的数据类型也决定了该数组存储的数 据的类型；⽽且，数组存储的数据是有序的、可重复的，特点单⼀。 但是集合提⾼了数据存储的灵活 性，Java 集合不仅可以⽤来存储不同类型不同数量的对象，还可以保存具有映射关系的数据 Iterator 迭代器 迭代器 Iterator 是什么？Iterator 对象称为迭代器（设计模式的⼀种），迭代器可以对集合进⾏遍历，但每⼀个集合内部的 数据结构可能是不尽相同的，所以每⼀个集合存和取都很可能是不⼀样的，虽然我们可以⼈为地在每⼀ 个类中定义 hasNext() 和 next() ⽅法，但这样做会让整个集合体系过于臃肿。于是就有了迭代 器。 迭代器是将这样的⽅法抽取出接⼝，然后在每个类的内部，定义⾃⼰迭代⽅式，这样做就规定了整个集 合体系的遍历⽅式都是 hasNext() 和 next() ⽅法，使⽤者不⽤管怎么实现的，会⽤即可。迭代器的 定义为：提供⼀种⽅法访问⼀个容器对象中各个元素，⽽⼜不需要暴露该对象的内部细节。 迭代器 Iterator 有啥⽤？ Iterator 主要是⽤来遍历集合⽤的，它的特点是更加安全，因为它可以确保，在当前遍历的集合元 素被更改的时候，就会抛出 ConcurrentModificationException 异常。 如何使⽤？ 我们通过使⽤迭代器来遍历 HashMap ，演示⼀下 迭代器 Iterator 的使⽤。 有哪些集合是线程不安全的？怎么解决呢？ 我们常⽤的 Arraylist , LinkedList , Hashmap , HashSet , TreeSet , TreeMap ， PriorityQueue 都不是线程安全的。 解决办法很简单，可以使⽤线程安全的集合来代替。 如果你要使⽤线程安全的集合的话， java.util.concurrent 包中提供了很多并发容器供你使⽤： 1. ConcurrentHashMap : 可以看作是线程安全的 HashMap public interface Iterator<E> { //集合中是否还有元素 boolean hasNext(); //获得集合中的下⼀个元素 E next(); ...... } Map<Integer, String> map = new HashMap(); map.put(1, "Java"); map.put(2, "C++"); map.put(3, "PHP"); Iterator<Map.Entry<Integer, Stringef iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<Integer, String> entry = iterator.next(); System.out.println(entry.getKey() + entry.getValue()); }2. CopyOnWriteArrayList :可以看作是线程安全的 ArrayList ，在读多写少的场合性能⾮常 好，远远好于 Vector . 3. ConcurrentLinkedQueue :⾼效的并发队列，使⽤链表实现。可以看做⼀个线程安全的 LinkedList ，这是⼀个⾮阻塞队列。 4. BlockingQueue : 这是⼀个接⼝，JDK 内部通过链表、数组等⽅式实现了这个接⼝。表示阻塞 队列，⾮常适合⽤于作为数据共享的通道。 5. ConcurrentSkipListMap :跳表的实现。这是⼀个 Map ，使⽤跳表的数据结构进⾏快速查 找。 Collection ⼦接⼝之 List Arraylist 和 Vector 的区别? 1. ArrayList 是 List 的主要实现类，底层使⽤ Object[ ]存储，适⽤于频繁的查找⼯作，线程不 安全 ； 2. Vector 是 List 的古⽼实现类，底层使⽤ Object[ ]存储，线程安全的。 Arraylist 与 LinkedList 区别? 1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全； 2. 底层数据结构： Arraylist 底层使⽤的是 Object 数组； LinkedList 底层使⽤的是 双 向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链 表的区别，下⾯有介绍到！） 3. 插⼊和删除是否受元素位置的影响： ① ArrayList 采⽤数组存储，所以插⼊和删除元素的 时间复杂度受元素位置的影响。 ⽐如：执⾏ add(E e) ⽅法的时候， ArrayList 会默认在 将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插⼊和删除元素的话（ add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进 ⾏上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执⾏向后位/向前移⼀位的 操作。 ② LinkedList 采⽤链表存储，所以对于 add(E e) ⽅法的插⼊，删除元素时间复杂 度不受元素位置的影响，近似 O(1)，如果是要在指定位置 i 插⼊和删除元素的话（ (add(int index, E element) ） 时间复杂度近似为 o(n)) 因为需要先移动到指定位置再插⼊。 4. 是否⽀持快速随机访问： LinkedList 不⽀持⾼效的随机元素访问，⽽ ArrayList ⽀持。 快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) ⽅法)。 5. 内存空间占⽤： ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留⼀定的容量空 间，⽽ LinkedList 的空间花费则体现在它的每⼀个元素都需要消耗⽐ ArrayList 更多的空间 （因为要存放直接后继和直接前驱以及数据）。 补充内容:双向链表和双向循环链表 双向链表： 包含两个指针，⼀个 prev 指向前⼀个节点，⼀个 next 指向后⼀个节点。 另外推荐⼀篇把双向链表讲清楚的⽂章：https://juejin.im/post/5b5d1a9af265da0f47352f14双向循环链表： 最后⼀个节点的 next 指向 head，⽽ head 的 prev 指向最后⼀个节点，构成⼀个 环。 补充内容:RandomAccess 接⼝ 查看源码我们发现实际上 RandomAccess 接⼝中什么都没有定义。所以，在我看来 RandomAccess 接⼝不过是⼀个标识罢了。标识什么？ 标识实现这个接⼝的类具有随机访问功能。 在 binarySearch（ ) ⽅法中，它要判断传⼊的 list 是否 RamdomAccess 的实例，如果是，调 ⽤ indexedBinarySearch() ⽅法，如果不是，那么调⽤ iteratorBinarySearch() ⽅法 public interface RandomAccess { }ArrayList 实现了 RandomAccess 接⼝， ⽽ LinkedList 没有实现。为什么呢？我觉得还是 和底层数据结构有关！ ArrayList 底层是数组，⽽ LinkedList 底层是链表。数组天然⽀持随机 访问，时间复杂度为 O(1)，所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元 素，时间复杂度为 O(n)，所以不⽀持快速随机访问。， ArrayList 实现了 RandomAccess 接⼝， 就表明了他具有快速随机访问功能。 RandomAccess 接⼝只是标识，并不是说 ArrayList 实现 RandomAccess 接⼝才具有快速随机访问功能的！ 说⼀说 ArrayList 的扩容机制吧 详⻅笔主的这篇⽂章:通过源码⼀步⼀步分析 ArrayList 扩容机制 Collection ⼦接⼝之 Set comparable 和 Comparator 的区别 comparable 接⼝实际上是出⾃ java.lang 包 它有⼀个 compareTo(Object obj) ⽅法⽤ 来排序 comparator 接⼝实际上是出⾃ java.util 包它有⼀个 compare(Object obj1, Object obj2) ⽅法⽤来排序 ⼀般我们需要对⼀个集合使⽤⾃定义排序时，我们就要重写 compareTo() ⽅法或 compare() ⽅法， 当我们需要对某⼀个集合实现两种排序⽅式，⽐如⼀个 song 对象中的歌名和歌⼿名分别采⽤⼀种排序 ⽅法的话，我们可以重写 compareTo() ⽅法和使⽤⾃制的 Comparator ⽅法或者以两个 Comparator 来实现歌名排序和歌星名排序，第⼆种代表我们只能使⽤两个参数版的 Collections.sort() . Comparator 定制排序 public static <T> int binarySearch(List<? extends Comparable<? super Tef list, T key) { if (list instanceof RandomAccess || list.size() <BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); } ArrayList<Integer> arrayList = new ArrayList<Integer>(); arrayList.add(-1); arrayList.add(3); arrayList.add(3); arrayList.add(-5); arrayList.add(7); arrayList.add(4); arrayList.add(-9); arrayList.add(-7);Output: 重写 compareTo ⽅法实现按年龄来排序 System.out.println("原始数组:"); System.out.println(arrayList); // void reverse(List list)：反转 Collections.reverse(arrayList); System.out.println("Collections.reverse(arrayList):"); System.out.println(arrayList); // void sort(List list),按⾃然排序的升序排序 Collections.sort(arrayList); System.out.println("Collections.sort(arrayList):"); System.out.println(arrayList); // 定制排序的⽤法 Collections.sort(arrayList, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }); System.out.println("定制排序后："); System.out.println(arrayList); 原始数组: [-1, 3, 3, -5, 7, 4, -9, -7] Collections.reverse(arrayList): [-7, -9, 4, 7, -5, 3, 3, -1] Collections.sort(arrayList): [-9, -7, -5, -1, 3, 3, 4, 7] 定制排序后： [7, 4, 3, 3, -1, -5, -7, -9] // person对象没有实现Comparable接⼝，所以必须实现，这样才不会出错，才可 以使treemap中的数据按顺序排列 // 前⾯⼀个例⼦的String类已经默认实现了Comparable接⼝，详细可以查看 String类的API⽂档，另外其他 // 像Integer类等都已经实现了Comparable接⼝，所以不需要另外实现了 public class Person implements Comparable<Person> { private String name; private int age; public Person(String name, int age) { super(); this.name = name; this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } /** * T重写compareTo⽅法实现按年龄来排序 */ @Override public int compareTo(Person o) { if (this.age > o.getAge()) { return 1; } if (this.age < o.getAge()) { return -1; } return 0; } }Output： ⽆序性和不可重复性的含义是什么 1、什么是⽆序性？⽆序性不等于随机性 ，⽆序性是指存储的数据在底层数组中并⾮按照数组索引的顺 序添加 ，⽽是根据数据的哈希值决定的。 2、什么是不可重复性？不可重复性是指添加的元素按照 equals()判断时 ，返回 false，需要同时重 写 equals()⽅法和 HashCode()⽅法。 ⽐较 HashSet、LinkedHashSet 和 TreeSet 三者的异同 HashSet 是 Set 接⼝的主要实现类 ，HashSet 的底层是 HashMap，线程不安全的，可以存储 null 值； LinkedHashSet 是 HashSet 的⼦类，能够按照添加的顺序遍历； TreeSet 底层使⽤红⿊树，能够按照添加元素的顺序进⾏遍历，排序的⽅式有⾃然排序和定制排序。 Map 接⼝ HashMap 和 Hashtable 的区别 1. 线程是否安全： HashMap 是⾮线程安全的，HashTable 是线程安全的,因为 HashTable 内部的 ⽅法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使⽤ ConcurrentHashMap 吧！）； 2. 效率： 因为线程安全的问题，HashMap 要⽐ HashTable 效率⾼⼀点。另外，HashTable 基本被 淘汰，不要在代码中使⽤它； 3. 对 Null key 和 Null value 的⽀持： HashMap 可以存储 null 的 key 和 value，但 null 作 public static void main(String[] args) { TreeMap<Person, String> pdata = new TreeMap<Person, String>(); pdata.put(new Person("张三", 30), "zhangsan"); pdata.put(new Person("李四", 20), "lisi"); pdata.put(new Person("王五", 10), "wangwu"); pdata.put(new Person("⼩红", 5), "xiaohong"); // 得到key的值的同时得到key所对应的值 Set<Person> keys = pdata.keySet(); for (Person key : keys) { System.out.println(key.getAge() + "-" + key.getName()); } } 5-⼩红 10-王五 20-李四 30-张三为键只能有⼀个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会 抛出 NullPointerException。 4. 初始容量⼤⼩和每次扩充容量⼤⼩的不同 ： ① 创建时如果不指定容量初始值，Hashtable 默 认的初始⼤⼩为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化⼤⼩为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使⽤你给定的⼤⼩，⽽ HashMap 会将其扩充为 2 的幂次⽅⼤⼩（HashMap 中的 tableSizeFor() ⽅法保证，下⾯给出了源代码）。也就是说 HashMap 总是使⽤ 2 的幂作为 哈希表的⼤⼩,后⾯会介绍到为什么是 2 的幂次⽅。 5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于 阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择 先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以减少搜索时间。 Hashtable 没有这样的机制。 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 z{ 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); } 下⾯这个⽅法保证了 HashMap 总是使⽤ 2 的幂作为哈希表的⼤⼩。HashMap HashSet 实现了 Map 接⼝ 实现 Set 接⼝ 存储键值对 仅存储对象 调⽤ put() 向 map 中添加元素 调⽤ add() ⽅法向 Set 中添加元素 HashMap 使⽤键 （Key）计算 Hashcode HashSet 使⽤成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以 equals()⽅法⽤来判断对象的相等性， HashMap 和 HashSet 区别 如果你看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的 源码⾮常⾮常少，因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet ⾃⼰不得不 实现之外，其他⽅法都是直接调⽤ HashMap 中的⽅法。 HashMap 和 TreeMap 区别 TreeMap 和 HashMap 都继承⾃ AbstractMap ，但是需要注意的是 TreeMap 它还实现了 NavigableMap 接⼝和 SortedMap 接⼝。 /** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n e>f 1; n |= n e>f 2; n |= n e>f 4; n |= n e>f 8; n |= n e>f 16; return (n < 0) ? 1 : (n |{ MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }实现 NavigableMap 接⼝让 TreeMap 有了对集合内元素的搜索的能⼒。 实现 SortMap 接⼝让 TreeMap 有了对集合中的元素根据键排序的能⼒。默认是按 key 的升序排 序，不过我们也可以指定排序的⽐较器。示例代码如下： /** * @author shuang.kou * @createTime 2020年06⽉15⽇ 17:02:00 */ public class Person { private Integer age; public Person(Integer age) { this.age = age; } public Integer getAge() { return 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); } }); treeMap.put(new Person(3), "person1"); treeMap.put(new Person(18), "person2"); treeMap.put(new Person(35), "person3");输出: 可以看出， TreeMap 中的元素已经是按照 Person 的 age 字段的升序来排列了。 上⾯，我们是通过传⼊匿名内部类的⽅式实现的，你可以将代码替换成 Lambda 表达式实现的⽅式： 综上，相⽐于 HashMap 来说 TreeMap 主要多了对集合中的元素根据键排序的能⼒以及对集合内元素 的搜索的能⼒。 HashSet 如何检查重复 当你把对象加⼊ HashSet 时，HashSet 会先计算对象的 hashcode 值来判断对象加⼊的位置，同时也 会与其他加⼊的对象的 hashcode 值作⽐较，如果没有相符的 hashcode，HashSet 会假设对象没有重 复出现。但是如果发现有相同 hashcode 值的对象，这时会调⽤ equals() ⽅法来检查 hashcode 相等 的对象是否真的相同。如果两者相同，HashSet 就不会让加⼊操作成功。（摘⾃我的 Java 启蒙书 《Head fist java》第⼆版） hashCode()与 equals()的相关规定： 1. 如果两个对象相等，则 hashcode ⼀定也是相同的 2. 两个对象相等,对两个 equals ⽅法返回 true 3. 两个对象有相同的 hashcode 值，它们也不⼀定是相等的 4. 综上，equals ⽅法被覆盖过，则 hashCode ⽅法也必须被覆盖 5. hashCode()的默认⾏为是对堆上的对象产⽣独特值。如果没有重写 hashCode()，则该 class 的 两个对象⽆论如何都不会相等（即使这两个对象指向相同的数据）。 FG与 equals 的区别 对于基本类型来说，}~ ⽐较的是值是否相等； 对于引⽤类型来说，}~ ⽐较的是两个引⽤是否指向同⼀个对象地址（两者在内存中存放的地址（堆内 存地址）是否指向同⼀个地⽅）； treeMap.put(new Person(16), "person4"); treeMap.entrySet().stream().forEach(personStringEntry > { System.out.println(personStringEntry.getValue()); }); } } person1 person4 person2 person3 TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) > { int num = person1.getAge() - person2.getAge(); return Integer.compare(num, 0); });对于引⽤类型（包括包装类型）来说，equals 如果没有被重写，对⽐它们的地址是否相等；如果 equals()⽅法被重写（例如 String），则⽐较的是地址⾥的内容。 HashMap 的底层实现 JDK1.8 之前 JDK1.8 之前 HashMap 底层是 数组和链表 结合在⼀起使⽤也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置 （这⾥的 n 指的是数组的⻓度），如果当前位置存在元素的话，就判断该元素与要存⼊的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。 所谓扰动函数指的就是 HashMap 的 hash ⽅法。使⽤ hash ⽅法也就是扰动函数是为了防⽌⼀些实现 ⽐较差的 hashCode() ⽅法 换句话说使⽤扰动函数之后可以减少碰撞。 JDK 1.8 HashMap 的 hash ⽅法源码: JDK 1.8 的 hash ⽅法 相⽐于 JDK 1.7 hash ⽅法更加简化，但是原理不变。 对⽐⼀下 JDK1.7 的 HashMap 的 hash ⽅法源码. 相⽐于 JDK1.8 的 hash ⽅法 ，JDK 1.7 的 hash ⽅法的性能会稍差⼀点点，因为毕竟扰动了 4 次。 所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建⼀个链表数组，数组中每⼀格就是⼀个链 表。若遇到哈希冲突，则将冲突的值加到链表中即可。 static final int hash(Object key) { int h; // key.hashCode()：返回散列值也就是hashcode // ^ ：按位异或 // e>fÅ⽆符号右移，忽略符号位，空位都以0补⻬ return (key }~ null) ? 0 : (h = key.hashCode()) ^ (h e>f 16); } 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 e>f 20) ^ (h e>f 12); return h ^ (h e>f 7) ^ (h e>f 4); }JDK1.8 之后 相⽐于之前的版本， JDK1.8 之后在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不 是转换为红⿊树）时，将链表转化为红⿊树，以减少搜索时间。TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都⽤到了红⿊树。红⿊树就是为了解决⼆叉 查找树的缺陷，因为⼆叉查找树在某些情况下会退化成⼀个线性结构。 HashMap 的⻓度为什么是 2 的幂次⽅ 为了能让 HashMap 存取⾼效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上⾯也讲到了过 了，Hash 值的范围值-2147483648 到 2147483647，前后加起来⼤概 40 亿的映射空间，只要哈希函数 映射得⽐较均匀松散，⼀般应⽤是很难出现碰撞的。但问题是⼀个 40 亿⻓度的数组，内存是放不下 的。所以这个散列值是不能直接拿来⽤的。⽤之前还要先做对数组的⻓度取模运算，得到的余数才能⽤ 来要存放的位置也就是对应的数组下标。这个数组下标的计算⽅法是“ (n - 1) & hash ”。（n 代表 数组⻓度）。这也就解释了 HashMap 的⻓度为什么是 2 的幂次⽅。 这个算法应该如何设计呢？ 我们⾸先可能会想到采⽤%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是 2 的幂次 则等价于与其除数减⼀的与(&)操作（也就是说 hash%lengthFGhash&(length-1)的前提是 length 是 2 的 n 次⽅；）。” 并且 采⽤⼆进制位操作 &，相对于%能够提⾼运算效率，这就解释了 HashMap 的⻓ 度为什么是 2 的幂次⽅。 HashMap 多线程操作导致死循环问题 主要原因在于并发下的 Rehash 会造成元素之间会形成⼀个循环链表。不过，jdk 1.8 后解决了这个问 题，但是还是不建议在多线程下使⽤ HashMap,因为多线程下使⽤ HashMap 还是会存在其他问题⽐如数 据丢失。并发环境下推荐使⽤ ConcurrentHashMap 。 详情请查看：https://coolshell.cn/articles/9606.html HashMap 有哪⼏种常⻅的遍历⽅式? HashMap 的 7 种遍历⽅式与性能分析！ConcurrentHashMap 和 Hashtable 的区别 ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的⽅式上不同。 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采⽤ 分段的数组+链表 实现，JDK1.8 采 ⽤的数据结构跟 HashMap1.8 的结构⼀样，数组+链表/红⿊⼆叉树。Hashtable 和 JDK1.8 之前 的 HashMap 的底层数据结构类似都是采⽤ 数组+链表 的形式，数组是 HashMap 的主体，链表 则是主要为了解决哈希冲突⽽存在的； 实现线程安全的⽅式（重要）： ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个 桶数组进⾏了分割分段(Segment)，每⼀把锁只锁容器其中⼀部分数据，多线程访问容器⾥不同 数据段的数据，就不会存在锁竞争，提⾼并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，⽽是直接⽤ Node 数组+链表+红⿊树的数据结构来实现，并发控制使⽤ synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起 来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但 是已经简化了属性，只是为了兼容旧版本；② Hashtable(同⼀把锁) :使⽤ synchronized 来保 证线程安全，效率⾮常低下。当⼀个线程访问同步⽅法时，其他线程也访问同步⽅法，可能会进 ⼊阻塞或轮询状态，如使⽤ put 添加元素，另⼀个线程不能使⽤ put 添加元素，也不能使⽤ get，竞争会越来越激烈效率越低。 两者的对⽐图： HashTable: http://www.cnblogs.com/chengxiao/p/6842045.html> JDK1.7 的 ConcurrentHashMap：http://www.cnblogs.com/chengxiao/p/6842045.html> JDK1.8 的 ConcurrentHashMap： JDK1.8 的 ConcurrentHashMap 不在是 Segment 数组 + HashEntry 数组 + 链表，⽽是 Node 数 组 + 链表 / 红⿊树。不过，Node 只能⽤于链表的情况，红⿊树的情况需要使⽤ TreeNode 。当冲突 链表达到⼀定⻓度时，链表会转换成红⿊树。 ConcurrentHashMap 线程安全的具体实现⽅式/底层具体实现 JDK1.7（上⾯有示意图） ⾸先将数据分为⼀段⼀段的存储，然后给每⼀段数据配⼀把锁，当⼀个线程占⽤锁访问其中⼀个段数据 时，其他段的数据也能被其他线程访问。 ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。 Segment 实现了 ReentrantLock,所以 Segment 是⼀种可重⼊锁，扮演锁的⻆⾊。HashEntry ⽤于存储 键值对数据。⼀个 ConcurrentHashMap ⾥包含⼀个 Segment 数组。Segment 的结构和 HashMap 类似，是⼀种数组 和链表结构，⼀个 Segment 包含⼀个 HashEntry 数组，每个 HashEntry 是⼀个链表结构的元素，每 个 Segment 守护着⼀个 HashEntry 数组⾥的元素，当对 HashEntry 数组的数据进⾏修改时，必须⾸ 先获得对应的 Segment 的锁。 JDK1.8 （上⾯有示意图） ConcurrentHashMap 取消了 Segment 分段锁，采⽤ CAS 和 synchronized 来保证并发安全。数据结构 跟 HashMap1.8 的结构类似，数组+链表/红⿊⼆叉树。Java 8 在链表⻓度超过⼀定阈值（ 8）时将链表 （寻址时间复杂度为 O(N)）转换为红⿊树（寻址时间复杂度为 O(log(N))） synchronized 只锁定当前链表或红⿊⼆叉树的⾸节点，这样只要 hash 不冲突，就不会产⽣并发，效 率⼜提升 N 倍。 Collections ⼯具类 Collections ⼯具类常⽤⽅法: 1. 排序 2. 查找,替换操作 3. 同步控制(不推荐，需要线程安全的集合类型时请考虑使⽤ JUC 包下的并发集合) 排序操作 查找,替换操作 static class Segment<K,V> extends ReentrantLock implements Serializable { } 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个元 素整体移到后⾯同步控制 Collections 提供了多个 synchronizedXxx() ⽅法·，该⽅法可以将指定集合包装成线程同步的集 合，从⽽解决多线程并发访问集合时的线程安全问题。 我们知道 HashSet ， TreeSet ， ArrayList , LinkedList , HashMap , TreeMap 都是线程不安全 的。 Collections 提供了多个静态⽅法可以把他们包装成线程同步的集合。 最好不要⽤下⾯这些⽅法，效率⾮常低，需要线程安全的集合类型时请考虑使⽤ JUC 包下的并发集 合。 ⽅法如下： 其他重要问题 什么是快速失败(fail-fast)？ 快速失败(fail-fast) 是 Java 集合的⼀种错误检测机制。在使⽤迭代器对集合进⾏遍历的时候，我们 在多线程下操作⾮安全失败(fail-safe)的集合类可能就会触发 fail-fast 机制，导致抛出 ConcurrentModificationException 异常。 另外，在单线程下，如果在遍历过程中对集合对象 的内容进⾏了修改的话也会触发 fail-fast 机制。 注：增强 for 循环也是借助迭代器进⾏遍历。 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), ⽤新元素替 换旧元素 synchronizedCollection(Collection<T> c) //返回指定 collection ⽀持的同 步（线程安全的）collection。 synchronizedList(List<T> list)//返回指定列表⽀持的同步（线程安全的） List。 synchronizedMap(Map<K,V> m) //返回由指定映射⽀持的同步（线程安全的） Map。 synchronizedSet(Set<T> s) //返回指定 set ⽀持的同步（线程安全的）set。举个例⼦：多线程下，如果线程 1 正在对集合进⾏遍历，此时线程 2 对集合进⾏修改（增加、删除、 修改），或者线程 1 在遍历过程中对集合进⾏修改，都会导致线程 1 抛出 ConcurrentModificationException 异常。 为什么呢？ 每当迭代器使⽤ hashNext() / next() 遍历下⼀个元素之前，都会检测 modCount 变量是否为 expectedModCount 值，是的话就返回遍历；否则抛出异常，终⽌遍历。 如果我们在集合被遍历期间对其进⾏修改的话，就会改变 modCount 的值，进⽽导致 modCount Ö~ expectedModCount ，进⽽抛出 ConcurrentModificationException 异常。 注：通过 Iterator 的⽅法修改集合的话会修改到 expectedModCount 的值，所以不会抛出异 常。 final void checkForComodification() { if (modCount Ö~ expectedModCount) throw new ConcurrentModificationException(); } 好吧！相信⼤家已经搞懂了快速失败(fail-fast)机制以及它的原理。 我们再来趁热打铁，看⼀个阿⾥巴巴⼿册相关的规定： 有了前⾯讲的基础，我们应该知道：使⽤ Iterator 提供的 remove ⽅法，可以修改到 expectedModCount 的值。所以，才不会再抛出 ConcurrentModificationException 异常。什么是安全失败(fail-safe)呢？ 明⽩了快速失败(fail-fast)之后，安全失败(fail-safe)我们就很好理解了。 采⽤安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，⽽是先复制原有集合内容，在 拷⻉的集合上进⾏遍历。所以，在遍历过程中对原集合所作的修改并不能被迭代器检测到，故不会抛 ConcurrentModificationException 异常。 Arrays.asList()避坑指南 最近使⽤ Arrays.asList() 遇到了⼀些坑，然后在⽹上看到这篇⽂章：Java Array to List Examples 感觉挺不错的，但是还不是特别全⾯。所以，⾃⼰对于这块⼩知识点进⾏了简单的总结。 简介 Arrays.asList() 在平时开发中还是⽐较常⻅的，我们可以使⽤它将⼀个数组转换为⼀个 List 集 合。 JDK 源码对于这个⽅法的说明： 《阿⾥巴巴 Java 开发⼿册》对其的描述 Arrays.asList() 将数组转换为集合后,底层其实还是数组，《阿⾥巴巴 Java 开发⼿册》对于这个 ⽅法有如下描述： String[] myArray = { "Apple", "Banana", "Orange" }； List<String> myList = Arrays.asList(myArray); //上⾯两个语句等价于下⾯⼀条语句 List<String> myList = Arrays.asList("Apple","Banana", "Orange"); /** *返回由指定数组⽀持的固定⼤⼩的列表。此⽅法作为基于数组和基于集合的API 之间的桥梁，与 Collection.toArray()结合使⽤。返回的List是可序 列化并实现RandomAccess接⼝。 */ public static <T> List<T> asList(T... a) { return new ArrayList<>(a); }使⽤时的注意事项总结 传递的数组必须是对象数组，⽽不是基本类型。 Arrays.asList() 是泛型⽅法，传⼊的对象必须是对象数组。 当传⼊⼀个原⽣数据类型数组时， Arrays.asList() 的真正得到的参数就不是数组中的元素，⽽是 数组对象本身！此时 List 的唯⼀元素就是这个数组，这也就解释了上⾯的代码。 我们使⽤包装类型数组就可以解决这个问题。 使⽤集合的修改⽅法: add() 、 remove() 、 clear() 会抛出异常。 Arrays.asList() ⽅法返回的并不是 java.util.ArrayList ，⽽是 java.util.Arrays 的 ⼀个内部类,这个内部类并没有实现集合的修改⽅法或者说并没有重写这些⽅法。 下图是 java.util.Arrays$ArrayList 的简易源码，我们可以看到这个类重写的⽅法有哪些。 int[] myArray = { 1, 2, 3 }; List myList = Arrays.asList(myArray); System.out.println(myList.size());//1 System.out.println(myList.get(0));//数组地址值 System.out.println(myList.get(1));//报错：ArrayIndexOutOfBoundsException int [] array=(int[]) myList.get(0); System.out.println(array[0]);//1 Integer[] myArray = { 1, 2, 3 }; List myList = Arrays.asList(1, 2, 3); myList.add(4);//运⾏时报错：UnsupportedOperationException myList.remove(1);//运⾏时报错：UnsupportedOperationException myList.clear();//运⾏时报错：UnsupportedOperationException List myList = Arrays.asList(1, 2, 3); System.out.println(myList.getClass());//class java.util.Arrays$ArrayList private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable { ... @Override public E get(int index) { ... } @Override public E set(int index, E element) { ... } @Override public int indexOf(Object o) { ... } @Override public boolean contains(Object o) { ... } @Override public void forEach(Consumer<? super E> action) { ... } @Override public void replaceAll(UnaryOperator<E> operator) { ... } @Override public void sort(Comparator<? super E> c) { ... } } 我们再看⼀下 java.util.AbstractList 的 remove() ⽅法，这样我们就明⽩为啥会抛出 UnsupportedOperationException 。public E remove(int index) { throw new UnsupportedOperationException(); }