集合的分类

Java中的集合类主要分为两大类: Collection接口（单列集合）和Map接口（双列集合）；前者是存储对象的集合类，后者存储的是键值对(key-value)的集合类

Collection接口下又分为List、Set和Queue接口，每个接口有其具体实现类， Map接口下有很多接口，比如HashMap，LinkedHashMap， TreeMap， Hashtable， ConcurrentHashMap

  • List下有ArrayList (基于动态数组，查询速度快，插入、删除慢) ， LinkedList (基于双向链表，插入、删除快，查询速度慢) ;
  • Set下有HashSet (基于哈希表，元素无序，不允许重复) ， LinkedHashSet (基于链表和哈希表，维护插入顺序，不允许重复) ，TreeSet (基于红黑树，元素有序，不允许重复) ;

Map 接口：存储的是键值对，也就是给对象（value）设置了一个 key，这样通过 key 可以找到那个 value。

  • HashMap：基于哈希表，键值对无序，不允许键重复。LinkedHashMap：基于链表和哈希表，维护插入顺序，不允许键重复。
  • TreeMap：基于红黑树，键值对有序，不允许键重复。

线程安全

以上描述的集合类都是线程不安全的。

HashMap

在jdk1.8中

  1. HashMap底层是数组+链表或红黑树的结构，加载因子为0.75

  2. 向HashMap中用put()方法添加一个元素时，通过元素key的哈希值运算得到一个table表的索引

  3. 查着索引处是否有元素

    1. 没有，则直接添加
    2. 有，则判断该位置的元素和要加入的元素的key的内容是否相同
      1. 相同：替换value
      2. 不同：需要判断是树结构还是链表结构，做出相应处理
        1. key值不同，红黑树进行添加元素操作
        2. key值不同，链表进行尾添加，判断当前链表个数是否超过8，再判断table大小是否>=64。是，则转变为红黑树，否则扩容table表。

  4. 第一次添加table容量为16，临界值为12（16*0.75）

  5. 再扩容，table容量为32，临界值为24

ArrayList 和 Array 有什么区别？ArrayList 和 LinkedList 的区别是什么？

  • ArrayList vs Array：
  1. ArrayList是动态数组的实现，而Array 是固定长度的数组。在随机访问时，Array由于其连续内存存储，性能通常优于ArrayList。
  2. ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer） 。Array 可以直接存储基本类型数据，也可以存储对象。
  3. ArrayList 提供了更多的功能，比如自动扩容、增加和删除元素等，Array则没有这些功能。
  • ArrayList vs LinkedList：
  1. ArrayList基于动态数组，LinkedList 基于双向链表。在ArrayList末尾添加元素通常很快，但在ArrayList中间或开始插入或删除元素时，可能需要移动后续元素，时间复杂度为 O(n)。而LinkedList添加和删除元素时性能更佳, 只需改变节点的引用。
  2. 随机访问：ArrayList在随机访问时性能更好，而LinkedList访问元素时效率较低，因为需要从头开始或从尾开始通过链接遍历，时间复杂度为 O(n)。
  3. 容量：当容量不足以容纳更多元素时，ArrayList 会扩容，这个过程涉及创建新数组和复制旧数组的内容，有一定的开销。
  4. 使用场景：选择 ArrayList 或者 LinkedList 通常取决于你的 Java 应用是否需要频繁的随机访问操作，还是更多的插入和删除操作。

​ 总结来说，ArrayList和Array的主要区别在于动态大小和功能，而ArrayList和LinkedList的主要区别在于底层数据结构和它们对元素操作的性能特点。选择使用哪一个取决于具体的应用场景和性能需求。

ArrayList的扩容机制

​ ArrayList扩容的本质就是计算出新的扩容数组的size 后实例化，并将原有数组内容复制到新数组中去。

  1. 当创建一个ArrayList集合时，它会分配一定的初始容量，通常为10。这是为了节省内存，因为并不是所有的ArrayList都需要大量的空间。
  2. 需要扩容时，会调用grow()方法， 该方法先尝试将数组扩大为原数组的1.5倍。（默认新容量=旧容量右移一位（相当于除于2）在加上旧容量）
  3. 若新的容量满足需求，会调用一个Arrays.copyof 方法, 将所有的元素从旧数组复制到新数组中。如果扩容后的新容量还是不满足需求，那新容量大小为当前所需的容量加 1。

红黑树

红黑树的特点

解决Hash冲突的方法有哪些？HashMap 是如何解决 hash 冲突的

哈希冲突

