集合类

典型回答 我们知道，ConcurrentHashMap在使用时，和HashMap有一个比较大的区别，那就是HashMap中，null可以作为键或者值都可以。而在ConcurrentHashMap中，key和value都不允许为null。 那么，为什么呢？为啥ConcurrentHashMap要设计成这样的呢？ 关于这个问题，其实最有发言权的就是ConcurrentHashMap的作者——Doug Lea� 他自己曾经出面解释过这个问题，内容如下（http://cs.oswego.edu/pipermail/concurrency-interest/2006-May/002485.html ，原文地址已经打不开了，大家将就着看一下截图吧） ： 主要意思就是说： ConcurrentMap（如ConcurrentHashMap、ConcurrentSkipListMap）不允许使用null值的主要原因是，在非并发的Map中（如HashMap)，是可以容忍模糊性（二义性）的，而在并发Map中是无法容忍的。 假如说，所有的Map都支持null的话，那么map.get(key)就可以返回null，但是，这时候就会存在一个不确定性，当你拿到null的时候，你是不知道他是因为本来就存了一个null进去还是说就是因为没找到而返回了null。 在HashMap中，因为它的设计就是给单线程用的，所以当我们map.get(key)返回null的时候，我们是可以通过map.contains(key)检查来进行检测的，如果它返回true，则认为是存了一个null，否则就是因为没找到而返回了null。 但是，像ConcurrentHashMap，它是为并发而生的，它是要用在并发场景中的，当我们map.get(key)返回null的时候，是没办法通过map.contains(key)检查来准确的检测，因为在检测过程中可能会被其他线程所修改，而导致检测结果并不可靠。 所以，为了让ConcurrentHashMap的语义更加准确，不存在二义性的问题，他就不支持null。

典型回答 本文的源码是基于Java 7的，主要是1.7中有个单独的IndexFor方法，讲起来更方便大家理解，而Java8中虽然没有这样一个单独的方法，但是查询下标的算法也是和Java 7一样的。 JDK1.7的HashMap的hash方法的实现中，是通过两个方法int hash(Object k)和int indexFor(int h, int length)来实现。 ✅HashMap的hash方法是如何实现的？ 我们重点来看一下indexFor方法。为了方便大家理解，我们看Java 7的中该实现的细节： 1 2 3 static int indexFor(int h, int length) { return h & (length-1); } indexFor方法其实主要是将hashcode换成链表数组中的下标。其中的两个参数h表示元素的hashcode值，length表示HashMap的容量。那么return h & (length-1) 是什么意思呢？ 其实，他就是取模。Java之所以使用位运算(&)来代替取模运算(%)，最主要的考虑就是效率。 为什么是用&而不是用%呢？因为&是基于内存的二进制直接运算，比转成十进制的取模快的多。又因为X % 2^n = X & (2^n – 1)，可以把%运算转换为&运算。所以，hashMap的capacity一定要是2^n。这样，HashMap计算hash的速度才够快 为什么**X % 2^n = X & (2^n – 1)**？ 假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 -1 = 7 ，即0111。 此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。 从2进制角度来看，X / 8相当于 X » 3，即把X右移3位，此时得到了X / 8的商，而被移掉的部分(后三位)，则是X % 8，也就是余数。 ...

