Java的集合有哪些？

Java 的集合框架提供了一组用于存储和操作对象的类和接口。这些集合类按照它们的功能和特性大致可以分为以下几个主要类别：

Collection Interface

  • Collection<E>: 所有单列集合类的顶级接口。

  • List: 有序集合，允许重复元素。

    • ArrayList: 动态数组实现。

    • LinkedList: 双向链表实现。

    • Vector: 线程安全的 ArrayList。

    • Stack: 基于 Vector 实现的后进先出 (LIFO) 集合。

  • Set: 无序集合，不允许重复元素。

    • HashSet: 基于 HashMap 实现。

    • LinkedHashSet: 保持元素插入顺序的 HashSet。

    • TreeSet: 基于 TreeMap 实现，元素按自然顺序或自定义顺序排序。

    • EnumSet: 专门用于 enum 类型的高效集合。

  • Queue: 用于存储元素的先进先出 (FIFO) 集合。

    • ArrayDeque: 基于数组的双端队列。

    • LinkedList: 也可以用作队列。

    • PriorityQueue: 基于优先级堆实现，元素按优先级排序。

Java容器都有哪些？

Java容器主要包括以下几大类：

  • Collection: 包括List、Set等。

  • Map: 包括HashMap、TreeMap等。

  • Queue: 包括ArrayDeque、PriorityQueue等。

List、Set、Map之间的区别是什么？

  • List: 有序的集合，允许重复元素。

  • Set: 不允许重复元素的集合，无序。

  • Map: 存储键值对映射，键不允许重复。

HashMap和Hashtable有什么区别？

  • 线程安全性:Hashtable是线程安全的，HashMap不是。

  • null值/键:Hashtable不允许键或值为null，而HashMap允许一个null键和多个null值。

  • 性能:HashMap通常比Hashtable快，因为Hashtable需要进行同步处理。

Hashtable 是线程安全的，主要是因为它在其关键方法上使用了同步机制。具体来说，Hashtable 中的大部分方法都是同步的，这意味着在这些方法执行期间，多个线程不能同时访问这些方法。下面是 Hashtable 线程安全的一些关键点：

  1. 同步方法:

    • Hashtable 中的关键方法，如 put(), get(), remove(), containsKey(), containsValue() 等，都是同步的。这意味着当一个线程正在执行这些方法时，其他线程必须等待该方法执行完毕才能继续执行。

  2. 同步块:

    • Hashtable 中的一些方法使用了同步块来保护内部数据结构，确保在这些方法执行期间数据的一致性。

  3. 内部同步:

    • Hashtable 的实现中，它使用了内部的同步机制来保护数据结构，例如在插入或删除元素时，它会锁定整个数据结构，以防止其他线程同时对其进行修改。

这里是一个简化的示例，展示了 Hashtable 中一个同步方法的实现方式：

public synchronized V put(K key, V value) {
    // 实现细节
}

在这个例子中，put() 方法被声明为 synchronized，这意味着在任何时候只有一个线程可以调用该方法。如果多个线程试图同时调用 put() 方法，它们将被阻塞，直到当前执行的线程完成方法调用。

说一下HashMap的实现原理？

HashMap使用哈希表实现，内部维护了一个数组，数组中的每个元素都是一个链表或者红黑树节点。当插入一个元素时，根据键的哈希值计算出数组索引，然后将元素添加到对应位置的链表或红黑树中。当数组负载因子超过阈值时，会进行扩容。

HashMap 是如何实现扩容的
下面是 HashMap 扩容的基本步骤和实现细节：

  1. 初始容量与负载因子:

    • HashMap 在创建时可以指定初始容量（默认为16）和负载因子（默认为0.75）。

    • 初始容量必须为2的幂，以保证哈希算法的性能。

    • 负载因子决定了何时进行扩容，当元素数量超过 capacity * loadFactor 时触发扩容。

  2. 扩容时机:

    • 当 HashMap 中的元素数量达到或超过了 threshold （capacity * loadFactor）时，会触发扩容操作。

    • threshold 是一个变量，用于跟踪何时需要进行扩容。

  3. 扩容过程:

    • 扩容时，HashMap 会创建一个新的更大的数组，通常是当前数组大小的两倍。

    • 然后，原有的所有元素都会被重新计算哈希值，并重新插入到新的数组中。

    • 这个过程称为“再哈希”（rehashing），它会根据新的数组大小重新计算每个元素的位置。

  4. 再哈希:

    • 再哈希时，HashMap 遍历旧数组中的每一个元素。

    • 对于每个元素，HashMap 会重新计算其哈希值，并根据新的数组大小确定其新的位置。

    • 如果新的数组大小是旧数组大小的两倍，那么哈希值的计算会考虑到这一点，以确保元素正确放置在新数组中。

    • 如果使用的是链表结构，链表会被重新插入到新数组中。

    • 如果使用的是红黑树结构，树也会被重新插入到新数组中。

  5. 红黑树优化:

    • 从 Java 8 开始，HashMap 在某些情况下使用红黑树来替代链表，以减少链表的长度，提高查找性能。

    • 当链表中的节点数量超过一定阈值（默认为8），并且数组的容量大于等于64时，链表会被转换为红黑树。

    • 在扩容过程中，如果原来的链表或红黑树被拆分到了新的位置，它们也会被重新转换为链表或红黑树。

  6. 更新阈值:

    • 扩容完成后，新的 threshold 值会被计算出来，以便下次触发扩容。

    • 新的 threshold 值等于新的数组容量乘以负载因子。

