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)方法。