典型回答 为什么不继续使用链表 我们知道，HashMap解决hash冲突是通过拉链法完成的，在JDK8之前，如果产生冲突，就会把新增的元素增加到当前桶所在的链表中。 这样就会产生一个问题，当某个bucket冲突过多的时候，其指向的链表就会变得很长，这样如果put或者get该bucket上的元素时，复杂度就无限接近于O(N)，这样显然是不可以接受的。 所以在JDK1.7的时候，在元素put之前做hash的时候，就会充分利用扰动函数，将不同KEY的hash尽可能的分散开。不过这样做起来效果还不是太好，所以当链表过长的时候，我们就要对其数据结构进行修改 为什么是红黑树 当元素过多的时候，用什么来代替链表呢？我们很自然的就能想到可以用二叉树查找树代替，所谓的二叉查找树，一定是left < root < right，这样我们遍历的时间复杂度就会由链表的O(N)变为二叉查找树的O(logN)，二叉查找树如下所示： 但是，对于极端情况，当子节点都比父节点大或者小的时候，二叉查找树又会退化成链表，查询复杂度会重新变为O(N)，如下所示： 所以，我们就需要二叉平衡树（AVL树）出场，他会在每次插入操作时来检查每个节点的左子树和右子树的高度差至多等于1，如果>1，就需要进行左旋或者右旋操作，使其查询复杂度一直维持在O(logN)。 但是这样就万无一失了吗？其实并不然，我们不仅要保证查询的时间复杂度，还需要保证插入的时间复杂度足够低，因为平衡二叉树要求高度差最多为1，非常严格，导致每次插入都需要左旋或者右旋，极大的消耗了插入的时间。 对于那些插入和删除比较频繁的场景，AVL树显然是不合适的。为了保证查询和插入的时间复杂度维持在一个均衡的水平上，所以就引入了红黑树。 在红黑树中，所有的叶子节点都是黑色的空节点，也就是叶子节点不存数据；任何相邻的节点都不能同时为红色，红色节点是被黑色节点隔开的，每个节点，从该节点到达其可达的叶子节点的所有路径，都包含相同数目的黑色节点。 我们可以得到如下结论：红黑树不会像AVL树一样追求绝对的平衡，它的插入最多两次旋转，删除最多三次旋转，在频繁的插入和删除场景中，红黑树的时间复杂度，是优于AVL树的。 综上所述，这就是HashMap选择红黑树的原因。 知识扩展 为什么是链表长度达到8的时候转 这个问题有两层含义，第一个是为什么不在冲突的时候立刻转为红黑树，第二个是为什么是达到8的时候转 为什么不在冲突的时候立刻转 原因有2，从空间维度来讲，因为红黑树的空间是普通链表节点空间的2倍，立刻转为红黑树后，太浪费空间；从时间维度上讲，红黑树虽然查询比链表快，但是插入比链表慢多了，每次插入都要旋转和变色，如果小于8就转为红黑树，时间和空间的综合平衡上就没有链表好 为什么长度为8的时候转 先来看源码的一段注释： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 /* Because TreeNodes are about twice the size of regular nodes, we * use them only when bins contain enough nodes to warrant use * (see TREEIFY_THRESHOLD). And when they become too small (due to * removal or resizing) they are converted back to plain bins. In * usages with well-distributed user hashCodes, tree bins are * rarely used. Ideally, under random hashCodes, the frequency of * nodes in bins follows a Poisson distribution * (http://en.wikipedia.org/wiki/Poisson_distribution) with a * parameter of about 0.5 on average for the default resizing * threshold of 0.75, although with a large variance because of * resizing granularity. Ignoring variance, the expected * occurrences of list size k are (exp(-0.5) * pow(0.5, k) / * factorial(k)). The first values are: * * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * more: less than 1 in ten million */ 大概的翻译就是TreeNode占用的内存是Node的两倍，只有在node数量达到8时才会使用它，而当 node 数量变小时（删除或者扩容），又会变回普通的 Node 。当 hashCode遵循泊松分布时，因为哈希冲突造成桶的链表长度等于8的概率只有0.00000006 。官方认为这个概率足够的低，所以指定链表长度为 8 时转化为红黑树。所以 8 这个数是经过数学推理的，不是瞎写的。 ...

