Java学习----Set接口

今日学习内容总结如下：

HashSet类

HashSet类直接实现了Set接口， 其底层其实是包装了一个HashMap去实现的
以需要存储的数据作为map的key值，以常量PRESENT作为value值

private transient HashMap map;
private static final Object PRESENT=new Object();

 HashSet采用HashCode算法来存取集合中的元素，因此具有比较好的读取和查找性能

Set 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 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 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 
		extends HashSet 
		implements Set, Cloneable, Serializable

LinkedHashSet是HashSet的一个子类，LinkedHashSet也根据HashCode的值来决
    定元素的存储位置，但同时它还用一个链表来维护元素的插入顺序，插入的时候即
    要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素

采用双向链表记录添加元素的顺序

LinkedHashMap类中的节点定义

static class Entry extends HashMap.Node {
        		Entry before, after;
		        Entry(int hash, K key, V value, Node next) {
		            super(hash, key, value, next);
		        }
    		}

Set set=new LinkedHashSet<>();
for(int i=0;i<10;i++)
	set.add("str-"+i);
Iterator it=set.iterator();
while(it.hasNext()){
    String tmp=it.next();
    System.out.println(tmp);
}

因为底层采用链表和哈希表的算法。链表保证元素的添加顺序，哈希表保证元素的唯一性

TreeSet类

TreeSet实现了SortedSet接口，顾名思义这是一种排序的Set集合

public class TreeSet 
 			extends AbstractSet 
 			implements NavigableSet, Cloneable, Serializable

数据存储采用的是

private transient NavigableMap m;
 
public interface NavigableMap extends SortedMap

查看jdk源码发现底层是用TreeMap实现的，本质上是一个红黑树原理。正因为它是排序了的，所以相对HashSet来说，TreeSet提供了一些额外的按排序位置访问元素的方法，例如first(), last(), lower(), higher(), subSet(),headSet(), tailSet()

Random r=new Random();
Set lhs=new LinkedHashSet<>(); //用于记录生成的对技术的顺序
Set 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{
    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 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(Comparatorsuper E> comparator) {
        this(new TreeMap<>(comparator));
    }

Set 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);