​ 当两个不同的数经过哈希函数计算后得到了同一个结果，即他们会被映射到哈希表的同一个位置时，该现象称为发生了哈希冲突。

解决方法

解决哈希冲突的方法主要有以下两种：

  1. 链地址法：在数组的每个位置维护一个链表。当发生冲突时，新的元素会被添加到链表的尾部。
  2. 开放寻址法：当发生冲突时，根据某种探测算法在哈希表中寻找下一个空闲位置来存储元素。

Java中的 HashMap使用链地址法解决hash冲突。

HashMap 为什么是线程不安全的? 如何实现线程安全

为什么是线程不安全的

​ HashMap是线程不安全的。因为HashMap的内部实现并没有加锁，多个线程同时访问和修改时可能会引发数据竞争，造成数据不一致或陷入死循环等问题。

如何实现线程安全

为了实现线程安全的 HashMap，有以下两种方式：

  • 使用Collections.synchronizedMap()方法：这种方法通过在 HashMap的方法上加synchronized锁实现线程安全。不过，这种方式对整个Map加锁，会导致较高的锁竞争和性能开销，尤其是在高并发情况下。
1
Map<String, String> synchronizedMap = Collections.synchronizedMap(new HashMap<>());
  • 使用ConcurrentHashMap：ConcurrentHashMap 是专门设计用于多线程环境的哈希表实现。它使用分段锁机制，允许多个线程同时进行读操作，提高并发性能。

concurrentHashMap 如何保证线程安全

​ ConcurrentHashMap 在HashMap的基础上，通过 CAS 或者 synchronized 来保证线程安全的，并且缩小了锁的粒度，查询性能也更高。

HashMap和ConcurrentHashMap的区别

线程安全性：

  • HashMap 是线程不安全的。在多线程环境中，如果同时进行读写操作，可能会导致数据不一致或抛出异常。如果要实现线程安全，可以通过使用 Collections.synchronizedMap() 方法对整个map上锁。
  • ConcurrentHashMap 是线程安全的，它使用了分段锁（Segment Locking）的机制，将整个数据结构分成多个段（Segment），每个段都有自己的锁。这样，不同的线程可以同时访问不同的段，提高并发性能。

初始化容量和负载因子：

  • HashMap 可以通过构造方法设置初始容量和负载因子。
  • ConcurrentHashMap 在Java 8及之后版本中引入了ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)构造方法，允许设置初始容量、负载因子和并发级别。

性能：

  • 在低并发情况下，HashMap 的性能可能会比 ConcurrentHashMap 稍好，因为 ConcurrentHashMap 需要维护额外的并发控制。
  • 在高并发情况下，ConcurrentHashMap 的性能通常更好，因为它能够更有效地支持并发访问。

​ 总的来说，如果需要在多线程环境中使用哈希表，而且需要高性能的并发访问，通常会选择使用 ConcurrentHashMap。如果在单线程环境中使用，或者能够手动进行外部同步管理，那么 HashMap 可能是更简单的选择。

HashMap 和 HashSet 的区别

不同点：

​ HashMap 适用于需要存储键值对的情况，而 HashSet 适用于只关心元素唯一性的情况。在某些情况下，可以使用 HashMap 来模拟 HashSet 的行为，只使用键而将值设为固定的常量。

相同点：

​ 两者都允许所存对象为null，并且使用迭代器或增强型 for 循环遍历。

HashMap 和 HashTable 的区别

重点为前四点

空值

  • HashMap 允许键和值都为 null。
  • Hashtable 不允许键或值为 null。

线程安全

  • HashMap 不保证在多线程环境中的线程安全性。如果需要同步，可以使用 Collections.synchronizedMap() 方法来创建一个同步的 HashMap。
  • Hashtable 它的方法是线程安全的。这是通过在每个方法上添加同步关键字来实现的，但这也可能导致性能下降。

初始容量和加载因子

  • HashMap 允许通过构造方法设置初始容量和加载因子，以便更好地调整性能。
  • Hashtable 的初始容量和加载因子是固定的。

性能

  • HashMap 在多线程环境中可能比 Hashtable 更快，因为它没有同步开销。
  • 由于 Hashtable 是同步的，它在多线程环境中的性能可能较差。

继承关系

Hashtable 是 Dictionary 类的子类，而 HashMap 是 AbstractMap 类的子类，实现了 Map 接口。

迭代器

  • HashMap 的迭代器是通过 Iterator 实现的。
  • Hashtable 的迭代器是通过 Enumerator 实现的。