【JavaSE面试篇】Java集合部分高频八股汇总-EW帮帮网

Vector：线程安全的动态数组，其内部方法基本都经过 synchronized 修饰，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。
Hashtable：线程安全的哈希表，HashTable 的加锁方法是给每个方法加上 synchronized 关键字，这样锁住的是整个 Table 对象，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用，如果要保证线程安全的哈希表，可以用 ConcurrentHashMap。

java.util.concurrent 包提供的都是线程安全的集合：

并发 Map：

ConcurrentHashMap：它与 HashTable 的主要区别是二者加锁粒度的不同，在 JDK1.7，ConcurrentHashMap 加的是分段锁，也就是 Segment 锁，每个 Segment 含有整个 table 的一部分，这样不同分段之间的并发操作就互不影响。在 JDK 1.8 ，它取消了 Segment 字段，直接在 table 元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率。对于 put 操作，如果 Key 对应的数组元素为 null，则通过 CAS 操作（Compare and Swap）将其设置为当前值。如果 Key 对应的数组元素（也即链表表头或者树的根元素）不为 null，则对该元素使用 synchronized 关键字申请锁，然后进行操作。如果该 put 操作使得当前链表长度超过一定阈值，则将该链表转换为红黑树，从而提高寻址效率。
ConcurrentSkipListMap：实现了一个基于 SkipList（跳表）算法的可排序的并发集合，SkipList 是一种可以在对数预期时间内完成搜索、插入、删除等操作的数据结构，通过维护多个指向其他元素的 “跳跃” 链接来实现高效查找。

并发 Set：

ConcurrentSkipListSet：是线程安全的有序的集合。底层是使用 ConcurrentSkipListMap 实现。
CopyOnWriteArraySet：是线程安全的 Set 实现，它是线程安全的无序的集合，可以将它理解成线程安全的 HashSet。有意思的是，CopyOnWriteArraySet 和 HashSet 虽然都继承于共同的父类 AbstractSet；但是，HashSet 是通过 “散列表” 实现的，而 CopyOnWriteArraySet 则是通过 “动态数组（CopyOnWriteArrayList）” 实现的，并不是散列表。

并发 List：

CopyOnWriteArrayList：它是 ArrayList 的线程安全的变体，其中所有写操作（add，set 等）都通过对底层数组进行全新复制来实现，允许存储 null 元素。即当对象进行写操作时，使用了 Lock 锁做同步处理，内部拷贝了原数组，并在新数组上进行添加操作，最后将新数组替换掉旧数组；若进行的读操作，则直接返回结果，操作过程中不需要进行同步。

并发 Queue：

ConcurrentLinkedQueue：是一个适用于高并发场景下的队列，它通过无锁的方式（CAS），实现了高并发状态下的高性能。通常，ConcurrentLinkedQueue 的性能要好于 BlockingQueue 。
BlockingQueue：与 ConcurrentLinkedQueue 的使用场景不同，BlockingQueue 的主要功能并不在于提升高并发时的队列性能，而在于简化多线程间的数据共享。BlockingQueue 提供一种读写阻塞等待的机制，即如果消费者速度较快，则 BlockingQueue 则可能被清空，此时消费线程再试图从 BlockingQueue 读取数据时就会被阻塞。反之，如果生产线程较快，则 BlockingQueue 可能会被装满，此时，生产线程再试图向 BlockingQueue 队列装入数据时，便会被阻塞等待。

并发 Deque：

LinkedBlockingDeque：是一个线程安全的双端队列实现。它的内部使用链表结构，每一个节点都维护了一个前驱节点和一个后驱节点。LinkedBlockingDeque 没有进行读写锁的分离，因此同一时间只能有一个线程对其进行操作
ConcurrentLinkedDeque：ConcurrentLinkedDeque 是一种基于链接节点的无限并发链表。可以安全地并发执行插入、删除和访问操作。当许多线程同时访问一个公共集合时，ConcurrentLinkedDeque 是一个合适的选择。

3. Collections和Collection的区别？

Collection：是 Java 集合框架中的一个接口，它是所有集合类的基础接口。它定义了一组通用的操作和方法，如添加、删除、遍历等，用于操作和管理一组对象。Collection 接口有许多实现类，如 List、Set 和 Queue 等。
Collections（注意有一个 s）：是 Java 提供的一个工具类，位于 java.util 包中。它提供了一系列静态方法，用于对集合进行操作和算法。Collections 类中的方法包括排序、查找、替换、反转、随机化等等。这些方法可以对实现了 Collection 接口的集合进行操作，如 List 和 Set。

