目录
无序(添加和取出的顺序不一致),没有索引
注意:取出的顺序虽然不是添加的顺序,但是是固定的
不允许重复元素,所以最多包含一个null
Set中常用的实现类有 HashSet 和 TreeSet
有两种 1、迭代器 2、增强for循环 (但是不能使用索引方式来获取 没有索引)
HashSet实现了Set接口
HashSet实际上底层是HashMap
public HashSet() { map = new HashMap<>(); }
可以存放null值,但是只能有一个null
HashSet不保证元素是有序的,取决于hash值 来确定存放在数组中索引的位置(底层源码)
不能有重复的元素 add添加如果成功就返回true 否则返回false
经典的面试题
- public class HashSet_ {
- public static void main(String[]args){
- Set set = new HashSet();
- set.add("lucy"); //ok
- set.add("lucy"); //加入不了
- set.add(new Dog("tom")); //ok
- set.add(new Dog("tom"));//ok
- //String这个比较特殊 要看源码才能解析
- //主要是因为String重写了hashCode和equals 导致hashMap认为这两个是同一个所以失败
- set.add(new String("jack")); //ok
- set.add(new String("jack")); //这个是不成功的
- }
- }
- class Dog {
- private String name ;
-
- public Dog(String name) {
- this.name = name;
- }
- }
-
HashSet底层是HashMap ,而HashMap的底层是 数组+链表+红黑树
执行add方法
HashSet的底层是HashMap
添加一个元素,先得到hash值, 通过公式转换成索引值
找到存储数据的数组 --表table,看这个索引位置是否已经有元素吗
如果没有直接加入
如果有,调用equalse比较,如果相同,就放弃添加,如果不相同,则添加到最后
java8中 如果一条链表元素个数 >=(默认是8),并且数组的长度 >=64的时候,这个链表就进行树化(变成红黑树)
- package com.sofwin.controller;
-
- import java.util.HashSet;
-
- /**
- * @packageName: com.sofwin.controller
- * @author: wentao
- * @date: 2022/10/31 21:34
- * @version: 1.0
- * @email 1660420659@qq.com
- * @description: TODO
- */
- 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(hashSet);
- /**
- * 源码解读
- * 1、 执行HashSet()
- * public HashSet() {
- * map = new HashMap<>();
- * }
- *2、执行add方法
- *
- * public boolean add(E e) {
- * // PRESENT --> private static final Object PRESENT = new Object();
- * return map.put(e, PRESENT)==null;
- * }
- *
- * 3.执行put() 该方法会执行hash(key)方法
- * public V put(K key, V value) {
- * //key是java value是PRESENT 是共享的
- * return putVal(hash(key), key, value, false, true);
- * }
- *4.hash(key) 方法是通过对象的hashCode方法获取的
- * static final int hash(Object key) {
- * int h;
- * return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
- * }
- *
- * 5、核心代码 putVal
- * final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- * boolean evict) {
- * Node
[] tab; Node p; int n, i; //定义辅助变量 - * //table是hashMap的一个属性 是Node[]
- * //如果table为空 或者长度为0 就进行第一次扩容
- * if ((tab = table) == null || (n = tab.length) == 0)
- * //设置创建了一个容量为·16的Node数组赋值给table 并且设置了临界值
- * n = (tab = resize()).length;
- * // (n - 1) & hash 通过hash计算该元素在数组中的索引
- * //判断在该索引位置的数组是否有元素 如果没有元素,就进行创建一个新的元素并且添加
- * if ((p = tab[i = (n - 1) & hash]) == null)
- * tab[i] = newNode(hash, key, value, null);
- * else {
- * //开发技巧提示, 在需要局部变量在创建 是比较好的
- * Node
e; K k; //定义辅助变量 - * //如果当前索引位置链表对应的第一个元素和准备添加的key哈希值一样
- * //并且满足准备加入的key和p指向的node节点的key一样 或者 满足key != null && key.equals(k)
- * //就不能加入
- * if (p.hash == hash &&
- * ((k = p.key) == key || (key != null && key.equals(k))))
- *
- * e = p;
- * //p是不是一颗红黑树 用红黑树进行putTreeVal 进行添加
- * else if (p instanceof TreeNode)
- * e = ((TreeNode
)p).putTreeVal(this, tab, hash, key, value); - * else {
- * //否则 就加入到链表中
- * //for循环比较 (1)依次和该链表每个元素比较后 都不相同,说明不相同 进行尾插
- * for (int binCount = 0; ; ++binCount) {
- * if ((e = p.next) == null) {
- * p.next = newNode(hash, key, value, null);
- * //(3)如果链表大于等于8的时候 就判断是否转换为红黑树
- * //注意:在进行转换红黑树的方法时候,还进行一个判断
- * //1,如果table数组为空,或者大小未超过64,则重置table大小
- * //扩容table table变大了碰撞就更小了,使得链表不容易继续加长
- * // if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
- * // resize();
- * if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
- * treeifyBin(tab, hash); //下面有具体注释
- * break;
- * }
- * //(2)在依次比较过程中如果有相等的就走人
- * 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(); //第一次是16 12 第二次都是扩大二倍
- * afterNodeInsertion(evict); //这个方法是一个空方法,是留给HashMap的子类扩展功能的
- * return null;
- * }
- *
- */
- }
- }
HashSet的扩容和转成红黑树的机制
- HashSet底层是HashMap,第一次添加的时候,table数组扩容到16,临界值(threshold)是16*0.75 =12
-
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //default initial capacity 初始化的容量 必须是2的倍数 开始为16
-
- static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量
-
- static final float DEFAULT_LOAD_FACTOR = 0.75f; //加载因子、负载因子等等
-
- static final int TREEIFY_THRESHOLD = 8; //treeify threshold判断链表是否转化为红黑树的临界值,值为8
-
- static final int UNTREEIFY_THRESHOLD = 6; //untree判断是否应该由红黑树退回链表的临界值,值为6
-
-
- static class Node
implements Map.Entry { //这个是节点的类 --- 存放元素的信息 - final int hash;
- final K key;
- V value;
- Node
next; - }
-
-
- static final class TreeNode
extends LinkedHashMap.Entry { //红黑树的类 - TreeNode
parent; // red-black tree links - TreeNode
left; - TreeNode
right; - TreeNode
prev; // 需要在下一次删除时断开链接 - boolean red;
- }
-
- transient Node
[] table; //存放链表的数组 -
- transient int size;//已存元素的个数
-
- int threshold;//表示下次扩容的临界值 初始为0,当size>=threshold时,扩容 threshold=集合的容量*负载因子(加载因子)
-
- final float loadFactor;//加载因子
-
- public HashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
- }
-
-
- Node
[] oldTab = table; - int oldCap = (oldTab == null) ? 0 : oldTab.length;
- int oldThr = threshold;
- int newCap, newThr = 0;
- else {
- // 第一次的时候 table容量为16
- //阀值为 16*0.75
- newCap = DEFAULT_INITIAL_CAPACITY;
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
如果table数组中数据(数据不管是数组中还是链表中),只要个数到达临界值12,就会扩容到16*2 = 32 ,新的临界值是原来的2 12×2 = 24
- //加入完毕后 是否超过阀值 如果超过就进行扩容
- // 注意 这个size是每次加入一个元素都会增加
- //因此 即使 数组中有一个链表是12的长度 在加入元素的时候也会进行扩容
- if (++size > threshold)
- resize();
-
- resize() :扩容方法
- if (oldCap > 0) {
- if (oldCap >= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- //oldCap大于等于12的时候 扩容2倍
- else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
- oldCap >= DEFAULT_INITIAL_CAPACITY)
- //阀值也变成二倍
- newThr = oldThr << 1; // double threshold
- }
在java8中,如果一条链表的元素个数到达8 并且table的大小大于等于64就会进行树化(红黑树),否则仍然采取数组扩容机制
*
- //树化代码
- * final void treeifyBin(Node
[] tab, int hash) { - * int n, index; Node
e; - * //1,如果table数组为空,或者大小未超过64,则重置table大小
- * if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
- * resize();
- * //2,如果table大小超过64,把当前链表转换成红黑树
- * else if ((e = tab[index = (n - 1) & hash]) != null) {
- * TreeNode
hd = null, tl = null; - * do {
- * //2.1,循环链表,把每一个对象转换成红黑树,并绑定上下级关系
- * TreeNode
p = replacementTreeNode(e, null); - * if (tl == null)
- * hd = p;
- * else {
- * //并绑定上下级关系
- * p.prev = tl;
- * tl.next = p;
- * }
- * tl = p;
- * } while ((e = e.next) != null);
- * //2.2 重置红黑树相关信息
- * if ((tab[index] = hd) != null)
- * hd.treeify(tab);
- * }
- * }
- //通过这个代码debug来看,能很清晰的看见什么时候树化的
- public class TreeNode_ {
- public static void main(String[]args){
- HashSet hashSet = new HashSet();
- for (int i = 1; i <= 12; i++){
- hashSet.add(new Acb(i));
- }
- }
- }
- class Acb {
- private int a;
-
- public Acb(int a) {
- this.a = a;
- }
-
- @Override
- public int hashCode() {
- return 1;
- }
- }
HashSet底层添加机制
1、 先获取元素的哈希值(程序员可以重写) 通过hash值来计算在数组中的索引位置 2、 如果该位置上没有其他元素,就直接进行添加 3、 如果该位置有元素就进行判断 进行equals判断(程序员可以重写) 如果相等,则不添加 如果不相等,就加入到链表中尾插
面试题
- public class HashSet_ {
- public static void main(String[]args){
- Set set = new HashSet();
- set.add("lucy"); //ok
- set.add("lucy"); //加入不了
- set.add(new Dog("tom")); //ok
- set.add(new Dog("tom"));//ok
- set.add(new String("jack")); //ok
- set.add(new String("jack")); //这个是不成功的
- //String这个类重写了hashCode和equals方法
- /*
- 思路分析:
- //1、先通过hash值来计算在数组中的索引
- //有因为String重写了hashCode方法,是通过字符串来计算hashCode的
- // 因此new String("jack") 这两个hash值是一样的,所以得到数组中索引是一样的
- //2、第一次添加数组位置没有元素 添加成功
- //3、第二次添加的时候有元素了, 如果进行equals比较
- //4.结果String重写了equals是比较字符串,字符串相等 因此添加不成功
- hashCode()
- public int 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;
- }
-
- equals方法:
- public boolean equals(Object anObject) {
- if (this == anObject) {
- return true;
- }
- if (anObject instanceof String) {
- String anotherString = (String)anObject;
- int n = value.length;
- if (n == anotherString.value.length) {
- char v1[] = value;
- char v2[] = anotherString.value;
- int i = 0;
- while (n-- != 0) {
- if (v1[i] != v2[i])
- return false;
- i++;
- }
- return true;
- }
- }
- return false;
- }
- */
- }
- }
- class Dog {
- private String name ;
- public Dog(String name) {
- this.name = name;
- }
- }
练习题
定义一个Employee类 该类包含private成员属性 name、sal、birthday(MyDate类型),
其中birthday为MyDate类 (属性包含year、month、day)
要求:创建三个Employee放入HashSet中
当name和birthday的值相同时,认为是相同员工,不能添加到HashSet集合中
- package com.sofwin.controller;
-
- import java.util.HashSet;
- import java.util.Objects;
-
- /**
- * @author: wentao
- * @date: 2022/11/1 10:26
- * @version: 1.0
- */
- public class Employee {
- private String name;
- private String sal;
- private MyDate brithday;
-
- public static void main(String[]args){
- HashSet set = new HashSet();
- set.add(new Employee("张三","nan",new MyDate(2022,1,1)));
- set.add(new Employee("李四","nan",new MyDate(2022,1,1)));
- set.add(new Employee("王五","nan",new MyDate(2022,1,1)));
- set.add(new Employee("张三","nv",new MyDate(2022,1,1)));
- System.out.println(set);
- //[Employee{name='张三', sal='nan', brithday=MyDate{year=2022, month=1, day=1}},
- // Employee{name='王五', sal='nan', brithday=MyDate{year=2022, month=1, day=1}},
- // Employee{name='李四', sal='nan', brithday=MyDate{year=2022, month=1, day=1}}]
- }
-
-
- @Override
- public boolean equals(Object o) {
- if (this == o) return true;
- if (o == null || getClass() != o.getClass()) return false;
- Employee employee = (Employee) o;
- return Objects.equals(name, employee.name) &&
- Objects.equals(brithday, employee.brithday);
- }
-
- public Employee(String name, String sal, MyDate brithday) {
- this.name = name;
- this.sal = sal;
- this.brithday = brithday;
- }
-
- @Override
- public int hashCode() {
-
- return Objects.hash(name, brithday);
- }
-
-
- @Override
- public String toString() {
- return "Employee{" +
- "name='" + name + '\'' +
- ", sal='" + sal + '\'' +
- ", brithday=" + brithday +
- '}';
- }
- }
-
- class MyDate {
- private int year;
- private int month;
- private int day;
-
- @Override
- public 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;
- }
-
- public MyDate(int year, int month, int day) {
- this.year = year;
- this.month = month;
- this.day = day;
- }
-
- @Override
- public int hashCode() {
-
- return Objects.hash(year, month, day);
- }
-
- @Override
- public String toString() {
- return "MyDate{" +
- "year=" + year +
- ", month=" + month +
- ", day=" + day +
- '}';
- }
- }
-
LinkedHashSet 是HashSet的子类
LinkedHashSet底层是一个LinkedHashMap,底层维护了一个数组+双向链表+红黑树
LinkedHashSet根据元素的hashCode值来决定元素的存储位置,同时使用链表维护元素的次序,这使得元素看起来是以插入顺序保存的
LinkedHashSet不允许添加重复元素
在LinkedHashSet中维护了一个hash表(数组table)和双向链表 (LinkedHashSet有head和tail 头结点和尾结点)
每个结点都有before和after属性 (前一个节点 后一个节点),这样就可以形成双向链表
在添加一个元素的时候,先求hash值,在求索引,确定该元素在table的位置,然后将添加的元素加入到双向链表中(如果已经存在,相同不添加,不相同加入到链表中(next指向 跟hashSet一样))
加入双向链表中利用before和after进行指向,这样就确保了插入顺序和遍历顺序一样
- /**
- * @author: wentao
- * @date: 2022/11/1 12:20
- * @version: 1.0
- * @description: LinkedHashSet的底层机制
- */
- public class LinkedHashSetSource {
- public static void main(String[]args){
- //分析一下 LinkedHashSet的底层机制
- 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);
- /*
- 1. LinkedHashSet 加入顺序和取出元素/数据一致
-
- 2.LinkedHashSet 底层维护的 LinkedHashMap 的底层是HashMap
- Set set = new LinkedHashSet();
- public LinkedHashSet() {
- super(16, .75f, true);
- }
-
- HashSet(int initialCapacity, float loadFactor, boolean dummy) {
- map = new LinkedHashMap<>(initialCapacity, loadFactor);
- }
-
- public LinkedHashMap(int initialCapacity, float loadFactor) {
- super(initialCapacity, loadFactor);
- accessOrder = false;
- }
-
- public HashMap(int initialCapacity, float loadFactor)
-
- 3、 底层是HashMap 因此初始化16 阈值是12 以后扩容跟HashMap 也可以说HashSet一致
-
- 4、注意存放的结点类型不在是 Node 而是LinkedHashMap$Entry
- 5、数组是HashMap$Node[] 存放的元素类型是LinkedHashMap$Entry 多态现象
- //继承关系在内部类完成
- static class Entry
extends HashMap.Node { - Entry
before, after; - Entry(int hash, K key, V value, Node
next) { - super(hash, key, value, next);
- }
- }
- 6、
- */
-
-
-
- }
- }
- class Customer {
- private String name;
- private int num;
-
- public Customer(String name, int num) {
- this.name = name;
- this.num = num;
- }
-
- @Override
- public String toString() {
- return "Customer{" +
- "name='" + name + '\'' +
- ", num=" + num +
- '}';
- }
- }
Set调用的底层其实是Map,这里Set只是用来Map中的key存储数据了 value是固定一个值(PRESENT)