哈希表

哈希表是一种使用哈希函数将键映射到表中的索引位置的数据结构。它提供了一种高效的方法来插入、查找和删除键值对。哈希表的平均时间复杂度为 O(1)，这使得它成为非常高效的查找结构。

哈希表的基本组成部分包括：

  • 哈希函数：将键映射到哈希表中的索引位置。

  • 哈希表：一个数组，用于存储键值对。

  • 冲突解决策略：处理多个键映射到同一索引位置的问题。

哈希函数

哈希函数是一个从键（通常是字符串或其他数据类型）到整数索引的映射函数。理想情况下，哈希函数应该均匀地分布键，以最小化哈希冲突。一个好的哈希函数具有以下特点：

  • 均匀性：哈希函数应该尽可能均匀地分布哈希值。

  • 简单性：哈希函数应该足够简单，以便快速计算。

  • 确定性：对于相同的输入，哈希函数应该始终产生相同的结果。

常见的哈希函数包括：

  • 除留余数法：取键的值模以哈希表的大小。

  • 折叠法：将键分成几个部分，然后将这些部分相加或连接起来。

  • 中间平方法：将键的平方结果的中间部分作为哈希值。

  • 位操作：通过对键进行位移或异或等操作生成哈希值。

  • 随机数法：使用随机数生成哈希值。

  • CRC32 或 MD5 等哈希算法：这些算法通常用于较大数据的哈希。

哈希冲突

哈希冲突是指两个或多个不同的键通过哈希函数映射到了同一个索引位置。这是不可避免的，因为哈希表的大小通常是有限的，而可能的键值却是无限的。处理哈希冲突的常见策略包括：

  1. 开放寻址法（Open Addressing）：

    • 线性探测：如果哈希位置被占用，则尝试下一个位置。

    • 二次探测：使用二次方程式来确定下一个探测位置。

    • 双重散列：使用第二个哈希函数来确定步长。

  2. 链地址法（Separate Chaining）：

    • 在每个哈希表的索引位置上存储一个链表或平衡树等数据结构，用于存储具有相同哈希值的键值对。

说一下HashSet的实现原理？

HashSet底层使用了HashMap，将元素作为键存储。由于HashMap不允许重复的键，所以HashSet也就实现了不允许重复元素的功能。HashSet中的元素是无序的。

  • HashMap 是一个高性能的键值对映射，不支持线程安全，允许 null 键和值。

  • HashSet 是一个不包含重复元素的集合，底层使用 HashMap 实现，不支持线程安全，允许一个 null 元素。

  • HashTable 是一个线程安全的键值对映射，不允许 null 键或值，性能通常不如 HashMap。

ArrayList和LinkedList的区别是什么？

  • ArrayList: 基于动态数组实现，随机访问速度快，适合频繁查询。

  • LinkedList: 基于双向链表实现，插入删除速度快，适合频繁增删。

如何实现数组和List之间的转换？

  • 数组转List: 使用Arrays.asList(T...)。

  • List转数组: 使用List.toArray(T[])。

ArrayList和Vector的区别是什么？

  • 线程安全性:Vector是线程安全的，ArrayList不是。

  • 性能:ArrayList通常比Vector快，因为Vector需要进行同步处理。

Array和ArrayList有何区别？

  • Array是固定长度的数据结构，可以存储基本类型或引用类型。

  • ArrayList是可变长度的列表，只支持引用类型。

在Queue中poll()和remove()有什么区别？

  • poll()尝试从队列中获取并移除头部元素，如果队列为空则返回null。

  • remove()同样获取并移除头部元素，但如果队列为空则抛出异常。

哪些集合类是线程安全的？

  • Vector

  • Hashtable

  • ConcurrentHashMap

  • CopyOnWriteArrayList

  • LinkedBlockingQueue

迭代器Iterator是什么？

Iterator是用于遍历集合元素的一个接口。它提供了hasNext()和next()等方法来依次访问集合中的元素。

Iterator怎么使用？有什么特点？

使用iterator()方法从集合中获取Iterator实例，然后通过hasNext()判断是否还有下一个元素，使用next()获取下一个元素。

特点：

  • 可以在遍历过程中移除元素，使用remove()方法。

  • 遍历过程中不能调用集合的add方法。

Iterator和ListIterator有什么区别？

  • ListIterator继承了Iterator，增加了额外的方法，如set()、add()，并且支持双向遍历。

怎么确保一个集合不能被修改？

可以通过Collections.unmodifiableCollection(Collection)方法返回一个不可变视图。例如：

List<String> list = new ArrayList<>();
List<String> unmodifiableList = Collections.unmodifiableList(list);