4. 集合遍历的方法有哪些？

在 Java 中，集合的遍历方法主要有以下几种：

普通 for 循环：可以使用带有索引的普通 for 循环来遍历 List。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

for (int i = 0; i < list.size(); i++) {
    String element = list.get(i);
    System.out.println(element);
}

增强 for 循环（for-each 循环）：用于循环访问数组或集合中的元素。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

for (String element : list) {
    System.out.println(element);
}

Iterator 迭代器：可以使用迭代器来遍历集合，特别适用于需要删除元素的情况。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

Iterator<String> iterator = list.iterator();
while(iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}

ListIterator 列表迭代器：ListIterator 是迭代器的子类，可以双向访问列表并在迭代过程中修改元素。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

ListIterator<String> listIterator= list.listIterator();
while(listIterator.hasNext()) {
    String element = listIterator.next();
    System.out.println(element);
}

使用 forEach 方法： Java 8 引入了 forEach 方法，可以对集合进行快速遍历。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

list.forEach(element -> System.out.println(element));

Stream API： Java 8 的 Stream API 提供了丰富的功能，可以对集合进行函数式操作，如过滤、映射等。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

list.stream().forEach(element -> System.out.println(element));

List

常见的 List 集合（非线程安全）：

ArrayList ：基于动态数组实现，它允许快速的随机访问，即通过索引访问元素的时间复杂度为 O (1)。在添加和删除元素时，如果操作位置不是列表末尾，可能需要移动大量元素，性能相对较低。适用于需要频繁随机访问元素，而对插入和删除操作性能要求不高的场景，如数据的查询和展示等。
LinkedList ：基于双向链表实现，在插入和删除元素时，只需修改链表的指针，不需要移动大量元素，时间复杂度为 O (1)。但随机访问元素时，需要从链表头或链表尾开始遍历，时间复杂度为 O (n)。适用于需要频繁进行插入和删除操作的场景，如队列、栈等数据结构的实现，以及需要在列表中间频繁插入和删除元素的情况。

常见的 List 集合（线程安全）：

Vector ：和 ArrayList 类似，也是基于数组实现。Vector 中的方法大多是同步的，这使得它在多线程环境下可以保证数据的一致性，但在单线程环境下，由于同步带来的开销，性能会略低于 ArrayList 。
CopyOnWriteArrayList ：在对列表进行修改（如添加、删除元素）时，会创建一个新的底层数组，将修改操作应用到新数组上，而读操作仍然在原数组上进行，这样可以保证读操作不会被写操作阻塞，实现了读写分离，提高了并发性能。适用于读操作远远多于写操作的并发场景，如事件监听列表等，在这种场景下可以避免大量的锁竞争，提高系统的性能和响应速度。

5. 讲一下java里面list的几种实现，几种实现有什么不同？

ArrayList：是应用更加广泛的动态数组实现，它本身不是线程安全的，所以性能要好很多。与 Vector 近似，ArrayList 也是可以根据需要调整容量，不过两者的调整逻辑有所区别，Vector 在扩容时会提高 1 倍，而 ArrayList 则是增加 50%。
LinkedList：顾名思义是 Java 提供的双向链表，所以它不需要像上面两种那样调整容量，它也不是线程安全的。

这几种实现具体在什么场景下应该用哪种？

Vector 和 ArrayList：作为动态数组，其内部元素以数组形式顺序存储的，所以非常适合随机访问的场合。除了尾部插入和删除元素，往往性能会相对较差，比如我们在中间位置插入一个元素，需要移动后续所有元素。
而 LinkedList：进行节点插入、删除却要高效得多，但是随机访问性能则要比动态数组慢。

6. Arraylist和LinkedList的区别？

ArrayList和LinkedList都是 Java 中常见的集合类，它们都实现了List接口。

