- 无序(添加和取出顺序不一致), 没有索引,但取出的顺序是固定的
- 不允许重复元素,最多包含一个null
Set接口常用方法
与List接口一样,Set也是Collection的子接口,常用方法同Collection
Set接口遍历方式
同Collection
- 可使用迭代器
- 增强for
- 不能使用索引的方式获取
HashSet
- HashSet实现了Set接口
- HashSet实际上是HashMap
- 可以存放null,但只能有一个null
- HashSet不保证元素是有序的,取决于hash后,再确定索引的结果
- 不能有重复元素/对象
HashSet底层机制
- HashMap底层是HashMap,HashMap底层是(数组+链表+红黑树)
- 添加一个元素时,先得到hash值(hash(key),通过对key求hashcode及更多操作得到hash值),会转成->索引值
- 找到存储数据表table,看这个索引位置是否已经存放有元素
- 没有就直接加入
- 有,调研equals比较,如果相同就放弃添加,不相同就添加到已有元素table的尾巴上
- HashSet第一次添加,table扩容会扩容到16,临界值(threshold)是16*加载因子(localFactor)是0.75 = 12
- 如果HashSet的总size(每加入一个node,size就会自增,不只是table大小)到了临界值12,table就会扩容到162 = 32,新的临界值就是320.74 = 24,以此类推。
- Java8中,如果一条链表元素个数到了TREEIFY_THRESHOLD(默认为8),并且table大小>=MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树),否则仍然采用数组扩容机制。
假设此时table大小<64,且有一条链表的元素个数到了8以后,往此链表上再添加元素时,不会直接树化,而是将table扩容一倍,以此类推,直到table大小>=64时,再往此链表添加元素时,就会发生树化。
LinkedHashSet
- LinkedHashSet是HashSet的子类
- LinkedHashSet底层是一个LinkedHashMap,底层维护了一个数组+双向链表
- LinkedHashSet根据元素的hashCode值来决定元素的存储位置,同时使用链表维护元素的次序,这时的元素看起来是以插入顺序保存的
- LinkedHashSet不允许添加重复元素
LinkedHashSet说明

- LinkedHashSet中维护了一个hash表和双向链表(LinkedHashSet有head和tail)
- 每一个节点有before和after属性,形成双向链表
- 在添加一个元素时,先求hash值,再求索引,确定该元素再hashtable的位置,然后将添加的元素加入到双向链表(如果已经存在,不添加[同hashset])
tail.after = newElement;//简单指定
newElement.before = tail;
tail = newElement;
- 这样的话,我们遍历LinkedHashSet也能确保插入顺序和遍历顺序一致。
LinkedHashSet细节
- LinkedHashSet 加入顺序和取出元素/数据的顺序一致
- LinkedHashSet底层维护的是一个LinkedHashMap(是HashMap的子类)
- LinkedHashSet底层结构(数组table + 双向链表)
- 添加第一次时,直接将数组table扩容到16, 存放的节点类型是 LinkedHashMap<span data-formula="Entry
- 数组是 HashMap" aria-hidden="true">Node[] ,存放的元素/数据是 LinkedHashMap<span data-formula="Entry 类型" aria-hidden="true">Entry 类型
本文章使用limfx的vscode插件快速发布