概念

数组和集合两种数据结构的区别

数组：固定长度（一旦创建长度无法改变）；可以包含基本数据类型和对象；可以直接访问元素

集合：动态长度（可以根据需要动态增加或减少元素）；只能包含对象；需要迭代器或其他方法访问元素

（迭代器：一种设计模式，用于遍历数据结构）

（迭代器常用方法：hasNext(), next(), remove()）

用过的一些Java集合类

ArrayList：动态数组，实现了List接口，支持动态增长

（List接口：List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引，可以根据序号存取容器中的元素）

LinkedList：双向链表，也实现了LIst接口，支持快速的插入和删除操作

HashMap：基于哈希表的Map实现，存储键值对，通过键快速查找值

HashSet：基于HahsMap实现的Set集合，用于存储唯一元素

TreeMap：基于红黑树实现的有序Map集合，可以按照键的顺序进行排序

LinkedHashMap：基于哈希表和双向链表实现的Map集合，保持插入顺序或访问顺序

PriorityQueue：优先队列，可以按照比较器或元素的自然顺序进行排序

Java中的集合

img

List：有序的Collection，能精准控制元素的插入位置，能根据索引访问元素。常用的类有LinkedList，ArrayList，Vector，Stack。

  • ArrayList：容量可变的非线程安全列表，支持快速随机访问，但插入和删除速度很慢。
  • LinkedList：本质是一个双向链表，与上面相比插入和删除速度更快，但随机访问速度更慢。

Set：元素不允许重复，无序。常用的实现有HashSet，LinkedHashSet，TreeSet。

  • HashSet：通过HashMap实现，使用key保证元素唯一性，但不保证有序性，线程不安全。
  • LinkedHashSet：继承自HashSet，通过LinkedHashMap实现，使用双向链表维护元素插入顺序。
  • TreeSet：通过TreeMap实现，按照比较规则插入新元素，保证插入后集合仍然有序。

Map：键值对集合，存储键、值和之间的映射。Key无序且唯一，value不要求有序且允许重复。Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值。常用的实现有TreeMap，HashMap，HashTable，LinkedHashMap，ConcurrentHashMap。

  • HashMap：JDK1.8前由数组+链表组成，数组是主体，链表解决哈希冲突。之后改变了解决哈希冲突的方式，即当链表长度大于阈值时，链表转化为红黑树，减少搜索时间。

  • LinkedHashMap：继承自HashMap，底层仍然是基于拉链式散列结构（即由数组和链表或红黑树组成）。另外增加了一条双向链表，使得可以保持键值对的插入顺序。同时实现了访问顺序相关逻辑。

  • HashTable：数组+链表，数组是主体，链表解决哈希冲突。

  • TreeMap：红黑树（自平衡的排序二叉树）

  • ConcurrentHashMap：Node数组+链表+红黑树，线程安全。

    （线程安全：多个线程访问同一段代码时，采用加锁机制，确保同一时刻只有一个线程在操作共享数据，避免数据不一致或污染的问题）

Java中线程安全的集合有哪些

  • java.util包：Vector、HashTable

  • java.util.concurrent包

    • 并发Map：ConcurrentHashMap、ConcurrentSkipListMap

    • 并发Set：ConcurrentSkipListSet、CopyOnWriteArraySet

    • 并发List：CopyOnWriteArrayList

    • 并发Queue：ConcurrentLinkedQueue、BlockingQueue

    • 并发Deque：LinkedBlockingDeque、ConcurrentLinkedDeque

      （Deque：双端队列）

Collections和Collection的区别

Collections：Java提供的一个工具类，位于java.util包中，提供了一系列静态方法，用于对集合进行操作和算法。该类中的方法包括排序、查找、替换、反转、随机化等。这些方法可以对实现了Collection接口的集合进行操作，如List和Set。

Collection：Java集合框架中的一个接口，是所有集合类的基础接口。定义了一组通用的操作和方法，如添加、删除、遍历等，用于操作和管理一组对象。该接口有许多实现类，如List、Set和Queue等。