底层数据结构不同：ArrayList使用数组实现，通过索引进行快速访问元素。LinkedList使用链表实现，通过节点之间的指针进行元素的访问和操作。
插入和删除操作的效率不同：ArrayList在尾部的插入和删除操作效率较高，但在中间或开头的插入和删除操作效率较低，需要移动元素。LinkedList在任意位置的插入和删除操作效率都比较高，因为只需要调整节点之间的指针，但是LinkedList是不支持随机访问的，所以除了头结点外插入和删除的时间复杂度都是O(n)，效率也不是很高所以LinkedList基本没人用。
随机访问的效率不同：ArrayList支持通过索引进行快速随机访问，时间复杂度为O(1)。LinkedList需要从头或尾开始遍历链表，时间复杂度为O(n)。
空间占用：ArrayList在创建时需要分配一段连续的内存空间，因此会占用较大的空间。LinkedList每个节点只需要存储元素和指针，因此相对较小。
使用场景：ArrayList适用于频繁随机访问和尾部的插入删除操作，而LinkedList适用于频繁的中间插入删除操作和不需要随机访问的场景。
线程安全：这两个集合都不是线程安全的，Vector是线程安全的

7. 为什么ArrayList不是线程安全的，具体来说是哪里不安全？

在高并发添加数据下，ArrayList会暴露三个问题；

部分值为null（我们并没有add null进去）
索引越界异常
size与我们add的数量不符

三种情况都是如何产生的：

部分值为null：当线程 1 走到了扩容那里发现当前size是 9，而数组容量是 10，所以不用扩容，这时候 cpu 让出执行权，线程 2 也进来了，发现size是 9，而数组容量是 10，所以不用扩容，这时候线程 1 继续执行，将数组下标索引为 9 的位置set值了，还没有来得及执行size++，这时候线程 2 也来执行了，又把数组下标索引为 9 的位置set了一遍，这时候两个先后进行size++，导致下标索引 10 的地方就为null了。
索引越界异常：线程 1 走到扩容那里发现当前size是 9，数组容量是 10 不用扩容，cpu 让出执行权，线程 2 也发现不用扩容，这时候数组的容量就是 10，而线程 1 set完之后size++，这时候线程 2 再进来size就是 10，数组的大小只有 10，而你要设置下标索引为 10 的就会越界（数组的下标索引从 0 开始）；
size与我们add的数量不符：这个基本上每次都会发生，这个理解起来也很简单，因为size++本身就不是原子操作，可以分为三步：获取size的值，将size的值加 1，将新的size值覆盖掉原来的，线程 1 和线程 2 拿到一样的size值加完了同时覆盖，就会导致一次没有加上，所以肯定不会与我们add的数量保持一致的；

8. ArrayList的扩容机制说一下

ArrayList在添加元素时，如果当前元素个数已经达到了内部数组的容量上限，就会触发扩容操作。
ArrayList的扩容操作主要包括以下几个步骤：

计算新的容量：一般情况下，新的容量会扩大为原容量的 1.5 倍（在 JDK 10 之后，扩容策略做了调整），然后检查是否超过了最大容量限制。
创建新的数组：根据计算得到的新容量，创建一个新的更大的数组。
将元素复制：将原来数组中的元素逐个复制到新数组中。
更新引用：将ArrayList内部指向原数组的引用指向新数组。
完成扩容：扩容完成后，可以继续添加新元素。

ArrayList的扩容操作涉及到数组的复制和内存的重新分配，所以在频繁添加大量元素时，扩容操作可能会影响性能。为了减少扩容带来的性能损耗，可以在初始化ArrayList时预分配足够大的容量，避免频繁触发扩容操作。

之所以扩容是 1.5 倍，是因为 1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数。

// 新容量计算
int newCapacity = oldCapacity + (oldCapacity >> 1);

9. 线程安全的 List， CopyonWriteArraylist是如何实现线程安全的？

CopyOnWriteArrayList底层也是通过一个数组保存数据，使用volatile关键字修饰数组，保证当前线程对数组对象重新赋值后，其他线程可以及时感知到。

private transient volatile Object[] array;

在写入操作时，加了一把互斥锁ReentrantLock以保证线程安全。

public boolean add(E e) {
    //获取锁
    final ReentrantLock lock = this.lock;
    //加锁
    lock.lock();
    try {
        //获取到当前List集合保存数据的数组
        Object[] elements = getArray();
        //获取该数组的长度（这是一个伏笔，同时len也是新数组的最后一个元素的索引值）
        int len = elements.length;
        //将当前数组拷贝一份的同时，让其长度加1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        //将加入的元素放在新数组最后一位，len不是旧数组长度吗，为什么现在用它当成新数组的最后一个元素的索引？
        newElements[len] = e;
        //替换引用，将数组的引用指向给新数组的地址
        setArray(newElements);
        return true;
    } finally {
        //释放锁
        lock.unlock();
    }
}

