Java学习----Set接口
今日学习内容总结如下:
HashSet类
HashSet类直接实现了Set接口, 其底层其实是包装了一个HashMap去实现的
以需要存储的数据作为map的key值,以常量PRESENT作为value值
private transient HashMap<E, Object> map;
private static final Object PRESENT=new Object();
HashSet采用HashCode算法来存取集合中的元素,因此具有比较好的读取和查找性能
Set<Person> set=new HashSet<>();
Person p1=new Person();
Person p2=new Person();
set.add(p1);
set.add(p2);
System.out.println(set.size());
//这里显示值为2,因为 Person类中的hashCode方法和equals方法都来自于Object类
Set<Person> set=new HashSet<>();
Person p1=new Person(1L,"yan");
Person p2=new Person(1L,"yan");
set.add(p1);
set.add(p2);
System.out.println(p1.equals(p2));
System.out.println(set.size()); //返回值仍旧为2
在Person类中添加方法
public boolean equals(Object obj){
if(obj!=null && obj instanceof Person){
Person p=(Person)obj;
//具体的比较内容取决于业务规则,这里不进行判空了(偷懒)
return this.id==p.id && this.name.equals(p.name);
}
return false;
}
//再次运行程序输出值还是2
问题在于hashcode值
public int hashCode(){
return this.id.hashCode();
}
原因在于:向HashSet中添加元素时首先执行的是对象的hashcode值比较,如果两个
对象的hashcode值相等时才会继续调用equals方法;如果两个对象的hashcode值不
相等则不会调用equals方法
潜规则:不是Java的语法强制要求
要求当两个对象的equals为true时,hashCode值必须相等
向set中添加元素到底比较是采用==还是equals?
Set<String> set=new HashSet<>();
String s1="abc";
String s2=new String("abc");
System.out.println(s1==s2);
set.add(s1);
set.add(s2);
System.out.println(set.size()); //返回为1
HashSet实际上是通过使用HashMap的key实现的,所有key对应的value都是一个常量
散列算法
散列法Hashing是一种将字符组成的字符串转换为固定长度(一般是更短长度)的数值或索引值的方法,称为散列法,也叫哈希法。
由于通过更短的哈希值比用原始值进行数据库搜索更快,这种方法一般用来在数据库中建立索引并进行搜索,同时还用在各种解密算法中
当然在存储时需要解决哈希碰撞问题
通常处理碰撞的方法有开放寻址Open Addressing法和链地址法。
String类型中的hashCode方法的实现:
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
hash = h = isLatin1() ? StringLatin1.hashCode(value)
: StringUTF16.hashCode(value);
}
return h;
}
由于自定义类都会直接或者间接的继承于java.lang.Object,所以所有的类中都有hashCode方法
public native int hashCode();
HashSet的特征
无序:不仅不能保证元素插入的顺序(如果需要顺序则可以使用LinkedHashSet)
,而且在元素在以后的顺序中也可能变化(这是由HashSet按HashCode存储对象
(元素)决定的,对象变化则可能导致HashCode变化)
如果需要访问的顺序和插入的顺序一致,可以使用HashSet的子类LinkedHashSet
不允许重复 [equals和hashcode]
HashSet是线程非安全的,方法上没有同步约束
如何判断两个对象相等
实现Set接口的HashSet,依靠HashMap来实现的。
我们应该为要存放到散列表的各个对象定义hashCode()和equals()
HashSet的equals和hashCode
前面说过,Set集合是不允许重复元素的,否则将会引发各种奇怪的问题。
那么HashSet如何判断元素重复呢?
HashSet需要同时通过equals和HashCode来判断两个元素是否相等,具体规则
是,如果两个元素通过equals为true,并且两个元素的hashCode相等,则这两
个元素相等(即重复)。
所以如果要重写保存在HashSet中的对象的equals方法,也要重写hashCode方
法,重写前后hashCode返回的结果相等(即保证保存在同一个位置)。所有参
与计算 hashCode() 返回值的关键属性,都应该用于作为 equals() 比较的
标准。
结论:要求当两个同类型对象equals为true时,必须hashCode值一致。事实上
equals方法和hashCode方法没有任何必然联系,所以说前面的规则是个潜规则
LinkedHashSet
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, Serializable
LinkedHashSet是HashSet的一个子类,LinkedHashSet也根据HashCode的值来决
定元素的存储位置,但同时它还用一个链表来维护元素的插入顺序,插入的时候即
要计算hashCode又要维护链表,而遍历的时候只需要按链表来访问元素
采用双向链表记录添加元素的顺序
LinkedHashMap类中的节点定义
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);
}
}
Set<String> set=new LinkedHashSet<>();
for(int i=0;i<10;i++)
set.add("str-"+i);
Iterator<String> it=set.iterator();
while(it.hasNext()){
String tmp=it.next();
System.out.println(tmp);
}
因为底层采用链表和哈希表的算法。链表保证元素的添加顺序,哈希表保证元素的唯一性
TreeSet类
TreeSet实现了SortedSet接口,顾名思义这是一种排序的Set集合
public class TreeSet<E>
extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, Serializable
数据存储采用的是
private transient NavigableMap<E,Object> m;
public interface NavigableMap<K,V> extends SortedMap<K,V>
查看jdk源码发现底层是用TreeMap实现的,本质上是一个红黑树原理。正因为它是排序了的,所以相对HashSet来说,TreeSet提供了一些额外的按排序位置访问元素的方法,例如first(), last(), lower(), higher(), subSet(),headSet(), tailSet()
Random r=new Random();
Set<Integer> lhs=new LinkedHashSet<>(); //用于记录生成的对技术的顺序
Set<Integer> set=new TreeSet<>();
while(set.size()<10){
int k=r.nextInt(100);
lhs.add(k);
set.add(k);
}
System.out.println("生成的数据为:")
System.out.println(lhs);
System.out.println("插入TreeSet后的数据为:");
System.out.println(set);
TreeSet的排序分两种类型,一种是自然排序,另一种是定制排序。
对象大小的比较
Java中为了实现对象的比较引入了compare算法
这里用于实现了两个日期的比较大小,如果返回为0则表示两个对象相等,如果返回为1则表示d1大于参数;如果返回-1表示d1小于参数
实现Comparable接口,在类定义中添加比较规则
public class Person implements Comparable<Person>{
private Long id;
private String name;
public int compareTo(Person person){
if(name!=null && name.trim().length()>0)
return this.name.compareTo(person.name);
return 0;
}
}
Set<Person> set=new TreeSet<>();
for(int i=0;i<10;i++)
set.add(new Person(1L+i, (9-i)+"name"));
set.forEach(System.out::println);
自然排序(在元素中写排序规则)
TreeSet 会调用compareTo方法比较元素大小,然后按升序排序(从小到达)。所以自然排序中的元素对象,都必须实现了Comparable接口,否则会跑出异常。对于TreeSet判断元素是否重复的标准,也是调用元素从Comparable接口继承而来compareTo方法,如果返回0则是重复元素。Java的常见类都已经实现了Comparable接口
给Person类上添加针对Comparable接口的实现:考虑具体的业务规则,按照类中什么属性进行排序比较
定制排序(在集合中写排序规则)
TreeSet还有一种排序就是定制排序,定制排序时候,需要关联一个 Comparator对象,由Comparator提供排序逻辑
构造器
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
Set<Person> set=new TreeSet<>((obj1, obj2)->{
Person p1=(Person)obj1;
Person p2=(Person)obj2;
return p2.getId().compareTo(p1.getId());
});
for(int i=0;i<10;i++)
set.add(new Person(1L+i, (9-i)+"name"));
set.forEach(System.out::println);