知识星球

主题

Java 集合 ​

2 Java 集合 ​

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对(两个对象)的映射表。

2.1 Collection ​

集合有哪些类？ ​

  • Set
    • TreeSet 基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
    • HashSet 基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
    • LinkedHashSet 具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。
  • List
    • ArrayList 基于动态数组实现，支持随机访问。
    • Vector 和 ArrayList 类似，但它是线程安全的。
    • LinkedList 基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。
  • Queue
    • LinkedList 可以用它来实现双向队列。
    • PriorityQueue 基于堆结构实现，可以用它来实现优先队列。

ArrayList的底层？ ​

_ArrayList_实现了_List_接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟_Vector_大致相同。每个_ArrayList_都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java泛型只是编译器提供的语法糖，所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。

ArrayList_base

ArrayList自动扩容？ ​

每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过ensureCapacity(int minCapacity)方法来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。

数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

ArrayList_add

ArrayList的Fail-Fast机制？ ​

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

ArrayList和LinkedList的区别？ ​

ArrayList基于数组实现，存储空间是连续的，LinkedList基于链表，存储空间是不连续的。

对于随机访问，ArrayList更加高效，而LinkedList需要遍历链表。

对于增、删操作，LinkedList更加高效，而ArrayList需要进行数据移动。

同等的数据量，LinkedList占用的空间更小，而ArrayList需要预留空间，方便后续数据增加，LinkedList只需要增加一个节点。

2.2 Map ​

Map有哪些类？ ​

  • TreeMap 基于红黑树实现。
  • HashMap 1.7基于哈希表实现，1.8基于数组+链表+红黑树。
  • HashTable 和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高(1.7 ConcurrentHashMap 引入了分段锁, 1.8 引入了红黑树)。
  • LinkedHashMap 使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用(LRU)顺序。

JDK7 HashMap如何实现？ ​

哈希表有两种实现方式，一种开放地址方式(Open addressing)，另一种是冲突链表方式(Separate chaining with linked lists)。Java7 _HashMap_采用的是冲突链表方式。

HashMap_base

从上图容易看出，如果选择合适的哈希函数，put()和get()方法可以在常数时间内完成。但在对_HashMap_进行迭代时，需要遍历整个table以及后面跟的冲突链表。因此对于迭代比较频繁的场景，不宜将_HashMap_的初始大小设的过大。

有两个参数可以影响_HashMap_的性能: 初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。

JDK8 HashMap如何实现？ ​

根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。

为了降低这部分的开销，在 Java8 中，当链表中的元素达到了 8 个时，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

error.图片加载失败

HashMap的底层数据结构是什么？ ​

JDK1.7，HashMap 由数组+链表组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。

JDK 8 中，HashMap 由数组+链表+红黑树组成。链表过长，会严重影响 HashMap 的性能，而红黑树搜索的时间复杂度是 O(logn)，而链表是糟糕的 O(n)。

因此，JDK 8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：

  • 当链表超过 8 且数据总量超过 64 时会转红黑树。
  • 将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。

为什么链表改为红黑树的阈值是 8? ​

因为泊松分布，我们来看作者在源码中的注释：

txt
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

翻译过来大概的意思是：理想情况下使用随机的哈希码，容器中节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为 8 时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了 8，是根据概率统计而选择的。

解决hash冲突的办法有哪些？HashMap用的哪种？ ​

解决Hash冲突方法有：

  • 开放定址法：也称为再散列法，基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H(p),如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正删除节点。
  • 再哈希法：双重散列，多重散列，提供多个不同的hash函数，当R1=H1(key1)发生冲突时，再计算R2=H2(key1)，直到没有冲突为止。这样做虽然不易产生堆集，但增加了计算的时间。
  • 链地址法：拉链法，将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
  • 建立公共溢出区：将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

HashMap中采用的是链地址法 。

为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树? ​

红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。

当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。

如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。

HashMap默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8 ？ ​

为什么HashMap的加载因子一定是0.75？而不是0.8，0.6？

HashMap 中 key 的存储索引是怎么计算的？ ​

首先根据key的值计算出hashcode的值，然后根据hashcode计算出hash值，最后通过hash&（length-1）计算得到存储的位置。

