1、Set接口基本介绍
- 无序（添加和取出的顺序不一致），没有索引
- 不允许重复元素，所以最多包含一个null
- JDK API中Set接口的实现类有AbstractSet ， ConcurrentHashMap.KeySetView ， ConcurrentSkipListSet ， CopyOnWriteArraySet ， EnumSet ， HashSet ， JobStateReasons ， LinkedHashSet ， TreeSet
2、Set接口的常用方法
- 和List接口一样，Set接口也是Collection的子接口，因此，常用方法和Collection接口一样
3、Set接口的遍历方式
- 同Collection的遍历方式一样，因为Set接口是Collection接口的子接口
- 可以使用迭代器
- 增强for循环
- 不能使用索引的方式来获取
import java.util.Iterator;
import java.util.Set;
import java.util.HashSet;
@SuppressWarnings({"all"})
public class SetMethod {
public static void main(String[] args) {
//1. 以Set 接口的实现类 HashSet 来讲解Set 接口的方法
//2. set 接口的实现类的对象（Set接口对象），不能存放重复的元素，可以添加一个null
//3. set 接口对象存放数据是无序的（即添加的顺序和取出的顺序不一致）
//4. 注意：取出的顺序的虽然不是添加的顺序，但是他是固定的
Set set = new HashSet();
set.add("john");
set.add("lucy");
set.add("john");
set.add("jack");
set.add("hsp");
set.add(null);
set.add(null);
System.out.println("set=" + set);
//遍历
//方式1：使用迭代器
Iterator iterator= set.iterator();
while (iterator.hasNext()) {
Object obj = iterator.next();
System.out.println("obj=" + obj);
}
System.out.println("===============");
//方式2：增强for循环
for (Object o : set) {
System.out.println("0=" + o);
}
}
}
/*
运行结果：
set=[null, hsp, john, lucy, jack]
obj=null
obj=hsp
obj=john
obj=lucy
obj=jack
===============
0=null
0=hsp
0=john
0=lucy
0=jack
*/
4、HashSet的全面说明
-
HashSet实现了Set接口
-
HashSet实际上是HashMap，
public HashSet() { map = new HashMap<>(); } -
可以存放null值，但是只能有一个null
-
HashSet不保证元素是有序的，取决于hash后，再确定索引的结果
-
不能有重复元素/对象
-
分析HashSet底层是HashMap，HashMap底层是（数组+链表+红黑树）
-
HashSet的添加元素底层时如何实现
- HashSet底层是 HashMap
- 添加一个元素时看，先得到hash值 -会转成 - > 索引值
- 找到存储数据表table，看到这个索引位置是否已经存放有元素
- 如果没有，直接加入
- 如果有，调用 equals 比较，如果相同，就放弃添加，如果不相同，则添加到最后
- 在Java8中，如果一条链表的元素个数到达TEEIFY_THRESHOLD(默认是8)，并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64)，就会进行树化（红黑树）
package com.hspedu.set_; import java.util.HashSet; @SuppressWarnings({"all"}) public class HashSetSource { public static void main(String[] args) { HashSet hashSet = new HashSet(); hashSet.add("java"); hashSet.add("php"); hashSet.add("java"); System.out.println("set=" + hashSet); /* 源码解读 1. 执行 HashSet() public HashSet() { map = new HashMap<>(); } 2. 执行 add() public boolean add(E e) { //e = "java" return map.put(e, PRESENT)==null; //(static) PRESENT = new Object(); } 3. 执行 put() , 该方法会执行 hash(key) 得到key对应的hash值 算法(h = key.hashCode()) ^ (h >>> 16) public V put(K key, V value) {//key = "java" value = PRESENT return putVal(hash(key), key, value, false, true); } 4. 执行 putVal final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //table 就是 HashMap 的一个数组，类型是 Node[] //if 语句表示如果当前table 是null, 或者 大小=0 //就是第一次扩容，到16个空间 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //(1)根据key，得到hash 去计算该key应该存放到table表的哪个索引位置 //并把这个位置的对象，赋给 p //(2)判断 p 是否为null //(2.1) 如果p 为null，表示还没有存放元素，就创建一个Node (key = "java",value = PRESENT) //(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null) // if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //一个开发技巧提示：在需要局部变量(辅助变量)时候，再创建 Node<K,V> e; K k; //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样 //并且满足下面两个条件之一： //(1) 准备加入的key 和 p 指向的Node 结点的 key 是同一个对象 //(2) p 指向的Node 结点的 key 的equals() 和准备加入的key比较后相同 //就不能加入 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //再判断 p 是不是一颗红黑树 //如果是一颗红黑树，就调用 putTreeVal , 来进行添加 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //如果table对应索引位置，已经有一个链表，就使用for循环比较 //(1) 依次和该链表的每一个元素比较后，都不相同，则加入到该链表的最后 // 注意在把元素添加到链表后，立即判断，该链表是否已经达到8个结点 // ， 如果达到，就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树) // 注意，在转成红黑树时，要进行判断，判断条件 // if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // resize(); // 如果上面条件成立，先table扩容， // 只有上面条件不成立时，才进行转成红黑树 //(2) 依次和该链表的每一个元素比较过程中，如果有相同情况，就直接break else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); 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) resize(); afterNodeInsertion(evict); return null; } */ } } /* 运行结果： set=[java, php] */ -
HashSet的扩容和转成红黑树机制
-
HashSet底层是 HashMap，第一次添加时，table数组扩容到16，临界值（threshold）是16*加载因子，
（loadFactor）是0.75 = 12
-
如果table 数组使用到了临界值12，就会扩容到16 * 2 = 32，新的临界值就是32 * 0.75 = 24，依此类推
-
在Java8中，如果一条链表的元素个数到达TEEIFY_THRESHOLD(默认是8)，并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64)，就会进行树化（红黑树），否则仍然采用数组扩容机制
-
5、LinkedHashSet的全面说明
-
LinkedHashSet 是 HashSet 的子类
-
LinkedHashSet 底层是一个 LinkedHashMap，底层维护了一个 数组 + 双向链表
-
LinkedHashSet 根据元素的hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序（图），这使得元素看起来是以插入顺序保存的。
-
LinkedHashSet 不允许添加重复元素
-
底层机制
- 在LinkedHashSet 中维护了一个hash表二号双向链表（LinkedHashSet 有 head 和 tail）
- 每一个结点有before 和after 属性，这样可以形成双向链表
- 在添加一个元素时，先求hash值，在求索引，确定该元素在table 的位置，然后将添加的元素加入到双向链表（如果已经存在，不添加 【原则和hashset一样】）
- 这样的话，我们遍历LinkedHashSet 也能确保插入顺序和遍历顺序一致
package com.hspedu.set_; import java.util.LinkedHashSet; import java.util.Set; @SuppressWarnings({"all"}) public class LinkedHashSetSource { public static void main(String[] args) { //分析LinkeHashSet的底层机制 Set set = new LinkedHashSet(); set.add(new String("AA")); set.add(456); set.add(456); set.add(new Customer("刘",1001)); set.add(123); set.add("HSP"); System.out.println("set = " + set); //1. LinkedHashSet 加入顺序和取出元素/数据的顺序一致 //2. LinkedHashSet 底层维护的是一个LinkedHashMap(是HashMap的子类) //3. LinkedHashSet 底层结构 (数组+双向链表) //4. 添加第一次时，直接将 table 扩容到 16 ，存放的结点类型是 LinkedHashMap$Entry //5. 数组是 HashMap$Node[] 存放的元素/数据是 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); } } */ } } class Customer { private String name; private int no; public Customer(String name, int no) { this.name = name; this.no = no; } } /* 运行结果： set = [AA, 456, com.hspedu.set_.Customer@154617c, 123, HSP] */ -
练习
package com.hspedu.set_; import java.util.LinkedHashSet; import java.util.Objects; @SuppressWarnings({"all"}) public class LinkedHashSetExercise { public static void main(String[] args) { LinkedHashSet linkedHashSet = new LinkedHashSet(); linkedHashSet.add(new Car("奥拓",1000)); linkedHashSet.add(new Car("奥迪",300000)); linkedHashSet.add(new Car("法拉利",100000000)); linkedHashSet.add(new Car("奥迪",300000)); linkedHashSet.add(new Car("保时捷",700000000)); linkedHashSet.add(new Car("奥迪",300000)); System.out.println("linkedHashSet = " + linkedHashSet); } } class Car { private String name; private double price; public Car(String name, double price) { this.name = name; this.price = price; } public String getName() { return name; } public void setName(String name) { this.name = name; } public double getPrice() { return price; } public void setPrice(double price) { this.price = price; } @Override public String toString() { return "\n" + "Car{" + "name='" + name + '\'' + ", price=" + price + '}'; } //重写equals 方法 和 hashCode //当 name 和 price 相同时，就返回相同的 hashCode 值，equas返回t @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Car car = (Car) o; return Double.compare(car.price, price) == 0 && Objects.equals(name, car.name); } @Override public int hashCode() { return Objects.hash(name, price); } } /* 运行结果： linkedHashSet = [ Car{name='奥拓', price=1000.0}, Car{name='奥迪', price=300000.0}, Car{name='法拉利', price=1.0E8}, Car{name='保时捷', price=7.0E8}] */