集合框架

ArrayList

2020-04-29

Java

集合框架

2024-08-07

ArrayList是Java集合框架中使用最为频繁的实现，其本质是一个有序的可自由扩容的对象数组。它实现了RandomAccess这个标记接口，意味着其在随机访问性能上有一定优势。

...

LinkedList

LinkedList是基于双向链表实现的有序集合，~~其不能像ArrayList一样通过索引(index)访问元素~~，同时LinkedList还实现了Deque接口，意味着LinkedList可以实现双端队列的操作。

...

Queue

Queue（队列），实际开发过程中，~~在单线程环境下~~使用的并不多，Queue作为集合框架中重要组成似乎习惯性被忽略。队列总是先持有元素，再处理元素¹。

Queue继承关系简图

...

Set

Set是不含重复元素的集，严格来讲，Set不允许当e1.equals(e2)为真时， e1 和 e2 同时出现在集合中。Set最多允许一个null元素。

将可变对象置入Set时需要特别小心，当对象的改动影响到了元素之间的equals()比较的结果，那么Set的行为就变得不确定了。因此，不能将Set本身作为Set的元素。

...

HashMap和TreeMap

由于Map的键是Set，因此使用可变对象作为Map的key时，需要覆盖 equals 和 hashCode 方法，Map不能使用自身作为key。

Java 8对Map接口进行了优化，新增了主要是针对函数式接口的默认方法（方法体被省略）：

default V merge (K key, V value,
  BiFunction<? super V, ? super V, ? extends V> remappingFunction) {...}
default V compute (K key,
  BiFunction<? super K, ? super V, ? extends V> remappingFunction) {...}
default V computeIfPresent (K key,
  BiFunction<? super K, ? super V, ? extends V> remappingFunction) {...}
default V computeIfAbsent (K key,
  Function<? super K, ? extends V> mappingFunction) {...}
default V replace (K key, V value) {...}
default boolean replace(K key, V oldValue, V newValue) {...}
default boolean remove (Object key, Object value) {...}
default V putIfAbsent (K key, V value) {...}
default void replaceAll (
  BiFunction<? super K, ? super V, ? extends V> function) {...}
default V getOrDefault (Object key, V defaultValue) {...}

上述方法使用的不多，主要用来对Map键值进行更新，按需查阅API文档。

...

LinkedHashMap

LinkedHashMap(链表散列映射)是HashMap的导出类，像LinkedHashSet与HashSet的关系一样。

其与HashMap的差别在于其使用LinkedList来维护键值对插入的顺序，其插入机制和HashMap是一致的。

LinkedHashMap和HashMap的性能相差不大，与HashSet和LinkedHashSet 一致：

集合	特征
`HashMap`	`HashMap`基于散列表，插入和查询键值对的开销是固定的
`LinkedHashMap`	和`HashMap`类似，不过其使用`LinkedList`维护内部次序，因此其迭代顺序是插入顺序或者LRU（最近最少使用）次序，性能稍差于`HashMap`

...