看到源码可以知道写入新元素时，首先会先将原来的数组拷贝一份并且让原来数组的长度 + 1 后就得到了一个新数组，新数组里的元素和旧数组的元素一样并且长度比旧数组多一个长度，然后将新加入的元素放置都在新数组最后一个位置后，用新数组的地址替换掉老数组的地址就能得到最新的数据了。

在我们执行替换地址操作之前，读取的是老数组的数据，数据是有效数据；执行替换地址操作之后，读取的是新数组的数据，同样也是有效数据，而且使用该方式能比读写都加锁要更加的效率。

现在我们来看读操作，读是没有加锁的，所以读是一直都能读

public E get(int index) {
    return get(getArray(), index);
}

Map

常见的 Map 集合（非线程安全）：

HashMap ：是基于哈希表实现的 Map ，它根据键的哈希值来存储和获取键值对，JDK 1.8 中是用数组 + 链表 + 红黑树来实现的。HashMap 是非线程安全的，在多线程环境下，当多个线程同时对 HashMap 进行操作时，可能会导致数据不一致或出现死循环等问题。比如在扩容时，多个线程可能会同时修改哈希表的结构，从而破坏数据的完整性。
LinkedHashMap ：继承自 HashMap ，它在 HashMap 的基础上，使用双向链表维护了键值对的插入顺序或访问顺序，使得迭代顺序与插入顺序或访问顺序一致。由于它继承自 HashMap ，在多线程并发访问时，同样会出现与 HashMap 类似的线程安全问题。
TreeMap ：是基于红黑树实现的 Map ，它可以对键进行排序，默认按照自然顺序排序，也可以通过指定的比较器进行排序。TreeMap 是非线程安全的，在多线程环境下，如果多个线程同时对 TreeMap 进行插入、删除等操作，可能会破坏红黑树的结构，导致数据不一致或程序出现异常。

常见的 Map 集合（线程安全）：

Hashtable ：是早期 Java 提供的线程安全的 Map 实现，它的实现方式与 HashMap 类似，但在方法上使用了 synchronized 关键字来保证线程安全。通过在每个可能修改 Hashtable 状态的方法上加上 synchronized 关键字，使得在同一时刻，只能有一个线程能够访问 Hashtable 的这些方法，从而保证了线程安全。
ConcurrentHashMap ：在 JDK 1.8 以前采用了分段锁等技术来提高并发性能。在 ConcurrentHashMap 中，将数据分成多个段（Segment），每个段都有自己的锁。在进行插入、删除等操作时，只需要获取相应段的锁，而不是整个 Map 的锁，这样可以允许多个线程同时访问不同的段，提高了并发访问的效率。在 JDK 1.8 以后是通过 volatile + CAS 或者 synchronized 来保证线程安全的。

10. 如何对map进行快速遍历？

使用 Lambda 表达式和 forEach() 方法：在 Java 8 及以上版本中，可以使用 Lambda 表达式和 forEach() 方法来遍历 Map，这种方式更加简洁和函数式。

import java.util.HashMap;
import java.util.Map;

public class MapTraversalExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("key1", 1);
        map.put("key2", 2);
        map.put("key3", 3);

        // 使用 Lambda 表达式和 forEach() 方法遍历 Map
        map.forEach((key, value) -> System.out.println("Key: " + key + ", Value: " + value));
    }
}

使用 Stream API：Java 8 引入的 Stream API 也可以用于遍历 Map，可以将 Map 转换为流，然后进行各种操作。

import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;

public class MapTraversalExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("key1", 1);
        map.put("key2", 2);
        map.put("key3", 3);

        // 使用 Stream API 遍历 Map
        map.entrySet().stream()
           .forEach(entry -> System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue()));

        // 还可以进行其他操作，如过滤、映射等
        Map<String, Integer> filteredMap = map.entrySet().stream()
            .filter(entry -> entry.getValue() > 1)
            .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

        System.out.println(filteredMap);
    }
}

11. HashMap实现原理介绍一下？

在 JDK 1.7 版本之前，HashMap 数据结构是数组和链表，HashMap通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是O(n)，所以冲突很严重，一个索引上的链表非常长，效率就很低了。

