Collection中Set家族:

Collection集合体系全景图（三）

Set调集的特色

  1. 无序性：Set调集中的元素没有次序，即无法经过下标或索引来访问元素。
  2. 仅有性：Set调集中的元素是仅有的，即不允许重复元素存在。
  3. 不行变性：Set调集中的元素一旦被增加到调集中，就不能被修正，只能被删去。
  4. 灵活性：Set调集本身是可变的，即能够增加、删去元素。
  5. 调集运算：Set调集支撑调集运算，如并集、交集、差集等操作。
  6. 高效性：Set调集的查找、增加、删去等操作都是高效的，时刻杂乱度为O(1)。

Set调集的完成类

Java中供给了多种Set调集的完成类，如HashSet、TreeSet、LinkedHashSet等，需求了解它们的特色、运用场景和差异。

HashSet特色

  1. 无序性：HashSet中的元素没有次序，即不能确保元素的次序与增加次序相同。
  2. 仅有性：HashSet中的元素是仅有的，即不能有重复元素。
  3. 高效性：HashSet的查找、刺进、删去操作都具有很高的功率，时刻杂乱度为O(1)。
  4. 底层完成：HashSet的底层完成是依据HashMap完成的，即便用了HashMap的键值对存储办法，可是HashSet只存储键，不存储值。(HashMap是依据哈希表完成的一个Map接口的完成类)
  5. 线程不安全：HashSet对错线程安全的，假如多个线程一起访问HashSet，可能会导致数据不一致的问题。假如需求在多线程环境下运用HashSet，能够运用Collections.synchronizedSet()办法将HashSet转换为线程安全的Set。

为什么HashSet中的元素没有次序，也不能重复

HashSet中的元素没有次序是因为它是依据哈希表完成的，哈希表是一种无序的数据结构。在哈希表中，元素的存储方位是依据它们的哈希值核算得出的，而不是依照它们的刺进次序或许其他次序来存储的。因而，HashSet中的元素没有次序。

HashSet中不能重复的原因是因为它是依据哈希表完成的，哈希表中每个元素都有一个仅有的哈希值。当咱们向HashSet中增加元素时，它会先核算元素的哈希值，然后依据哈希值来判别该元素是否现已存在于HashSet中。假如现已存在，则不会再次增加，确保了HashSet中元素的仅有性。

什么是哈希表

哈希表是一种数据结构，用于存储和查找数据。

具体来说，哈希表将每个数据元素经过哈希函数核算得到一个哈希值，然后将该值作为数组下标，将数据存储在对应的数组方位上。当需求查找数据时，只需求经过哈希函数核算出该数据的哈希值，然后在数组中查找对应方位上的数据即可。哈希表的长处是查找速度快，但缺陷是可能会呈现哈希抵触，即不同的数据元素核算得到的哈希值相同，需求运用特定的处理抵触办法来处理。

哈希表类似于字典或许电话簿，它能够经过一个关键字（比方名字或许电话号码）快速地查找到对应的值（比方地址或许其他联系办法）。在哈希表中，关键字被映射到一个固定的方位，这个方位便是哈希表中的索引

HashSet运用场景

  1. 去重：HashSet能够用来去除重复的元素，因为它只会保存不重复的元素。
  2. 查找：HashSet能够用来快速查找某个元素是否存在于调集中，因为它的查找时刻杂乱度是O(1)。
  3. 缓存：HashSet能够用来作为缓存，因为它能够快速地判别某个元素是否现已存在于缓存中。
  4. 调集运算：HashSet能够用来进行调集运算，如求交集（中共同存在）、并集（一切元素组成）、差集（一个调集中去掉另一个调集中的元素所得到的调集）等。
  5. 数据存储：HashSet能够用来存储数据，因为它能够快速地刺进、删去、查找元素。

TreeSet特色

  1. 有序性：TreeSet中的元素是有序的，它们依照自然次序或许指定的比较器次序进行排序。
  2. 仅有性：TreeSet中的元素是仅有的，它们不会重复。
  3. 可排序性：TreeSet中的元素能够依照自然次序或许指定的比较器次序进行排序。
  4. 底层数据结构：TreeSet底层选用红黑树完成，因而刺进、删去、查找等操作的时刻杂乱度为O(log n)。
  5. 线程不安全：TreeSet不是线程安全的，假如多个线程一起访问一个TreeSet对象，可能会呈现并发问题。
  6. 不允许空元素：TreeSet不允许刺进空元素，否则会抛出NullPointerException异常。