典型回答 在系统设计中，快速失效(fail-fast)系统是一种可以立即报告任何可能表明故障的情况的系统。快速失效系统通常设计用于停止正常操作，而不是试图继续可能存在缺陷的过程。 其实，这是一种理念，说白了就是在做系统设计的时候先考虑异常情况，一旦发生异常，直接停止并上报。 举一个最简单的fail-fast的例子： 1 2 3 4 5 6 public int divide(int dividend,int divisor){ if(divisor == 0){ throw new RuntimeException("divisor can't be zero"); } return dividend/divisor; } 上面的代码是一个对两个整数做除法的方法，在divide方法中，我们对除数做了个简单的检查，如果其值为0，那么就直接抛出一个异常，并明确提示异常原因。这其实就是fail-fast理念的实际应用。 这样做的好处就是可以预先识别出一些错误情况，一方面可以避免执行复杂的其他代码，另外一方面，这种异常情况被识别之后也可以针对性的做一些单独处理。 在Java中，集合类中有用到fail-fast机制进行设计，一旦使用不当，触发fail-fast机制设计的代码，就会发生非预期情况。 在集合类中，为了避免并发修改，会维护一个expectedModCount属性，他表示这个迭代器预期该集合被修改的次数。还有一个modCount属性，他表示该集合实际被修改的次数。在集合被修改时，会去比较modCount和expectedModCount的值，如果不一致，则会触发fail-fast机制，抛出ConcurrentModificationException。 fail-safe 机制是为线程安全的集合准备的，可以避免像 fail-fast 一样在并发使用集合的时候，不断地抛出异常。 扩展知识 集合类中的fail-fast 我们通常说的Java中的fail-fast机制，默认指的是Java集合的一种错误检测机制。当多个线程对部分集合进行结构上的改变的操作时，有可能会产生fail-fast机制，这个时候就会抛出ConcurrentModificationException ConcurrentModificationException，当方法检测到对象的并发修改，但不允许这种修改时就抛出该异常。 在Java中， 如果在foreach 循环里对某些集合元素进行元素的 remove/add 操作的时候，就会触发fail-fast机制，进而抛出ConcurrentModificationException。 如以下代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 List<String> userNames = new ArrayList<String>() {{ add("Hollis"); add("hollis"); add("HollisChuang"); add("H"); }}; for (String userName : userNames) { if (userName.equals("Hollis")) { userNames.remove(userName); } } System.out.println(userNames); 以上代码，使用增强for循环遍历元素，并尝试删除其中的Hollis字符串元素。运行以上代码，会抛出以下异常： ...

典型回答 同步容器是通过加锁实现线程安全的，并且只能保证单独的操作是线程安全的，无法保证复合操作的线程安全性。并且同步容器的读和写操作之间会互相阻塞。 在多线程场景中，如果使用同步容器，一定要注意复合操作的线程安全问题。必要时候要主动加锁。在并发场景中，建议直接使用java.util.concurent包中提供的容器类，如果需要复合操作时，建议使用有些容器自身提供的复合方法。 什么是同步容器？最常见的同步容器就是Vector和Hashtable了，在Java中，同步容器主要包括2类： 1、Vector、Stack、HashTable 2、Collections类中提供的静态工厂方法创建的类 本文拿相对简单的Vecotr来举例，我们先来看下Vector中几个重要方法的源码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; } public synchronized E remove(int index) { modCount++; if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); E oldValue = elementData(index); int numMoved = elementCount - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--elementCount] = null; // Let gc do its work return oldValue; } public synchronized E get(int index) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); return elementData(index); } 可以看到，Vector这样的同步容器的所有公有方法全都是synchronized的，也就是说，我们可以在多线程场景中放心的使用单独这些方法，因为这些方法本身的确是线程安全的。 ...

典型回答 Java.util包中的List接口继承了Collection接口，用来存放对象集合，所以对这些对象进行排序的时候，要么让对象类自己实现同类对象的比较，要么借助比较器进行比较排序。 举例：学生实体类，包含姓名和年龄属性，比较时先按姓名升序排序，如果姓名相同则按年龄升序排序。 实现Comparable 第一种：实体类自己实现Comparable接口比较 1 2 3 4 5 6 7 8 9 10 11 12 13 public class Student implements Comparable<Student>{ private String name; private int age; @Override public int compareTo(Student o) { int flag = this.name.compareTo(o.name); if(flag == 0) { flag = this.age - o.age; } return flag; } } Collections.sort(students); 借助Comparator 第二种：借助比较器进行排序。 ...

