Set接口

回到主页
  1. 无序(添加和取出顺序不一致)， 没有索引，但取出的顺序是固定的
  2. 不允许重复元素，最多包含一个null

Set接口常用方法

与List接口一样，Set也是Collection的子接口，常用方法同Collection

Set接口遍历方式

同Collection

  1. 可使用迭代器
  2. 增强for
  3. 不能使用索引的方式获取

HashSet

  1. HashSet实现了Set接口
  2. HashSet实际上是HashMap
  3. 可以存放null，但只能有一个null
  4. HashSet不保证元素是有序的，取决于hash后，再确定索引的结果
  5. 不能有重复元素/对象

HashSet底层机制

  1. HashMap底层是HashMap，HashMap底层是(数组+链表+红黑树)
  2. 添加一个元素时，先得到hash值(hash(key),通过对key求hashcode及更多操作得到hash值)，会转成->索引值
  3. 找到存储数据表table，看这个索引位置是否已经存放有元素
  4. 没有就直接加入
  5. 有，调研equals比较，如果相同就放弃添加，不相同就添加到已有元素table的尾巴上
  6. HashSet第一次添加，table扩容会扩容到16，临界值(threshold)是16*加载因子(localFactor)是0.75 = 12
  7. 如果HashSet的总size(每加入一个node，size就会自增，不只是table大小)到了临界值12，table就会扩容到162 = 32，新的临界值就是320.74 = 24，以此类推。
  8. Java8中，如果一条链表元素个数到了TREEIFY_THRESHOLD(默认为8)，并且table大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化(红黑树)，否则仍然采用数组扩容机制。

假设此时table大小<64,且有一条链表的元素个数到了8以后，往此链表上再添加元素时，不会直接树化，而是将table扩容一倍，以此类推，直到table大小>=64时，再往此链表添加元素时，就会发生树化。

LinkedHashSet

  1. LinkedHashSet是HashSet的子类
  2. LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组+双向链表
  3. LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，这时的元素看起来是以插入顺序保存的
  4. LinkedHashSet不允许添加重复元素

LinkedHashSet说明

alt text

  1. LinkedHashSet中维护了一个hash表和双向链表(LinkedHashSet有head和tail)
  2. 每一个节点有before和after属性，形成双向链表
  3. 在添加一个元素时，先求hash值，再求索引，确定该元素再hashtable的位置，然后将添加的元素加入到双向链表(如果已经存在，不添加[同hashset])
    tail.after = newElement;//简单指定
newElement.before = tail;
tail = newElement;
  4. 这样的话，我们遍历LinkedHashSet也能确保插入顺序和遍历顺序一致。

LinkedHashSet细节

  1. LinkedHashSet 加入顺序和取出元素/数据的顺序一致
  2. LinkedHashSet底层维护的是一个LinkedHashMap(是HashMap的子类)
  3. LinkedHashSet底层结构(数组table + 双向链表)
  4. 添加第一次时，直接将数组table扩容到16， 存放的节点类型是 LinkedHashMap<span data-formula="Entry
  5. 数组是 HashMap" aria-hidden="true">Node[] ，存放的元素/数据是 LinkedHashMap<span data-formula="Entry 类型" aria-hidden="true">Entry 类型

本文章使用limfx的vscode插件快速发布