目录
一、Set接口基本介绍
二、Set接口的常用方法
三、Set接口实现类——HashSet
四、HashSet(HashMap底层原理:重要!!!)
(一)第一次添加元素
(二)第二次添加不同的元素
(三)添加重复的元素
1.仍旧走到了putVal(hash(key), key, value, false, true);方法
2.判断计算出的索引位置,是否为null,不为null,继续跳过下一个if,进入else中的第1个if
3.添加失败的源码解读:
4.关于扩容的源码解读
5.转成红黑树源码解读
五、练习题
1.练习1
2.练习2
一、Set接口基本介绍
- 无序(添加和取出的顺序不一致),没有索引
- 不允许重复元素,所以最多包含一个null
- JDK API中Set接口的实现类有:
二、Set接口的常用方法
- 和List接口一样,Set接口也是Collection的子接口,因此,常用方法和Collection接口一样
- set 接口的实现类的对象(Set接口对象),不能存放重复的元素,可以添加一个null
- set 接口对象存放数据是无序(即添加的顺序和取出的顺序不一致)
- 注意:取出的顺序虽然不是添加的顺序,但是它是固定的
- Set接口的遍历方式:迭代器、增强for,不能使用索引的方式来获取
public static void main(String[] args) {Set set = new HashSet();set.add("john");set.add("lucy");set.add("john");set.add("jack");set.add("marry");set.add(null);set.add(null);System.out.println("set=" + set);// set=[null, marry, john, lucy, jack]set.remove(null);// 遍历// 方式1: 使用迭代器Iterator iterator = set.iterator();while (iterator.hasNext()) {Object obj = iterator.next();System.out.println(obj);}// marry// john// lucy// jack// 方式2:增强forfor (Object o : set) {System.out.println("o=" + o);}// o=marry// o=john// o=lucy// o=jack// set 接口对象,不能通过索引来获取
}
三、Set接口实现类——HashSet
- HashSet实现了Set接口
- HashSet底层是HashMap,而HashMap底层是数组+链表+红黑树
- HashSet可以存放null值,但是只能有一个null
- HashSet不保证元素是有序的,取决于hash后,再确定索引的结果
- 不能有重复元素/对象
public static void main(String[] args) {HashSet set = new HashSet();//说明//1. 在执行add方法后,会返回一个boolean值//2. 如果添加成功,返回 true, 否则返回false//3. 可以通过 remove 指定删除哪个对象System.out.println(set.add("john"));//TSystem.out.println(set.add("lucy"));//TSystem.out.println(set.add("john"));//FSystem.out.println(set.add("jack"));//TSystem.out.println(set.add("Rose"));//Tset.remove("john");System.out.println("set=" + set);// set=[Rose, lucy, jack]set = new HashSet();System.out.println("set=" + set);// set=[]//4 Hashset 不能添加相同的元素/数据?set.add("lucy");// 添加成功set.add("lucy");// 添加失败set.add(new Dog("tom"));// 添加成功set.add(new Dog("tom"));// 添加成功System.out.println("set=" + set);// set=[Dog{name='tom'}, Dog{name='tom'}, lucy]// 看源码,做分析,即 add 到底发生了什么?=> 底层机制set.add(new String("hello"));// 添加成功set.add(new String("hello"));// 添加失败System.out.println("set=" + set);// set=[Dog{name='tom'}, Dog{name='tom'}, hello, lucy]
}class Dog {private String name;public Dog(String name) {this.name = name;}@Overridepublic String toString() {return "Dog{" +"name='" + name + '\'' +'}';}
}
四、HashSet(HashMap底层原理:重要!!!)
(一)第一次添加元素
1. 执行 HashSet()public HashSet() {map = new HashMap<>();}2. 执行 add()// private static final Object PRESENT = new Object();// PRESENT 是一个静态常量,类型是Object,用于在map中进行占位的public boolean add(E e) { // e = "john"return map.put(e, PRESENT)==null;}3.执行 put()// key = "john" value = PRESENT 共享public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}4.执行hash(key)该方法会key对象的hashCode进行运算,得到新的hash值注意:static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}5.回到 putVal(hash(key), key, value, false, true);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[],初始长度为null// if 语句表示如果当前table 是null, 或者 大小=0// 进行第一次扩容,到16个空间 (在6中有讲解)if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length; // 16// (1) 根据key,即传入的对象,得到新的hash// (2) i = (n - 1) & hash:计算该key应该存放到table表的哪个索引位置,// (3) p = tab[i = (n - 1) & hash] 把这个位置的对象,赋给 p// (4) 判断p 所在的索引位置是否为null// (4.1) 如果p 为null, 表示还没有存放元素, 就创建一个Node(key="john",value=PRESENT)// (4.2) 将key存放在该位置 tab[i] = newNode(hash, key, value, null)if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// newNode()方法:// Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {// return new Node<>(hash, key, value, next);// }else{......}++modCount; // 计算插入的次数// size 就是每加入一个结点Node(k,v,h,next), size++if (++size > threshold) // 查看添加次数是否到达临界值12resize(); // 扩容afterNodeInsertion(evict);// void afterNodeInsertion(boolean evict) { } 是一个空方法,// 是为了让HashMap的子类,例如LinkedHashMap来实现return null; // 返回null就是存放成功的意思}6.第一次扩容的resize()方法:
因为数组长度为0,所以进入到最后一个else
数组扩容到16,临界值为12=0.75*16
else { // static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16newCap = DEFAULT_INITIAL_CAPACITY; // 16// static final float DEFAULT_LOAD_FACTOR = 0.75f;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 临界值:12}
}
(二)第二次添加不同的元素
前面的都一样,只是这次数组长度不为null,是16,所以不会扩容;通过hash(key)方法计算出新的hash值,再根据新的hash值计算存放的索引位置,赋值给p,判断p所在的位置是否为null,为null,就创建新的结点存放进去。
存放成功后,再次返回null给putVal()方法
(三)添加重复的元素
1.仍旧走到了putVal(hash(key), key, value, false, true);方法
先判断数组长度是否为null,不为null,进入到下一个if
2.判断计算出的索引位置,是否为null,不为null,继续跳过下一个if,进入else中的第1个if
3.添加重复值的源码解读:
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);else {// 如果table对应索引位置,已经是一个链表, 就使用for循环比较// (1) 依次和该链表的每一个元素比较后,都不相同, 则加入到该链表的最后// 注意在把元素添加到链表后,立即判断 该链表是否已经达到8个结点,// 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)// 注意:在转成红黑树之前,要调用treeifyBin()进行判断, 判断条件:// final void treeifyBin(Node<K,V>[] tab, int hash) {// int n, index; Node<K,V> e;// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // resize();// static final int MIN_TREEIFY_CAPACITY = 64;// 如果链表>=7,但是整个数组的长度没有到64,那么不会转成红黑树,// 会执行resize()方法进行扩容// 只有上面条件不成立时(即链表=8 && 数组长度>=64),才进行转成红黑树// (2) 依次和该链表的每一个元素比较过程中,如果有相同情况,就直接breakfor (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD(8) - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 添加重复值走下面的代码:// 注意:这里返回的oldValue是PRESENTif (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}// 添加成功走下面的代码:++modCount;// 每新增一个节点就会记录一次,当超过临界值12就会扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
在 HashSet 中,添加重复值时:
- value 不会更新:
HashSet 底层是使用 HashMap 来实现的,每个元素作为 HashMap 的键,值是一个固定的常量(PRESENT)。无论你往 HashSet 中添加多少次相同的元素,底层 HashMap 中该元素对应的 value 始终是 PRESENT。
因此,当添加重复的元素时,value 不会更新,因为值永远是 PRESENT,不会发生变化。
- key 也不会更新:
在 HashSet 中,key 是唯一的(即元素是唯一的)。当你第一次添加某个元素时,HashMap 会将该元素作为 key 插入。
当尝试添加重复的元素时,HashMap 会发现该 key 已经存在,于是不会再重新插入,也不会更新 key。
所以,key 也不会更新,因为 HashMap 保证键的唯一性,重复添加相同的 key 不会导致键的覆盖或更新。
总结:
- value:永远是 PRESENT,不会被更新。
- key:如果 key 已经存在(即元素已经在 HashSet 中),则不会被重新插入或更新。
- 因此,在 HashSet 中,添加重复的元素不会影响已有的键或值,元素的唯一性得到了保证。
- 先获取元素的哈希值(hashCode方法)
- 对哈希值进行运算,得出一个索引值,即为要存放在哈希表中的位置号
- 如果该位置上没有其他元素,则直接存放;如果该位置上已经有其他元素,只需要进行equals判断,如果相等,则不再添加。如果不相等但计算后的hash值相同,则以链表的方式添加。
- 注意:传入的对象要看是否重写了equals方法,如果重写了,则判断内容相等,不再添加;如果没有重写,则判断地址值,重复的元素可以相加。
- HashSet底层是HashMap
- 添加一个元素时,先得到hash值,会转成索引值
- 找到存储数据表table,看这个索引位置是否已经存放有元素
- 如果没有,则直接加入
- 如果有,调用equals比较,如果相同,就放弃添加;如果不相同,创建新的结点,添加到最后
- 在JDK8中,如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8),并且table的大小>= MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树)
4.关于扩容的源码解读
- HashSet底层是HashMap,第一次添加时,table数组扩容到16,临界值(threshold)是16*加载因子(loadFactor)是0.75=12
- 如果table数组使用到了临界值12,就会扩容到16 * 2 = 32,新的临界值就是32 * 0.75 = 24,以此类推
- 注意:table数组使用到了临界值12的意思是,每添加一个元素,size就会++一次,加到12的时候就会扩容,而不是数组索引使用了12位或者使用到了12这个索引!!!!!
- 在JDK8中,如果一条链表的元素个数到达TREEIFY_THRESHLOD(默认是8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树),否则仍然采用数组扩容机制
代码示例:
HashSet hashSet = new HashSet();for(int i = 1; i <= 100; i++) {hashSet.add(i);// 1,2,3,4,5...100}
存放到临界值之前:
存放到临界值之后,进行数组扩容:
数组2倍扩容部分源码:
5.转成红黑树源码解读
设置代码,让元素加到一条链表上
public static void main(String[] args) {HashSet hashSet = new HashSet();for(int i = 1; i <= 12; i++) {hashSet.add(new A(i));//}}
}class A {private int n;public A(int n) {this.n = n;}@Overridepublic int hashCode() {return 100;}
}
HashSet初始大小为null
添加第1个元素落到索引为4的位置上:
添加第2个元素,落入链表的下一个结点:
扩容数组到64后,继续添加
添加前:
添加后,链表变为红黑树:
五、练习题
1.练习1
定义一个Employee类,该类包含:private成员属性name,age 要求:
- 创建3个Employee对象放入HashSet中
- 当name和age的值相同时,认为是相同员工,不能添加到HashSet集合中
代码实现:
public class HashSetExercise {public static void main(String[] args) {HashSet hashSet = new HashSet();hashSet.add(new Employee("张三", 20));hashSet.add(new Employee("李四", 25));hashSet.add(new Employee("张三", 20));for (Object o : hashSet) {System.out.println(o);}// Employee{name='张三', age=20}// Employee{name='李四', age=25}}
}class Employee {private String name;private int age;public Employee(String name, int age) {this.name = name;this.age = age;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Employee employee = (Employee) o;return age == employee.age && Objects.equals(name, employee.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}@Overridepublic String toString() {return "Employee{" +"name='" + name + '\'' +", age=" + age +'}';}
}
2.练习2
定义一个Employee1类,该类包含:private成员属性name,sal,birthday(MyDate类型),其中birthday为MyDate类型(属性包括:year、month、day),要求:
- 创建3个Employee放入HashSet中
- 当name和birthday的值相同时,认为是相同员工,不能添加到HashSet集合中
代码实现:
public class HashSetExercise02 {public static void main(String[] args) {HashSet hashSet = new HashSet();hashSet.add(new Employee1("张三", 2000, new MyDate(1990, 1, 14)));hashSet.add(new Employee1("李四", 2000, new MyDate(1998, 10, 28)));hashSet.add(new Employee1("张三", 2900, new MyDate(1990, 1, 14)));for (Object o : hashSet) {System.out.println(o);}// Employee1{name='张三', sal=2000.0, birthday=MyDate{year=1990, month=1, day=14}}// Employee1{name='李四', sal=2000.0, birthday=MyDate{year=1998, month=10, day=28}}}
}class Employee1 {private String name;private double sal;private MyDate birthday;public Employee1(String name, double sal, MyDate birthday) {this.name = name;this.sal = sal;this.birthday = birthday;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Employee1 employee1 = (Employee1) o;return name.equals(employee1.name) && birthday.equals(employee1.birthday);}@Overridepublic int hashCode() {return Objects.hash(name, birthday);}@Overridepublic String toString() {return "Employee1{" +"name='" + name + '\'' +", sal=" + sal +", birthday=" + birthday +'}';}
}class MyDate {private int year;private int month;private int day;public MyDate(int year, int month, int day) {this.year = year;this.month = month;this.day = day;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;MyDate myDate = (MyDate) o;return year == myDate.year && month == myDate.month && day == myDate.day;}@Overridepublic int hashCode() {return Objects.hash(year, month, day);}@Overridepublic String toString() {return "MyDate{" +"year=" + year +", month=" + month +", day=" + day +'}';}
}