典型回答 我们知道，在foreach的同时修改集合，会触发fail-fast机制，要避免fail-fast机制，有如下处理方案： 通过普通的for循环（不建议，可能会漏删） 1 2 3 4 5 6 7 8 9 10 11 public void listRemove() { List<Student> students = this.getStudents(); for (int i=0; i<students.size(); i++) { if (students.get(i).getId()%3 == 0) { Student student = students.get(i); students.remove(student); //做一次i--，避免漏删 i--; } } } 通过普通的for循环进行倒叙遍历（也能用） 上面的方式需要做i–避免漏删，还有个办法，那就是倒叙遍历也能避免这个问题： 1 2 3 4 5 6 7 8 9 public void listRemove() { List<Student> students = this.getStudents(); for (int i = students.size() - 1; i >= 0; i--) { if (students.get(i).getId()%3 == 0) { Student student = students.get(i); students.remove(student); } } } 使用迭代器循环（可以用） 1 2 3 4 5 6 7 8 9 10 11 public void iteratorRemove() { List<Student> students = this.getStudents(); Iterator<Student> stuIter = students.iterator(); while (stuIter.hasNext()) { Student student = stuIter.next(); if (student.getId() % 2 == 0) { //这里要使用Iterator的remove方法移除当前对象，如果使用List的remove方法，则同样会出现ConcurrentModificationException stuIter.remove(); } } } 将原来的copy一份副本，遍历原来的list，然后删除副本（可以用，fail-safe的，但是比较复杂） 1 2 3 4 5 6 7 8 9 10 public void copyRemove() { // 注意，这种方法的equals需要重写 List<Student> students = this.getStudents(); List<Student> studentsCopy = deepclone(students); for(Student stu : students) { if(needDel(stu)) { studentsCopy.remove(stu); } } } 使用并发安全的集合类（可以用，但是需要转成线程安全的集合） 1 2 3 4 5 6 7 8 public void cowRemove() { List<String> students = new CopyOnWriteArrayList<>(this.getStudents()); for(Student stu : students) { if(needDel(stu)) { students.remove(stu); } } } 通过Stream的过滤方法，因为Stream每次处理后都会生成一个新的Stream，不存在并发问题，所以Stream的filter也可以修改list集合。（建议，简单高效） 1 2 3 4 5 6 public List<String> streamRemove() { List<String> students = this.getStudents(); return students.stream() .filter(this::notNeedDel) .collect(Collectors.toList()); } 通过removeIf方法，实现元素的过滤删除。从Java 8开始，List接口提供了removeIf方法用于删除所有满足特定条件的数组元素（推荐） 1 arraylist.removeIf(this::needDel);

典型回答 特性 ArrayList LinkedList Vector 实现接口 List Queue、Deque、List List 底层数据结构 数组 双向链表 数组 线程安全 非线程安全 非线程安全 线程安全 扩容机制 增长 50% 无需扩容 增长 100% 随机访问复杂度 O(1)（数组下标） O(n)（需遍历链表） O(1)（数组下标） 插入/删除复杂度 平均 O(n)（需移动元素） 头尾 O(1)，中间 O(n) 平均 O(n)（需移动元素） 迭代器 <font style="color:rgb(64, 64, 64);background-color:rgb(236, 236, 236);">Iterator</font> + <font style="color:rgb(64, 64, 64);background-color:rgb(236, 236, 236);">ListIterator</font> <font style="color:rgb(64, 64, 64);background-color:rgb(236, 236, 236);">Iterator</font> + <font style="color:rgb(64, 64, 64);background-color:rgb(236, 236, 236);">DescendingIterator</font> <font style="color:rgb(64, 64, 64);background-color:rgb(236, 236, 236);">Iterator</font> + <font style="color:rgb(64, 64, 64);background-color:rgb(236, 236, 236);">ListIterator</font> 序列化 仅序列化有效元素 序列化节点结构 默认序列化 是否建议使用 建议 建议 不建议 List主要有ArrayList、LinkedList与Vector几种实现。这三者都实现了List 接口，使用方式也很相似,主要区别在于因为实现方式的不同,所以对不同的操作具有不同的效率。 ...

典型回答 在Java的Set体系中，根据实现方式不同主要分为两大类。HashSet和TreeSet。 TreeSet 是二叉树实现的，TreeSet中的数据是自动排好序的，不允许放入null值；底层基于TreeMap HashSet 是哈希表实现的，HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束；底层基于HashMap 在HashSet中，基本的操作都是有HashMap底层实现的，因为HashSet底层是用HashMap存储数据的。当向HashSet中添加元素的时候，首先计算元素的hashCode值，然后通过扰动计算和按位与的方式计算出这个元素的存储位置，如果这个位置为空，就将元素添加进去；如果不为空，则用equals方法比较元素是否相等，相等就不添加，否则找一个空位添加。 TreeSet的底层是TreeMap的keySet()，而TreeMap是基于红黑树实现的，红黑树是一种平衡二叉查找树，它能保证任何一个节点的左右子树的高度差不会超过较矮的那棵的一倍。 TreeMap是按key排序的，元素在插入TreeSet时compareTo()方法要被调用，所以TreeSet中的元素要实现Comparable接口。TreeSet作为一种Set，它不允许出现重复元素。TreeSet是用compareTo()来判断重复元素的。 知识扩展 HashSet，TreeSet，LinkedHashSet，BitSet有何区别 功能不同：HashSet是功能最简单的Set，只提供去重的能力；LinkedHashSet不仅提供去重功能，而且还能记录插入和查询顺序；TreeSet提供了去重和排序的能力；BitSet不仅能提供去重能力，同时也能减少存储空间的浪费，不过对于普通的对象不太友好，需要做额外处理 实现方式不同：HashSet基于HashMap，去重是根据HashCode和equals方法的；LinkedHashSet是基于LinkedHashMap，通过双向链表记录插入顺序；TreeSet是基于TreeMap的，去重是根据compareTo方法的；BitSet基于位数组，一般只用于数字的存储和去重 其实BitSet只是叫做Set而已，它既没有实现Collection接口，也和Iterable接口没有什么关系，但是是名字相似而已 什么是BitSet？有什么作用？ 顾名思义，BitSet是位集合，通常来说，位集合的底层的数据结构是一个bit数组，如果第n位为1，则表明数字n在该数组中。 举个例子，如果调用BitSet#set(10)，业务语意是把10放到BitSet中，内部的操作则是通过把二进制的第十位（低位）置为1。这样，就代表BitSet中包含了10这个数字。 不过，对于Java中的BitSet来讲，因为Java不知道bit类型，所以它的底层结构并不是一个bit类型数组，但是也不是一个byte类型数组，而是一个long类型的数组，这样设置的目的是因为long有64位，每次可以读取64位，在进行set或者or操作的时候，for循环的次数会更少，提高了性能。 它最大的好处就是对于多个数字来说，降低了存储空间，如正常情况下，将每一个int类型（32bit）的数字存储到内存中需要 4B * (2^32) = 16 GB，但是如果用BitSet的话，就会节省到原来的1/32。 一个整型占4个字节，一共有2^32个。 BitSet常见的使用例子往往和大数相关： 现在有1千万个随机数，随机数的范围在1到1亿之间。求出将1到1亿之间没有在随机数中的数 统计N亿个数据中没有出现的数据 将N亿个不同数据进行排序等 但是BitSet也有缺点，譬如集合中存储一些差值比较大的数，如1亿和1两个数，就会导致内存的严重浪费

典型回答 在ArrayList的内部实现中，用于存储元素的数组（**transient Object[] elementData;**）被声明为transient，这意味着默认的序列化机制不会序列化这个数组。 那么，ArrayList是如何实现序列化的呢？ **ArrayList自定义了序列化过程，通过重写writeObject和readObject方法。 ** 之所以这么做，ArrayList的数组通常会有一些空的位置（因为容量会预留一些空间），为了节省空间和提高效率，ArrayList没有使用默认的序列化机制，而是自定义了序列化，只序列化实际存储的元素，而不是整个数组。 ArrayList重写了writeObject和readObject方法，如下所示： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // Read in size, and any hidden stuff s.defaultReadObject(); // Read in capacity s.readInt(); // ignored if (size > 0) { // be like clone(), allocate array based upon size not capacity ensureCapacityInternal(size); Object[] a = elementData; // Read in all elements in the proper order. for (int i=0; i<size; i++) { a[i] = s.readObject(); } } } private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } 知识扩展 为什么底层数组要使用transient ArrayList实际上是动态数组，每次在放满以后自动增长设定的长度值，如果数组自动增长长度设为100，而实际只放了一个元素，那就会序列化99个null元素。为了保证在序列化的时候不会将这么多null同时进行序列化，ArrayList把元素数组设置为transient。 ...