集合遍历的方法有哪些

  • 普通for循环
  • 增强for循环（for—each循环）
    • eg. for(String element : list){}
  • Iterator迭代器（特别适用于需要删除元素的情况）
1
2
3
4
5
6
7
List<String> list = new ArrayList<>();
//……
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
	String element = iterator.next();
    //……
}

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

    （与上面的区别为：ListIterator listIterator = list.listIterator();）

  • 使用forEach方法

1
list.forEach(element -> System.out.println(element));
  • Sream API：可以对集合进行函数式操作，如过滤、映射等
1
list.stream().forEach(element -> System.out.println(element));

List

List的几种实现及其不同

image.png

  • Vector：线程安全的动态数组，内部使用对象数组来保存数据，可以根据需要自动增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。
  • ArrayList：非线程安全的动态数组，性能更好，应用更加广泛，也可以根据需要调整容量。
  • LinkedList：双向链表，不需要像上面那样调整容量，非线程安全。

综上，前两个作为动态数组，内部元素以数组形式顺序存储，适合随机访问。除了在尾部的插入和删除操作，性能相对较差（比如中间插入一个元素，需要移动后续所有元素）。第三个进行节点插入、删除较高效，但随机访问性能较慢。

ArrayList和LinkedList的区别

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

为什么ArrayList不是线程安全的

在高并发添加数据下，ArrayList会暴露以下三个问题及其可能情况：

  • 部分值为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的数量保持一致的

把ArrayList变成线程安全的方式

  • 使用Collections类的synchronizedList方法将ArrayList包装成线程安全的List：
1
List<String> synchronizedList = Collections.synchronizedList(arrayList);
  • 使用CopyOnWriteArrayList类代替ArrayList，它是一个线程安全的List实现：
1
CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>(arrayList);
  • 使用Vector类代替ArrayList，Vector是线程安全的List实现：
1
Vector<String> vector = new Vector<>(arrayList);

ArrayList和LinkedList的应用场景

  • 前者适用于需要频繁访问和遍历集合元素，并且集合大小不经常改变的场景。
  • 后者适用于频繁进行插入和删除操作，或者集合大小经常改变的场景。

ArrayList的扩容机制

在添加元素时，如果当前元素个数已经达到了内部数组的容量上限就会触发扩容操作。

步骤如下：

  • 计算新的容量：一般会扩大为原容量的1.5倍，然后检查是否超过了最大容量限制。
  • 创建新的数组：根据新容量创建更大的新数组。
  • 复制元素：将原数组的元素逐个复制到新数组。
  • 更新引用：将ArrayList内部指向原数组的引用指向新数组。
  • 完成扩容：扩容完成后，可以继续添加新元素。

（1.5倍可以充分利用移位操作，减少浮点数或者运算时间和运算次数）

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

线程安全的 List——CopyonWriteArraylist如何实现线程安全

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

1
private transient volatile Object[] array;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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后就得到了一个新数组，新数组里的元素和旧数组的元素一样并且长度比旧数组多一个长度，然后将新加入的元素放置都在新数组最后一个位置后，用新数组的地址替换掉老数组的地址就能得到最新的数据了。

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

以下为读操作，读没有加锁，所以一直能读

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

Map

HashMap实现原理

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

img

  • JDK1.8进行优化，当一个链表的长度超过8时就转换数据结构，不再使用链表存储，而是红黑树，查找时使用红黑树，时间复杂度为O(log n)，可以提高查询性能，但在数量较少时(数量小于6)，会将红黑树转换回链表。

img

哈希冲突解决方法

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

HashMap是线程安全的吗

不是。HashMap在多线程会存在下面的问题：

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

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

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

HashMap的put过程

