Set集合
1.基础介绍
属于Collection的子类接口
Set集合存储数据的特点:无序，不可重复。取决于hash后，再确定索引的结果。
1.为什么重写了equals必须重写hashcode方法?
Set集合在判断2个对象是否相等的时候
<1>.先检查hashcode值是否相等(默认情况下一个唯一的值，内存地址就是由hashcode的16进制组成)
不相等，那么说明2个对象不相等。（不会去判断equals方法了）
如果相等才回去判断equals是否相等
<2>如果equals相等则2个对象就是相等的。
结论:
<1>.equals相等的2个对象 hashCode一定相等
<2>.hashCode相等的2个对象，equals不一定相等
问题一:如果我只重写equals方法？ Set 如何去执行add方法的？
equals(Object o){
属性全部相等return true...
}
没有重写hashcode（hashcode是系统分配唯一）
set.add(new User(18,"jack"));//分配一个唯一hashcode值
set.add(new User(18,"jack"));//分配一个唯一hashcode值
因为只重写了equals没有重写hashcode方法，导致2个对象hashcode值不一样，判断的时候直接认为2个对象不相等，equals方法不会执行了。
Set添加元素的过程：
1.先获取元素的哈希值（hashCode方法）
2.对哈希值进行运算，得出一个索引值即为要存放在哈希表中的位置号
3.如果该位置上没有其他元素，则直接存放；如果有其他元素，则需要equals进行判断，如果相等，则不再添加，如果不相等，则以链表的方式添加。
无序:指的是不会按照添加的顺序排列。
(其实set集合是有顺序的，HashSet会默认按照数据的hash值进行顺序排列) ;//跟数据大小无关
（TreeSet也有默认顺序的，会按照大小顺序进行排列顺序排列）;//跟数据的大小是由关系的
如果使用TreeSet存储数据（自定义类型 Student,User）可以存方法吗? 比较器
不可重复:不能添加重复的元素
执行添加的时候先判断hashcode 相等了 才会去判断equals 如果都相等，则判断是重复，不会添加，如果不相等才会添加。
有关hashSet扩容：
我们都明白扩容因子是0.75，当数组大小为16时，存放12个元素后，再次存放下一个元素时，就需要扩容了。
这是的12个元素不是指数组16个格子用了12个，而是真的指存放了12个元素，哪怕这12个元素都接在一个链表上。
2.HashSet的应用
HashSet:底层是由HashMap实现(HashMap中的Key)
public static void main(String[] args) {
HashSet<String> set=new HashSet<>();
//1.添加,插入数据(自动去除重复的元素)
set.add("jack");
set.add("apple");
set.add("china");
set.add("jack");
set.add("apple");
set.add("china");
set.add("rouse");
//2.根据元素从集合中删除
set.remove("jack");
//3.修改元素
set.remove("apple");
set.add("Apple");
System.out.println("获取集合的长度:"+set.size());//返回元素的个数
//4.遍历元素(只能根据增强for循环以及迭代器遍历集合)
System.out.println("-----------------增强for循环------------------");
for(String str:set) {
System.out.println(str);
}
System.out.println("---------------迭代器---------------");
Iterator<String> it=set.iterator();
while(it.hasNext()) {
System.out.println("元素为:"+it.next());
}
System.out.println("------------------------------");
System.out.println(set);
System.out.println("--------------------------");
//5.批量添加数据至集合
List<String> list=new ArrayList<String>();
list.add("赵云");
list.add("关羽");
list.add("赵云");
list.add("赵云");
list.add("关羽");
list.add("关羽");
set.addAll(list);
System.out.println(set);
}
2.1分析HashSet源码：
public static void main(String[] args) {
HashSet hashSet = new HashSet(); hashSet.add("java");//到此位置，第 1 次 add 分析完毕.
hashSet.add("php");//到此位置，第 2 次 add 分析完毕
hashSet.add("java");
System.out.println("set=" + hashSet);
}
1. 执行 HashSet()
public HashSet() {
map = new HashMap<>();
}
2. 执行 add()
public boolean add(E e) {//e = "java"
//(static) PRESENT = new Object();
哨兵value，只是占位map(k,v)的v的参数，没有意义。
return map.put(e,PRESENT)==null;
}
3.执行 put() , 该方法会执行 hash(key) 得到 key 对应的 hash 值
算法：h = key.hashCode()) ^ (h >>> 16)
算数右移16位。此hash值不是hashcode因为做了右移处理。
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)
//第二次add直接进入此if
if ((p = tab[i = (n - 1) & hash]) == null)
//为什么把key对应的hash存放进去呢？
//再次存入会查看key对应的hash和下一个相等不相等
//null表示没有后继结点
tab[i] = newNode(hash, key, value, null);
else {
//第三次add，进入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() 对当前这个链表进行树化(转成红黑树)
注意，在转成红黑树时，要进行判断, 判断条件
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
resize();
如果上面条件成立，先 table 扩容.
只有上面条件不成立时，才进行转成红黑树
(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接 break
for (int binCount = 0; ; ++binCount) {
//如果添加的元素，Set中没有的话，就走这，然后break
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD(8) - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果已经存在的话，for循环到这直接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;
//size 就是我们每加入一个结点 Node(k,v,h,next), size++
if (++size > threshold)
resize();//扩容
//空方法，留给子类使用。
afterNodeInsertion(evict);
return null;
}
3.LinkedHashSet的应用
3.1图示：
Set set = new LinkedHashSet();
set.add("AA");
set.add(456);
set.add(new Customer("刘",1001));
set.add(123);
set.add("Java")''
3.2使用
LinkedHashSet:有序的（跟你添加的顺序相同，有序使用链表去实现的）
public static void main(String[] args) {
LinkedHashSet<String> set=new LinkedHashSet<>();
set.add("jack");
set.add("apple");
set.add("china");
set.add("jack");
set.add("apple");
set.add("china");
set.add("rouse");
//1.不仅去重，而且会维持原先的顺序
System.out.println(set);
set.remove("jack");
System.out.println(set.contains("rouse")?"存在":"不存在");
System.out.println("集合的长度:"+set.size());
System.out.println("删除之后查看数据:"+set);
//2.集合的遍历方式: 增强for循环 迭代器
//不能使用普通for遍历
System.out.println("-----------------增强for循环------------------");
for(String str:set) {
System.out.println(str);
}
System.out.println("---------------迭代器---------------");
Iterator<String> it=set.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
System.out.println("------------------------------");
}
4.TreeSet的应用
4.1TreeSet基本使用
TreeSet:底层是由TreeMap实现(TreeMap中的key) 根据数据的大小进行排序(对于自定义类型，默认无法比较大小的，需要借助比较器进行使用TreeSet)
public static void main(String[] args) {
//1.去重，而且会自动按照数据的大小进行排序
TreeSet<Integer> ts=new TreeSet<>();
ts.add(900);
ts.add(1000);
ts.add(300);
ts.add(700);
ts.add(500);
ts.add(100);
ts.add(100);
ts.add(1000);
ts.add(900);
System.out.println(ts);
ts.remove(700);
System.out.println("删除之后:");
System.out.println(ts);
System.out.println("判断元素是否存在:"+ts.contains(500));
System.out.println("元素的个数:"+ts.size());
//1.遍历方式:增强for循环以及迭代器
for(Integer num:ts) {
System.out.println(num);
}
Iterator<Integer> it=ts.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
System.out.println("----------------------------------------");
//1.如果TreeSet放的是自定义类型 ，那么 自定义类型要么实现Comparable 接口，设置自比较，定义比较规则
//或者，在创建TreeSet 定义比较器传递Comparator接口的实现类对象，进行定义比较规则
TreeSet<Student> stuSet=new TreeSet<>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
if(o1.equals(o2)) {//如果2个对象相同则不放进去
return 0;//等于0说明 2个对象 相等
}else {//如果2个对象不相同 放进去
return 1;
}
}
});
stuSet.add(new Student("jack1",18));
stuSet.add(new Student("jack2",19));
stuSet.add(new Student("jack3",20));
stuSet.add(new Student("jack4",18));
stuSet.add(new Student("jack5",21));
System.out.println(stuSet);
}
4.2源码解读
-- 1. 当我们使用无参构造器，创建 TreeSet 时，仍然是无序的
-- 2. 添加的元素，按照字符串大小来排序
-- 3. 使用 TreeSet 提供的一个构造器，可以传入一个比较器(匿名内部类)
-- 4.并指定排序规则
请看源码：
1. 构造器把传入的比较器对象，赋给了 TreeSet 的底层的 TreeMap 的属 this.comparator
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
2.调用treeSet.add("tom"),在底层执行
//cpr 就是我们的匿名内部类(对象)
if (cpr != null) {
do {
parent = t;
//动态绑定到我们的匿名内部类(对象)
compare cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else //如果相等，即返回 0,这个 Key 就没有加入
return t.setValue(value);
} while (t != null);
}
@SuppressWarnings({"all"})
public class Test {
public static void main(String[] args) {
TreeSet treeSet = new TreeSet(new Comparator() {
@Override public int compare(Object o1, Object o2) {
//下面 调用 String 的 compareTo 方法进行字符串大小比较
return ((String) o2).compareTo((String) o1);
}});
//添加数据.
treeSet.add("jack");
treeSet.add("tom");
treeSet.add("sp");
treeSet.add("a");
treeSet.add("abc");
System.out.println("treeSet=" + treeSet);
}
}
TreeSet treeSet = new TreeSet(new Comparator() {
@Override public int compare(Object o1, Object o2) {
//下面 调用 String 的 compareTo 方法进行字符串大小比较
return ((String) o1).length() - ((String) o2).length();
}});
此时比较强写成长度大小，那么
添加数据
treeSet.add("abd");
treeSet.add("qwe");
添加是不成功的、因为
else //如果相等，即返回 0,这个 Key 就没有加入
return t.setValue(value);
版权声明：本文为jwsl999原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。