所以在 JDK 1.8 版本的时候做了优化，当一个链表的长度超过 8 的时候就转换数据结构，不再使用链表存储，而是使用红黑树，查找时使用红黑树，时间复杂度O（log n)，可以提高查询性能，但是在数量较少时，即数量小于 6 时，会将红黑树转换回链表。

12. 了解的哈希冲突解决方法有哪些？

链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。
再哈希法（Rehashing）：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。
哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

13. HashMap是线程安全的吗？

hashmap 不是线程安全的，hashmap 在多线程会存在下面的问题：

JDK 1.7 HashMap 采用数组 + 链表的数据结构，多线程背景下，在数组扩容的时候，存在 Entry 链死循环和数据丢失问题。
JDK 1.8 HashMap 采用数组 + 链表 + 红黑二叉树的数据结构，优化了 1.7 中数组扩容的方案，解决了 Entry 链死循环和数据丢失问题。但是多线程背景下，put 方法存在数据覆盖的问题。

如果要保证线程安全，可以通过这些方法来保证：

多线程环境可以使用Collec tions.synchronizedMap同步加锁的方式，还可以使用HashTable，但是同步的方式显然性能不达标，而ConurrentHashMap更适合高并发场景使用。
ConcurrentHashmap在 JDK1.7 和 1.8 的版本改动比较大，1.7 使用Segment+HashEntry分段锁的方式实现，1.8 则抛弃了Segment，改为使用CAS+synchronized+Node实现，同样也加入了红黑树，避免链表过长导致性能的问题。

14. HashMap的put(key,val)和get(key)过程

存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量 (超过Load Facotr则resize为原来的 2 倍)。
获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用 equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制 (默认是8)，则使用红黑树来替换链表，从而提高速度。

15. HashMap一般用什么做Key？为啥String适合做Key呢？

用 string 做 key，因为 String对象是不可变的，一旦创建就不能被修改，这确保了Key的稳定性。如果Key是可变的，可能会导致hashCode和equals方法的不一致，进而影响HashMap的正确性。

16. 为什么HashMap要用红黑树而不是平衡二叉树？

平衡二叉树追求的是一种 “完全平衡” 状态：任何结点的左右子树的高度差不会超过 1，优势是树的结点是很平均分配的。这个要求实在是太严了，导致每次进行插入 / 删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
红黑树不追求这种完全平衡状态，而是追求一种 “弱平衡” 状态：整个树最长路径不会超过最短路径的 2 倍。优势是虽然牺牲了一部分查找的性能效率，但是能够换取一部分维持树平衡状态的成本。与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因。

17. hashmap key可以为null吗？

可以为 null。

hashMap 中使用hash()方法来计算key的哈希值，当key为空时，直接另key的哈希值为 0，不走 key.hashCode ()方法；