img

  • 根据要添加的键的哈希码计算在数组中的位置（索引）
  • 检查该位置是否为空（即没有键值对存在）
    • 如果为空，则直接在该位置创建一个新的Entry对象来存储键值对。将要添加的键值对作为该Entry的键和值，并保存在数组的对应位置。将HashMap的修改次数加1，以便在进行迭代时发现并发修改。
  • 如果该位置已经存在其他键值对，检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同
    • 如果相同，则表示找到了相同的键，直接将新的值替换旧的值，完成更新操作。
  • 如果第一个键值对的哈希码和键不相同，则需要遍历链表或红黑树来查找是否有相同的键
    • 如果键值对集合是链表结构，从链表的头部开始逐个比较键的哈希码和equals()方法，直到找到相同的键或达到链表末尾。
      • 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
      • 如果没有找到相同的键，则将新的键值对添加到链表的头部。
    • 如果键值对集合是红黑树结构，在红黑树中使用哈希码和equals()方法进行查找。根据键的哈希码，定位到红黑树中的某个节点，然后逐个比较键，直到找到相同的键或达到红黑树末尾。
      • 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
      • 如果没有找到相同的键，则将新的键值对添加到红黑树中。
  • 检查链表长度是否达到阈值（默认为8）
    • 如果链表长度超过阈值，且HashMap的数组长度大于等于64，则会将链表转换为红黑树，以提高查询效率。
  • 检查负载因子是否超过阈值（默认为0.75）
    • 如果键值对的数量（size）与数组的长度的比值大于阈值，则需要进行扩容操作。
  • 扩容操作
    • 创建一个新的两倍大小的数组。
    • 将旧数组中的键值对重新计算哈希码并分配到新数组中的位置。
    • 更新HashMap的数组引用和阈值参数。
  • 完成添加操作

（HashMap是非线程安全的，如果在多线程环境下使用，需要采取额外的同步措施或使用线程安全的ConcurrentHashMap。）

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)，则使用红黑树来替换链表，从而提高速度。

HashMap调用get方法一定安全吗

不一定。需注意以下两点：

  • 空指针异常：如果用null作为键调用get方法，而且HashMap没有初始化，那么会抛出空指针异常。（如果HashMap已经初始化，允许使用null为键）
  • 线程安全：HashMap本身不是线程安全，如果需要在多线程环境使用类似HashMap的数据结构，可以考虑用ConcurrentHashMap。

HashMap一般用什么作为Key

用String作为Key，因为String对象不可变，一旦创建不可修改，确保了Key的稳定性。（如果Key可变，可能会导致HashCode和equals方法的不一致，进而影响HashMap的准确性。）

为什么HashMap用红黑树而不是平衡二叉树

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

HashMap的Key可以为null吗

可以。

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

img

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

重写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。

    （可以把hashCode理解为房间号，而equals理解为身份证号，住在同一个房间，不一定是同一个人，不住在同一个房间，必然不是同一个人。）

重写HashMap的equal方法不当会出现什么问题

HashMap在比较元素时，会先通过hashCode进行比较，相同的情况下再通过equals进行比较。

所以 equals相等的两个对象，hashCode一定相等。hashCode相等的两个对象，equals不一定相等（比如散列冲突的情况）

重写了equals方法，不重写hashCode方法时，可能会出现equals方法返回为true，而hashCode方法却返回false，这样的一个后果会导致在hashmap等类中存储多个一模一样的对象，导致出现覆盖存储的数据的问题，这与hashmap只能有唯一的key的规范不符合。

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

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

HashMap的扩容机制

HashMap默认的负载因子是0.75，即如果HashMap中的元素个数超过了总容量的75%，就会触发扩容。

扩容包括以下两个步骤：

  • 对哈希表长度的扩展（2倍）
  • 将旧哈希表中的数据放到新的哈希表中

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

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

img

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

img

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

img

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

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（扩容前索引位置加上扩容前数组长度的数值索引处）就是随机的，所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。

往hashmap存20个元素，会扩容几次？

当插入 20 个元素时，HashMap 的扩容过程如下：