为什么TreeSet中的元素是有序的，而且不能重复

因为它是依据红黑树完成的。红黑树是一种自平衡二叉查找树，它能够确保在刺进、删去元素时，树的高度一直保持在log(n)级别，然后确保了查找、刺进、删去等操作的时刻杂乱度都是O(logn)

O(logn) 是一种时刻杂乱度的表明办法，表明算法的运行时刻与输入规划 n 的对数成正比。也便是说，当输入规划 n 增加时，算法的运行时刻不会呈线性增加，而是以对数的办法增加。

举个例子，假设有一个有序数组，咱们想要在其间查找一个元素。假如咱们运用线性查找，需求遍历整个数组，时刻杂乱度为 O(n)。可是假如咱们运用二分查找，每次能够将查找规模缩小一半，时刻杂乱度便是 O(logn)

什么是红黑树

Collection集合体系全景图（三）

特色

  1. 每个节点要么是赤色，要么是黑色。
  2. 根节点是黑色的。
  3. 每个叶子节点（NIL节点，空节点）是黑色的。
  4. 假如一个节点是赤色的，则它的两个子节点都是黑色的。
  5. 对于每个节点，从该节点到其一切后代叶子节点的简略途径上，均包含相同数目的黑色节点。

缺陷

  1. 完成杂乱：红黑树的完成比较杂乱，需求考虑多种情况，包含旋转、色彩改换等操作，简单犯错。
  2. 空间占用较大：红黑树需求保护额定的色彩信息，因而比较于其他平衡树，它的空间占用较大。
  3. 不适合频频刺进删去操作：尽管红黑树的刺进和删去操作的时刻杂乱度都是O(log n)，可是因为需求保护平衡，每次刺进和删去操作都需求进行旋转和色彩改换，因而比较于其他数据结构，它不太适合频频进行刺进和删去操作。
  4. 不支撑高效的区间查询：红黑树尽管支撑快速的查找、刺进和删去操作，可是不支撑高效的区间查询操作，需求遍历整棵树来查找符合条件的节点，时刻杂乱度为O(n)。

TreeSet运用场景

  1. 需求对元素进行排序的场景：TreeSet内部选用红黑树完成，能够自动对元素进行排序，因而适用于需求对元素进行排序的场景。
  2. 需求去重的场景：TreeSet内部选用红黑树完成，能够自动去重，因而适用于需求去重的场景。
  3. 需求快速查找元素的场景：TreeSet内部选用红黑树完成，能够快速查找元素，因而适用于需求快速查找元素的场景。
  4. 需求依照规模查找元素的场景：TreeSet供给了一系列的办法，能够依照规模查找元素，例如：headSet、tailSet、subSet等办法，因而适用于需求依照规模查找元素的场景。
  5. 需求对元素进行高档操作的场景：TreeSet供给了一系列的办法，能够对元素进行高档操作，例如：first、last、ceiling、floor等办法，因而适用于需求对元素进行高档操作的场景。

LinkedHashSet特色

  1. 有序性：LinkedHashSet中的元素是依照刺进次序进行排序的，因而能够确保元素的次序性。
  2. 能够避免重复元素：LinkedHashSet中不允许存储重复元素，假如尝试增加重复元素，将会被忽略。
  3. 功能较好：LinkedHashSet的功能与HashSet相当，可是因为需求保护元素的刺进次序，因而在刺进和删去元素时可能会略微慢一些。
  4. 底层完成是HashMap：LinkedHashSet的底层完成是一个HashMap，因而具有HashMap的一切特色，如快速查找、高效存储等。

为什么LinkedHashSet是依照次序进行排序的

LinkedHashSet的底层完成是一个哈希表和一个双向链表。哈希表用于快速查找元素，双向链表用于保护元素的刺进次序。当元素被刺进时，它会被增加到哈希表中，而且在链表的结尾增加一个新节点。当元素被删去时，它会从哈希表中删去，而且从链表中删去相应的节点。

LinkedHashSet的使用场景包含：

  1. 需求保护元素的刺进次序。
  2. 需求快速查找、删去和刺进元素。
  3. 不允许元素重复。
  4. 需求确保元素的次序不变。