蔚来一面：HashMap 的 hash 方法原理是什么？

HashMap 的put方法流程？ ​

以JDK 8为例，简要流程如下：

1、首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；

2、如果数组是空的，则调用 resize 进行初始化；

3、如果没有哈希冲突直接放在对应的数组下标里；

4、如果冲突了，且 key 已经存在，就覆盖掉 value；

5、如果冲突后，发现该节点是红黑树，就将这个节点挂在树上；

6、如果冲突后是链表，判断该链表是否大于 8 ，如果大于 8 并且数组容量小于 64，就进行扩容；如果链表节点大于 8 并且数组的容量大于 64，则将这个结构转换为红黑树；否则，链表插入键值对，若 key 存在，就覆盖掉 value。

hashmap-put.png

JDK 8 为什么要 hashcode 异或其右移十六位的值？ ​

因为在JDK 7 中扰动了 4 次，计算 hash 值的性能会稍差一点点。

从速度、功效、质量来考虑，JDK 8 优化了高位运算的算法，通过hashCode()的高16位异或低16位实现：(h = k.hashCode()) ^ (h >>> 16)。

这么做可以在数组 table 的 length 比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

为什么 hash 值要与length-1相与？ ​

  • 把 hash 值对数组长度取模运算，模运算的消耗很大，没有位运算快。
  • 当 length 总是 2 的n次方时，h& (length-1) 运算等价于对length取模，也就是 h%length，但是 & 比 % 具有更高的效率。

HashMap数组的长度为什么是 2 的幂次方？ ​

2 的 N 次幂有助于减少碰撞的几率。如果 length 为2的幂次方，则 length-1 转化为二进制必定是11111……的形式，在与h的二进制与操作效率会非常的快，而且空间不浪费。

hashmap-length.png

当 length =15时，6 和 7 的结果一样，这样表示他们在 table 存储的位置是相同的，也就是产生了碰撞，6、7就会在一个位置形成链表，4和5的结果也是一样，这样就会导致查询速度降低。

如果我们进一步分析，还会发现空间浪费非常大，以 length=15 为例，在 1、3、5、7、9、11、13、15 这八处没有存放数据。因为hash值在与14（即 1110）进行&运算时，得到的结果最后一位永远都是0，即 0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的。

HashMap数组容量是怎样计算的？ ​

HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。会取大于或等于这个数的 且最近的2次幂作为 table 数组的初始容量，使用tableSizeFor(int)方法，如 tableSizeFor(10) = 16（2 的 4 次幂），tableSizeFor(20) = 32（2 的 5 次幂），也就是说 table 数组的长度总是 2 的次幂。

JDK 8 源码如下：

java
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;
    }

让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。

HashMap 的扩容方式？ ​

1、JDK1.7版本扩容 ①：先生成新数组；

②：遍历老数组中的每个位置上的链表上的每个元素；

③：获取每个元素的key，并基于新数组长度，计算出每个元素在新数组中的下标；

④：将元素添加到新数组中去；

⑤：所有元素转移完之后，将新数组赋值给HashMap对象的table属性。

2、JDK1.8版本扩容 ①：先生成新数组；

②：遍历老数组中的每个位置上的链表或红黑树；

③：如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去；

④：如果是红黑树，则先遍历红黑树，先计算出红黑树中每个元素对应在新数组中的下标位置；

a：统计每个下标位置的元素个数；

b：如果该位置下的元素个数超过了8，则生成一个新的红黑树，并将根节点添加到新数组的对应位置；

c：如果该位置下的元素个数没有超过8，那么则生成一个链表，并将链表的头节点添加到新数组的对应位置；

⑤：所有元素转移完了之后，将新数组赋值给HashMap对象的table属性。

一般用什么作为HashMap的key? ​

一般用Integer、String 这种不可变类当作 HashMap 的 key，String 最为常见。

  • 因为字符串是不可变的，所以在它创建的时候 hashcode 就被缓存了，不需要重新计算。
  • 因为获取对象的时候要用到 equals() 和 hashCode() 方法，那么键对象正确的重写这两个方法是非常重要的。Integer、String 这些类已经很规范的重写了 hashCode() 以及 equals() 方法。