初始容量：16

  • 插入第 1 到第 12 个元素时，不需要扩容。
  • 插入第 13 个元素时，达到负载因子限制，需要扩容。此时，HashMap 的容量从 16 扩容到 32。

扩容后的容量：32

  • 插入第 14 到第 24 个元素时，不需要扩容。

因此，总共会进行一次扩容。

说说hashmap的负载因子

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

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

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

HashMap和HashTable有什么区别

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

HashMap一般怎么用

HashMap主要用来存储键值对，可以调用put方法向其中加入元素，调用get方法获取某个键对应的值，也可以通过containsKey方法查看某个键是否存在。

ConcurrentHashMap是怎么实现的

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

img

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

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

img

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

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

简而言之，就相当于是ConcurrentHashMap通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。

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

分段锁是怎么加锁的

在 ConcurrentHashMap 中，将整个数据结构分为多个 Segment，每个 Segment 都类似于一个小的 HashMap，每个 Segment 都有自己的锁，不同 Segment 之间的操作互不影响，从而提高并发性能。

在 ConcurrentHashMap 中，对于插入、更新、删除等操作，需要先定位到具体的 Segment，然后再在该 Segment 上加锁，而不是像传统的 HashMap 一样对整个数据结构加锁。这样可以使得不同 Segment 之间的操作并行进行，提高了并发性能。

分段锁是可重入的吗

JDK 1.7 ConcurrentHashMap中的分段锁是用了 ReentrantLock，是一个可重入的锁。

已经用了synchronized，为什么还要用CAS呢？

ConcurrentHashMap使用这两种手段来保证线程安全主要是一种权衡的考虑，在某些操作中使用synchronized，还是使用CAS，主要是根据锁竞争程度来判断的。

比如：在putVal中，如果计算出来的hash槽没有存放元素，那么就可以直接使用CAS来进行设置值，这是因为在设置元素的时候，因为hash值经过了各种扰动后，造成hash碰撞的几率较低，那么我们可以预测使用较少的自旋来完成具体的hash落槽操作。

当发生了hash碰撞的时候说明容量不够用了或者已经有大量线程访问了，因此这时候使用synchronized来处理hash碰撞比CAS效率要高，因为发生了hash碰撞大概率来说是线程竞争比较强烈。

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

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

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

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

HashTable 底层实现原理是什么？

img

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

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

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

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

在Java中，可以使用synchronized关键字来标记一个方法或者代码块，当某个线程调用该对象的synchronized方法或者访问synchronized代码块时，这个线程便获得了该对象的锁，其他线程暂时无法访问这个方法，只有等待这个方法执行完毕或者代码块执行完毕，这个线程才会释放该对象的锁，其他线程才能执行这个方法或者代码块。

HashTable和ConcurrentHashMap的区别

  • 底层数据结构：

    • 前者采用数组+链表，数组是主体，链表解决哈希冲突；
    • 后者在JDK7之前采用分段的数组+链表，JDK8之后采用数组+链表/红黑树。

  • 实现线程安全的方式：

    • 前者将所有的方法都加了锁，效率低下，当一个线程访问同步方法，另一个线程也访问时，就会陷入阻塞轮询状态。
    • 后者在JDK8之前采用分段锁，对整个数组进行分段分割，多线程访问不同数据段里的数据，不存在锁竞争，提高了并发访问；JDK8之后采用数组+链表/红黑树，并发控制使用CAS和synchronized操作，更加提高了速度。

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

Set集合的特点

元素唯一，不会出现重复的元素

Set集合如何实现Key无重复的

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

有序的Set是什么

TreeSet和LinkedHashSet。

前者基于红黑树实现，保证元素的自然顺序；后者基于双重链表和哈希表的结合来实现元素的有序存储，保证元素添加的自然顺序。

记录插入顺序的集合是什么

通常指LinkedHashSet，不仅保证元素的唯一性，还可以保持元素的插入顺序。当需要在Set集合中记录元素的插入顺序时，可以选择使用LinkedHashSet来实现。