对 java 的集合类做一些整理，方便实际开发的时候选取合适的数据结构。

ArrayList

内部包含一个数组用以放置元素，有一个整数值表示当前数组的实际大小。

  • 比较元素，采用元素的 equals() 方法。

  • 查找元素，直接访问数组的下标即可。

  • 插入元素，需要先计算数组大小是否足够，如果容量不够，扩张为原来的 1.5 倍，插入元素之后，需要进行 System.arrayCopy() 操作复制后面部分的操作。

  • 删除元素，直接将目标位置的引用指向 null，删除元素之后，再进行 System.arrayCopy() 操作复制后面部分的数组。

  • 容量控制，使用 ensureCapacity(int min) 方法指定一个比较合适的初始大小， 降低内部数据扩张的可能性。

  • 容量调整，使用 trimToSize() 方法，重新分配一个当前 size 的数组空间。

LinkedList

除了实现 List 接口之外，还实现了双端队列接口 Deque 可以当做先进先出的队列使用，也可以当做先进后出的栈使用，方便对头部和尾部的元素做各种操作。

内部包含一个链表，每一个元素都持有上一个元素pre和下一个元素next的引用。

  • 比较元素，采用元素的 equals() 方法。

  • 查找元素，根据传入的下标，先判断是靠近头部还是尾部，从头部或者尾部开始查找。

  • 插入元素，找到指定的位置，将 pre 的 next 指向要插入的元素，将元素的 next 指向原本 pre 的 next。

  • 删除元素，找到指定的元素 target，将 target->pre->next 指向 target->next 。

  • 容量，因为是采用链表的结构存储，所以没有对容量的控制。

HashMap

HashMap 实现了 Map 接口，Map 是一种 key-value 映射的数据结构。

内部的 Entry 也实现了 Map.Entry 接口，包含了 key-value 键值对，以及指向下一个元素的 next，和 HashMap 的关键部分，hash

HashMap 内部维护了一个元素为 Entry 数组，数组的每一个元素都指向一个单向链表，在 JDK8 中，这个链表在长度超过 8 的时候会转换成 红黑树，以提高查找，插入，删除元素的效率。

容量扩展

HashMap 和 ArrayList 一样，也有扩展数组大小的机制，但是这个扩展的触发条件和扩展的倍数都不同于 ArrayList。

触发扩展的时机由 capacity 和 loadFactor 决定。HashMap 默认的 capacity 是 16，默认的 loadFactor 是 0.75，当数组大小到了 16 * 0.75 = 12 的时候，就会触发扩展，这两个值可以在构造函数中进行指定。

添加元素

计算 key 的 hash，根据 hash 找到应该存储在哪一个链表中，再插入这个链表中，如果 key 已经存在，更新已有的 value。

然后计算是否需要扩展数组的大小。

根据 key 计算 hash 算法会尽量使得结果均匀分配到每一个位置，以提高查找的效率。

查找元素

计算传入的 key 得出 hash，根据 hash 找到数组中的对应的链表。

在链表中遍历比较，先通过 hash 进行比较，因为 hash 是整型值，比较的效率会高于 equals 方法，当 hash 一样的时候，再通过 equals 进行比较。

由于 hash 算法的设计，使得每一个链表中的元素数量都比较少，所以 HashMap 的查找效率会比较高。

检查是否包含 key value

根据 key 查找元素，结果为空则不包含这个 key。

检查 value 则需要通过遍历来检查。

根据 key 删除 value

计算传入的 key 得到 hash，根据 hash 找到数组中对应的链表。

在链表中遍历比较，先通过 hash 进行比较，hash 相同的时候，再通过 equals 方法进行比较。找到元素之后，采用链表中删除元素的方法，删除元素。

HashSet

HashSet 实现的是 Set 接口，称为集合，集合中的元素不重复。

内部持有一个 HashMap 的引用，这个 HashMap 的 key-value 中，value 是一个固定的对象。

添加，删除，查找等操作都是对内部 HashMap 的添加，删除，查找等操作。

HashMap 中，key 并不重复，所以 HashSet 可以做到内部的元素不重复。

TreeMap

TreeMap 是有序的 Map，排序是根据 key 来排序的。在构造方法中可以传入一个 Comparator 接口对象，这个接口决定了 key 的排序方式，如果不传入这个接口对象，那么这个 Map 的 key 应该实现 Comparator 接口。

其他接口

TreeMap 实现了 SortedMap 接口和 NavigableMap 接口。

SortedMap 返回一部分的键值对，类似于 Python 中的切片操作，比如大于某个键，小于某个键，或者是在两个键的区间范围的键值对。

NavigableMap 根据给出的键查找邻近的键，或者邻近的键值对使用。

添加元素

添加元素，当添加元素的时候，如果 key 的比较结果相同，则认为是相同的元素，对应的 value 只会保存最后一次添加的 value。

内部实现

TreeMap 内部使用红黑树存储键值对，红黑树是一种大致上平衡的二叉树。（红黑树）

红黑树在每次添加元素之后，会进行平衡程度的调整，但是不会每一次都调整为绝对的平衡，（调整为绝对的平衡是 AVL 树），因为旋转调整也会消耗性能，但是在很大程度上保证了查找元素的效率和添加删除元素的效率。

TreeSet

和 TreeMap 相对于 HashMap 一样，相对 HashSet，TreeSet 是有序的 HashSet。

和 TreeMap 一样，TreeSet，要求提供一个 Comparator 接口对象用来做比较，或者传入的元素自身实现了 Comparator 接口。

添加元素

Set 的元素不重复，也就是说，添加比较结果相同的元素，会保存第一个元素。

其他接口

与 TreeMap 类似，TreeSet 实现了 SortedSet 接口，返回一些切片操作后的结果。

同样，TreeSet 实现了 NavigableSet 接口，传入一个元素，查找邻近的元素。

内部实现

和 HashMap-HashSet 的关系一样，TreeSet 基于 TreeMap 实现，所以有比较高的查找，删除，添加的效率。