HashMap为什么线程不安全？ ​

  • JDK 7 时多线程下扩容会造成死循环。
  • 多线程的put可能导致元素的丢失。
  • put和get并发时，可能导致get为null。

京东一面：为什么 HashMap 是线程不安全的？

简述 Java 的 TreeMap ​

TreeMap 是底层利用红黑树实现的 Map 结构，底层实现是一棵平衡的排序二叉树，由于红黑树的插入、删除、遍历时间复杂度都为 O(logN)，所以性能上低于哈希表。但是哈希表无法提供键值对的有序输出，红黑树可以按照键的值的大小有序输出

HashMap 和 Hashtable 有什么区别？ ​

  • HashMap 是 Hashtable 的轻量级实现，HashMap 允许 key 和 value 为 null，但最多允许一条记录的 key 为 null.而 HashTable 不允许。
  • HashTable 中的方法是线程安全的，而 HashMap 不是。在多线程访问 HashMap 需要提供额外的同步机制。
  • Hashtable 使用 Enumeration 进行遍历，HashMap 使用 Iterator 进行遍历。

如何决定使用 HashMap 还是 TreeMap? ​

如果对 Map 进行插入、删除或定位一个元素的操作更频繁，HashMap 是更好的选择。如果需要对 key 集合进行有序的遍历，TreeMap 是更好的选择。

HashSet是如何实现的？ ​

_HashSet_是对_HashMap_的简单包装，对_HashSet_的函数调用都会转换成合适的_HashMap_方法

java
//HashSet是对HashMap的简单包装
public class HashSet<E>
{
    ......
    private transient HashMap<E,Object> map;//HashSet里面有一个HashMap
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

什么是WeakHashMap? ​

我们都知道Java中内存是通过GC自动管理的，GC会在程序运行过程中自动判断哪些对象是可以被回收的，并在合适的时机进行内存释放。GC判断某个对象是否可被回收的依据是，是否有有效的引用指向该对象。如果没有有效引用指向该对象(基本意味着不存在访问该对象的方式)，那么该对象就是可回收的。这里的有效引用 并不包括弱引用。也就是说，虽然弱引用可以用来访问对象，但进行垃圾回收时弱引用并不会被考虑在内，仅有弱引用指向的对象仍然会被GC回收。

WeakHashMap 内部是通过弱引用来管理entry的，弱引用的特性对应到 WeakHashMap 上意味着什么呢？

WeakHashMap 里的entry可能会被GC自动删除，即使程序员没有调用remove()或者clear()方法。

WeakHashMap 的这个特点特别适用于需要缓存的场景。在缓存场景下，由于内存是有限的，不能缓存所有对象；对象缓存命中可以提高系统效率，但缓存MISS也不会造成错误，因为可以通过计算重新得到。

fail-fast 和 fail-safe 迭代器的区别是什么？ ​

  • fail-fast 直接在容器上进行，在遍历过程中，一旦发现容器中的数据被修改，就会立刻抛出 ConcurrentModificationException 异常从而导致遍历失败。常见的使用 fail-fast 方式的容器有 HashMap 和 ArrayList 等。
  • fail-safe 这种遍历基于容器的一个克隆。因此对容器中的内容修改不影响遍历。常见的使用 fail-safe 方式遍历的容器有 ConcurrentHashMap 和 CopyOnWriteArrayList。

Collection 和 Collections 有什么区别？ ​

  • Collection 是一个集合接口，它提供了对集合对象进行基本操作的通用接口方法，所有集合都是它的子类，比如 List、Set 等。
  • Collections 是一个包装类，包含了很多静态方法、不能被实例化，而是作为工具类使用，比如提供的排序方法：Collections.sort(list);提供的反转方法：Collections.reverse(list)。

红黑树有什么特征？ ​

  • 每个节点不是黑色就是红色
  • 根节点是黑色
  • 每个叶子节点都是黑色（指向为空的叶子节点）
  • 如果一个叶子节点是红色，其子节点必须是黑色
  • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点

Released under the MIT License.

Copyright © 2024-2025 lz