static final int hash(Object key) {
    int h;
    //当key等于null的时候，不走hashCode()方法
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hashMap 虽然支持key和value为null，但是null作为key只能有一个，null作为value可以有多个；
因为 hashMap 中，如果key值一样，那么会覆盖相同key值的value为最新，所以key为null只能有一个。

18. 重写HashMap的equal和hashcode方法需要注意什么？

HashMap 使用Key对象的hashCode()和equals方法去决定key-value对的索引。当我们试着从HashMap中获取值的时候，这些方法也会被用到。如果这些方法没有被正确地实现，在这种情况下，两个不同Key也许会产生相同的 hashCode ()和equals () 输出，HashMap将会认为它们是相同的，然后覆盖它们，而非把它们存储到不同的地方。

同样的，所有不允许存储重复数据的集合类都使用 hashCode ()和equals () 去查找重复，所以正确实现它们非常重要。equals ()和hashCode () 的实现应该遵循以下规则：

如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()总是为true的。
如果o1.hashCode() == o2.hashCode()，并不意味着o1.equals(o2)会为true。

19. 列举HashMap在多线程下可能会出现的问题？

JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。

20. HashMap的扩容机制介绍一下

hashMap 默认的负载因子是 0.75，即如果 hashmap 中的元素个数超过了总容量 75%，则会触发扩容，扩容分为两个步骤：

第 1 步是对哈希表长度的扩展（2 倍）
第 2 步是将旧哈希表中的数据放到新的哈希表中。

因为我们使用的是 2 次幂的扩展 (指长度扩为原来 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。

如我们从 16 扩展为 32 时，具体的变化如下所示：

因此元素在重新计算hash之后，因为n变为 2 倍，那么n - 1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成 “原索引 +oldCap”。可以看看下图为 16 扩充为 32 的resize示意图：

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是 0 还是 1 可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

21. HashMap的大小为什么是2的n次方大小呢？

在 JDK1.7 中，HashMap 整个扩容过程就是分别取出数组元素，一般该元素是最后一个放入链表中的元素，然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的 hash 值计算其在新数组中的下标，然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。

而在 JDK 1.8 中，HashMap 对扩容操作做了优化。由于扩容数组的长度是 2 倍关系，所以对于假设初始 tableSize = 4 要扩容到 8 来说就是 0100 到 1000 的变化（左移一位就是 2 倍），在扩容中只用判断原来的 hash 值和左移动的一位（newtable 的值）按位与操作是 0 或 1 就行，0 的话索引不变，1 的话索引变成原索引加上扩容前数组。

之所以能通过这种 “与运算” 来重新分配索引，是因为 hash 值本来就是随机的，而 hash 按位与上 newTable 得到的 0（扩容前的索引位置）和 1（扩容前索引位置加上扩容前数组长度的数值索引处）就是随机的，所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。

22. 说说hashmap的负载因子

HashMap 负载因子 loadFactor 的默认值是 0.75，当 HashMap 中的元素个数超过了容量的 75% 时，就会进行扩容。

默认负载因子为 0.75，是因为它提供了空间和时间复杂度之间的良好平衡。

负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞，降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。

23. Hashmap和Hashtable有什么不一样的？Hashmap一般怎么用？

HashMap 线程不安全，效率高一点，可以存储 null 的 key 和 value，null 的 key 只能有一个，null 的 value 可以有多个。默认初始容量为 16，每次扩充变为原来 2 倍。创建时如果给定了初始容量，则扩充为 2 的幂次方大小。底层数据结构为数组 + 链表，插入元素后如果链表长度大于阈值（默认为 8），先判断数组长度是否小于 64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
HashTable 线程安全，效率低一点，其内部方法基本都经过 synchronized 修饰，不可以有 null 的 key 和 value。默认初始容量为 11，每次扩容变为原来的 2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组 + 链表。它基本被淘汰了，要保证线程安全可以用 ConcurrentHashMap。
怎么用：HashMap 主要用来存储键值对，可以调用 put 方法向其中加入元素，调用 get 方法获取某个键对应的值，也可以通过 containsKey 方法查看某个键是否存在等

24. ConcurrentHashMap怎么实现的？

JDK 1.7 ConcurrentHashMap

在 JDK 1.7 中它使用的是数组加链表的形式实现的，而数组又分为：大数组 Segment 和小数组 HashEntry。 Segment 是一种可重入锁（ReentrantLock），在 ConcurrentHashMap 里扮演锁的角色；HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素。

JDK 1.7 ConcurrentHashMap 分段锁技术将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

JDK 1.8 ConcurrentHashMap

在 JDK 1.7 中，ConcurrentHashMap 虽然是线程安全的，但因为它的底层实现是数组 + 链表的形式，所以在数据比较多的情况下访问是很慢的，因为要遍历整个链表，而 JDK 1.8 则使用了数组 + 链表 / 红黑树的方式优化了 ConcurrentHashMap 的实现，具体实现结构如下：

JDK 1.8 ConcurrentHashMap JDK 1.8 ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。添加元素时首先会判断容器是否为空：

如果为空则使用 volatile 加 CAS 来初始化
如果容器不为空，则根据存储的元素计算该位置是否为空。
- 如果根据存储的元素计算结果为空，则利用 CAS 设置该节点；
- 如果根据存储的元素计算结果不为空，则使用 synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

如果把上面的执行用一句话归纳的话，就相当于是ConcurrentHashMap通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。

而且 JDK 1.8 使用的是红黑树优化了之前的固定链表，那么当数据量比较大的时候，查询性能也得到了很大的提升，从之前的 O(n) 优化到了 O(logn) 的时间复杂度。

25. ConcurrentHashMap用了悲观锁还是乐观锁?

悲观锁和乐观锁都有用到。

添加元素时首先会判断容器是否为空：

如果为空则使用 volatile 加 CAS（乐观锁） 来初始化。
如果容器不为空，则根据存储的元素计算该位置是否为空。
如果根据存储的元素计算结果为空，则利用 CAS（乐观锁） 设置该节点；
如果根据存储的元素计算结果不为空，则使用 synchronized（悲观锁） ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

26. HashTable 底层实现原理是什么？

Hashtable 的底层数据结构主要是数组加上链表，数组是主体，链表是解决 hash 冲突存在的。
HashTable 是线程安全的，实现方式是Hashtable 的所有公共方法均采用 synchronized 关键字，当一个线程访问同步方法，另一个线程也访问的时候，就会陷入阻塞或者轮询的状态。

27. HashTable线程安全是怎么实现的？

Hashtable是通过使用了 synchronized 关键字来保证其线程安全

因为它的put，get做成了同步方法，保证了Hashtable的线程安全性，每个操作数据的方法都进行同步控制之后，由此带来的问题任何一个时刻，只能有一个线程可以操纵Hashtable，所以其效率比较低。

28. hashtable 和concurrentHashMap有什么区别？

底层数据结构：

jdk7 之前的 ConcurrentHashMap 底层采用的是分段的数组 + 链表实现，jdk8 之后采用的是数组 + 链表 / 红黑树；
HashTable 采用的是数组 + 链表，数组是主体，链表是解决 hash 冲突存在的。

实现线程安全的方式：

jdk8 以前，ConcurrentHashMap 采用分段锁，对整个数组进行了分段分割，每一把锁只锁容器里的一部分数据，多线程访问不同数据段里的数据，就不会存在锁竞争，提高了并发访问；jdk8 以后，直接采用数组 + 链表 / 红黑树，并发控制使用 CAS 和 synchronized 操作，更加提高了速度。
HashTable：所有的方法都加了锁来保证线程安全，但是效率非常的低下，当一个线程访问同步方法，另一个线程也访问的时候，就会陷入阻塞或者轮询的状态。

29. 说一下HashMap和Hashtable、ConcurrentMap的区别？

HashMap线程不安全，效率高一点，可以存储 null 的 key 和 value，null 的 key 只能有一个，null 的 value 可以有多个。默认初始容量为 16，每次扩充变为原来 2 倍。创建时如果给定了初始容量，则扩充为 2 的幂次方大小。底层数据结构为数组 + 链表，插入元素后如果链表长度大于阈值（默认为 8），先判断数组长度是否小于 64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
HashTable线程安全，效率低一点，其内部方法基本都经过synchronized修饰，不可以有 null 的 key 和 value。默认初始容量为 11，每次扩容变为原来的 2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组 + 链表。它基本被淘汰了，要保证线程安全可以用ConcurrentHashMap。
ConcurrentHashMap是 Java 中的一个线程安全的哈希表实现，它可以在多线程环境下并发地进行读写操作，而不需要像传统的HashTable那样在读写时加锁。ConcurrentHashMap的实现原理主要基于分段锁和CAS操作。它将整个哈希表分成了多Segment（段），每个Segment都类似于一个小的HashMap，它拥有自己的数组和一个独立的锁。在ConcurrentHashMap中，读操作不需要锁，可以直接对Segment进行读取，而写操作则只需要锁定对应的Segment，而不是整个哈希表，这样可以大大提高并发性能。

Set

30. Set集合有什么特点？如何实现key无重复的？

set 集合特点：Set 集合中的元素是唯一的，不会出现重复的元素。
set 实现原理：Set 集合通过内部的数据结构（如哈希表、红黑树等）来实现 key 的无重复。当向 Set 集合中插入元素时，会先根据元素的hashCode值来确定元素的存储位置，然后再通过equals方法来判断是否已经存在相同的元素，如果存在则不会再次插入，保证了元素的唯一性。

31. 有序的Set是什么？记录插入顺序的集合是什么？

有序的 Set 是 TreeSet 和 LinkedHashSet。TreeSet 是基于红黑树实现，保证元素的自然顺序。LinkedHashSet 是基于双重链表和哈希表的结合来实现元素的有序存储，保证元素添加的自然顺序
记录插入顺序的集合通常指的是 LinkedHashSet，它不仅保证元素的唯一性，还可以保持元素的插入顺序。当需要在 Set 集合中记录元素的插入顺序时，可以选择使用 LinkedHashSet 来实现。

【JavaSE面试篇】Java集合部分高频八股汇总

概念

1. 说说Java中的集合？

2. Java中的线程安全的集合有什么？