Set 接口及实现类
Set 接口基本介绍
-
无序(添加和取出顺序不一致),没有索引
-
不允许重复,所以最多包含一个null
-
JDK API 中Set 接口实现类
Set 接口和常用方法
常用方法
和 List 接口一样,Set 接口也是 Collection 的子接口,因此,常用方法和 Collection 接口一样
Set 接口的遍历方式
同 Collection 接口的遍历方式一样,因为 Set 接口是 Collection 接口的子接口
- 使用迭代器
- 增强for
- 不能使用索引的方式来遍历
Set 接口的实现类 —— HashSet
-
HashSet 实现了 Set 接口
-
HashSet 实际上是 HashMap
public HashSet() { map = new HashMap<>(); }
-
可以存放 null 值,但只能有一个
-
HashSet 不保证元素是有序的,顺序取决于 hash 后,再确定索引的结果
-
不能有重复元素
HashSet 底层机制说明☆
-
HashSet 的底层是 HashMap,HashMap 的底层是 数组 + 链表 + 红黑树
-
Java中 HashMap 是利用“拉链法”处理 hashcode 的碰撞问题
-
先获取元素的哈希值(
hashCode()
方法) -
对哈希值进行运算,得出一个索引值即为要存放在哈希表中的位置号
-
找到存储数据表
table
,如果该位置上没有其他元素,则直接存放如果该位置上已经有有其他元素,则要进行
equals()
方法判断,如果相等,则不再添加,如果不相等,则以链表的方式添加 -
在Java 8 中,如果一条链表的元素个数超过
TREEIFY_THRESHOLD
(默认为8),并且table
的大小 >=MIN_TREEIFY_CAPACITY
(默认为64)就会进行树化(红黑树)
public class HashSetSource {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
}
}
-
public HashSet() { map = new HashMap<>(); }
-
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
-
hashSet.add("java");
-
public boolean add(E e) { return map.put(e, PRESENT)==null; // Dummy value to associate with an Object in the backing Map 与后置映射中的对象关联的虚拟值 // private static final Object PRESENT = new Object(); }
-
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
-
-
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
-
-
-
-
public int hashCode() { // 调用了该对象(这里是String)的hashCode()方法 int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }
-
-
-
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) // table 是 HashMap 的数组,类型是 Node[] // table 为null 或者 大小=0,第一次扩容到16 n = (tab = resize()).length; // 根据key,得到hash,去计算该key应该存放在 table 的哪个索引位置 // 并把这个位置的对象,赋给p // 判断p是否为null,表示还没有存放元素,就创建一个 Node(key = "java", value=PRESENT) if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 开发技巧,在需要局部变量(辅助变量)的时候,再创建 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 如果当前索引位置对应的链表第一个元素和准备添加的key的hash值一样,并且 //(1)准备加入的key 和 p 指向的Node 结点的 key 是同一个对象 // (2) p指向的Node 结点的 key 的euqals() 和准备加入的 可以比较后相同 e = p; else if (p instanceof TreeNode) // 判断p是不是一棵红黑树 // 如果是一颗红黑树,就调用putTreeVal()进行添加 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 如果table对应的索引位置,已经是一个链表,就使用for循环比较 // (1)一次和该链表的每一个元素比较后,都不相同,则加入到该链表的对吼 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // binCount >= 8 - 1 链表长度等于8 treeifyBin(tab, hash); // 树化 // 该函数里面进行判断是 table 扩容还是树化 // if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // <64 resize() // 扩容 // else if 树化 break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) // 当前为 16 * 0.75 = 12 resize(); // 扩容 afterNodeInsertion(evict); // 空方法,HashMap留给子类去实现的方法 return null; }
-
-
扩容和转成红黑树的机制☆☆
-
HashSet 底层是HashMap,第一次添加时,table 数组扩容到 16,临界值(threshold)= 16 * 加载因子(LoadFactor =0.75)= 12
-
如果 table 数组到达临界值 12,就扩容到 16 * 2 = 32,新的临界值就是 32 * 0.75 = 24,以此类推
-
在Java 8 中,如果一条链表的元素个数到达 TREEIFY_THRESHOLD(默认为8),并且 table 的大小 >= MIN_TREEIFY_CAPACITY(默认为64),就会进行树化(红黑树),否则仍然采用数组扩容机制
Set 接口实现类 —— LinkedHashSet
LinkedHashSet 的说明
- LinkedHashSet 是 HashSet 的子类
-
LinkedHashSet 底层是 LinkedHashMap,底层维护了一个 数组 + 双向链表
数组 table 存放的结点类型是 LinkedHashMap$Entry
static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }
-
LinkedHashSet 根据元素的 hashCode 值来确定元素的存储位置,同时使用链表维护元素的次序,这使得元素看起来是以插入顺序保存的
-
LinkedHashSet 不允许重复元素
public static void main(String[] args) {
LinkedHashSet linkedHashSet = new LinkedHashSet();
linkedHashSet.add(new String("AA"));
linkedHashSet.add(456);
linkedHashSet.add(456);
linkedHashSet.add(new Customer("刘", 1001));
linkedHashSet.add(123);
linkedHashSet.add(new Customer("张", 1002));
// ...
}
- LinkedHashSet 底层是LinkedHashMap,而LinkedHashMap 在 HashMap 存储结构的基础上多使用了双向链表记录添加元素的顺序
- LinkedHashMap 中定义了 Entry 继承了HashMap的Node,底层存储数据时是数组+链表/红黑树(即哈希表结构),在此结构之上还定义了 Entry<K,V> before, after;用来记录添加元素的顺序
Set 接口实现类 —— TreeSet
TreeSet 的特点:
-
有序
TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式,自然排序 和定制排序,其中自然排序为默认的排序方式。向TreeSet中加入的应该是同一个类的对象。
-
不重复;key不能为null(总结一点:凡是有Tree的集合,都是有序的,凡是有Set的就是不重复的)
-
TreeSet 底层调用 TreeMap
-
自然排序使用要排序元素的
CompareTo(Object obj)
方法来比较元素之间大小关系,然后将元素按照升序排列定制排序,应该使用 Comparator 接口,实现
int compare(T o1, T o2)
方法。