Java中的集合类

Java中集合类主要分为两大类：Collection接口和Map接口。前者是存储对象的集合类，后者存储的是键值对。

Collection接口下又分为List、Set、Queue接口。每个接口有其具体实现类：

List 接口:

  • ArrayList:基于动态数组,查询速度快,插入、删除慢。
  • LinkedList:基于双向链表,插入、删除快,查询速度慢。
  • Vector:线程安全的动态数组,类似于ArrayList,但开销较大。

Set接口:

  • HashSet:基于哈希表,元素无序,不允许重复。
  • LinkedHashSet:基于链表和哈希表,维护插入顺序,不允许重复。
  • TreeSet:基于红黑树,元素有序,不允许重复。

所以网上有些说Set是无序集合非常不准确,因为需要看具体的实现类。

Queue 接口:

  • PriorityQueue:基于优先级堆,元素按照自然顺序或指定比较器排序。
  • LinkedList:可以作为队列使用,支持FIFO(先进先出)操作。

Map 接口:

存储的是键值对,也就是给对象(value)设置了一个key,这样通过key可以找到那个
value.

  • HashMap:基于哈希表,键值对无序,不允许键重复。
  • LinkedHashMap:基于链表和哈希表,维护插入顺序,不允许键重复。
  • TreeMap:基于红黑树,键值对有序,不允许键重复。
  • Hashtable:线程安全的哈希表,不允许键或值为null。
  • ConcurrentHashMap:线程安全的哈希表,适合高并发环境,不允许键或值为null。

Java中数组和链表的区别

在存储结构方面:

数组基于连续的内存块,大小是固定的,需要重新分配内存来改变数组大小,内存使用紧凑但容易浪费空间。

链表是基于节点的结构,在内存中不需要连续存储,可以动态变化大小和插入删除节点,内存不连续但可以动态扩展。

在访问速度方面:

数组支持O(1)时间的随机访问,可以通过索引直接访问任何元素。

而链表访问特定元素需要线性时间O(n),因为节点在内存中不一定连续,访问效率受限于链表的结构。

在操作方面:

数组插入和删除需要移动数据,时间复杂度为O(n),而链表则很灵活,可在O(1)时间插入和修改指定位置元素。

在适用场景方面:

数组适合需要快速随机访问且大小固定的场景,如实现缓存、表格等数据结构。

链表适合需要频繁插入和删除操作且大小不确定的场景,如队列、栈、链表等

Java中List接口的实现类

List 接口主要包含 ArrayList、LinkedList、Vector、Stack、CopyOnWriteArrayList 几个实现
类。

最常见的就是ArrayList和LinkedList,注意这两者都不是并发容器,所以线程不安全。

ArrayList 是基于动态数组实现的,因此它的特性与数组一致,随机访问很快,删除和插入相对比较慢。

  • 随机访问时间复杂度为O(1)。
  • 插入和删除(除了在列表末尾)时间复杂度为O(n)。

LinkedList 是基于双向链表实现的,因此两端都能操作,特性就是正常的链表特性,两端插入删除很快,但是随机访问需要遍历链表所以比较慢。

  • 随机访问时间复杂度为O(n),需要遍历链表
  • 插入和删除时间复杂度为 O(1)。

Vector：基于动态数组实现,与ArrayList类似,但它是线程安全,所有法都是同步的，加了synchronized这把锁。也因为同步开销大，所以性能相对较低。

CopyOnWriteArrayList：基于动态数组实现,但所有可变操作(如add()、set()等)都会创建一个新的数组。它其实运用了一个叫写时复制的技术,即当写的时候,再去复制。它是线程安全的,适合在多线程环境中频繁读取、很少修改的场景。

AbstractList：一个抽象类,实现了List接口的大部分方法,提供了基本的List功能。如果我们想要扩展实现自己的列表,那么可以用它作为自定义列表实现的基础类,大大减少我们的自定义成本。

Java中HashMap和Hashtable的区别

  1. 线程安全性:
  • HashMap:非线程安全,多线程环境下可能会产生数据不一致问题。
  • Hashtable:线程安全,内部大部分方法都使用了synchronized关键字进行同步,保证了多线程的并发安全性。
  1. 性能差异:

** HashMap:由于没有线程同步开销,因此在单线程环境下性能优于Hashtable。
** Hashtable:由于方法的同步锁机制,性能低于HashMap。由于使用全局锁的方式,使得即使是不同的操作也会被串行化。

  1. 允许空值:
  • HashMap：允许一个null键和多个null值。
  • Hashtable：不允许null键和null值。插入null会抛出空指针异常。
  1. 继承结构：
  • HashMao：继承自AbstractMap，是Map接口的实现类。
  • Hashtable：继承自Dictionary(已废弃)，后来也实现了Map接口。一种较为古老的类，在Java2后逐渐被HashMap代替，不推荐使用。
  1. 迭代器类型：
  • HashMap:使用的是快速失败的Iterator在迭代过程中如果对Map 进行结构性修改,会抛出ConcurrentModificationException。
  • Hashtable: 使用的是弱一致性的Enumerator，虽然也不建议在迭代过程中修改Map,但不会抛出ConcurrentModificationException。

ConcurrentHashMap：
ConcurrentHashMap是Hashtable的替代方案。它在实现线程安全的同时,通过分段锁机制提高了并发性能,避免了全局锁导致的性能瓶颈。适用于高并发环境。
ConcurrentHashMap的读操作无锁化,写操作则使用了局部锁分段,使得在高并发下性能大大优于 Hashtable。

Java中HashSet和HashMap的区别

Hashset：

  • 基于哈希表的存储结构,只存储元素的值。但实际上它是基于hashmap来实现的,其中HashSet的元素作为hashmap的键存储,而所有的值都指向一个同一个特殊值,通常是null;
  • 保证了元素的唯一性,不允许有重复元素。
  • 只能通过元素的值来访问和操作。
  • 存储单一类型的元素。

hashMap：

  • 基于键值对的存储结构,每个元素由一个键和对应的值的组成。
  • 保证键的唯一性,而值可以重复。
  • 可以通过键来快速查找,插入和删除元素。
  • 可以存储键值对,其中键和值可以是不同类型的对象。

共同点:

  • HashSet和hashMap都不是线程安全的。可以考虑使用Collections,synchronized Set/Map
    方法才能转换成线程安全的即可,或者使用ConcurrentHashMap和CopyOnWriteArrayList等并发集合
  • 无序集合。
  • 使用场景前者需要存储单一的元素,且不关心元素顺序。后者需要根据键来查找插入和删除建制对的场景。