集合

3-set接口

2021-07-09 315 0

简介 HashSet、LinkedHashSet、TreeSet实现类的具体介绍

1. set接口

|----Collection接口：单列集合，用来存储一个一个的对象

|----Set接口：存储无序的、不可重复的数据 -->高中讲的“集合”

|----HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值

|----LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历

对于频繁的遍历操作，LinkedHashSet效率高于HashSet.

|----TreeSet：其中的元素是同一个类的对象，可以按照对象的指定属性进行排序。

Set接口中没有额外定义新的方法，使用的都是Collection中声明过的方法。

要求：

向Set(主要指：HashSet、LinkedHashSet)中添加的数据，其所在的类一定要重写hashCode()和equals()

重写的hashCode()和equals()尽可能保持一致性：相等的对象必须具有相等的散列值

重写两个方法的小技巧：对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。基本上都是使用工具生成，一般不建议自己手动实现。

List存储的数据是有序的，可重复的，set存储的数据是无序的不可重复的

一、Set：存储无序的、不可重复的数据

以HashSet为例说明：

1. 无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。哈希值决定了数据存储的位置。

list是有序的，意思是存储数据是按顺序存储的，一个挨着一个，相邻的数据元素的内存地址也是连续的。也就是逻辑上相邻，物理上也相邻。

而HashSet存储的位置不是按顺序来的，也就是其在内存中不是按顺序存储的。

2. 不可重复性：保证添加的元素按照equals()判断时，不能跟已有的元素相同。相同的元素，只能添加一个。

二、添加元素的过程：以HashSet为例：

我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，

此哈希值接着通过某种算法（散列函数、哈希函数）计算出在HashSet底层数组中的存放位置（即为：索引位置），

判断数组此位置上是否已经有元素：

如果此位置上没有其他元素，则元素a添加成功。 --->情况1

如果此位置上有其他元素b(或以链表形式存在的多个元素），则比较元素a与元素b的hash值：

如果hash值不相同，则元素a添加成功。--->情况2

如果hash值相同，进而需要调用元素a所在类的equals()方法：

equals()返回true,元素a添加失败（说明a和b是相同的）

equals()返回false,则元素a添加成功。--->情况3（hash值虽然相同，但是元素可能不同，哈希碰撞的情况）

对于添加成功的情况2和情况3而言：元素a 与已经存在指定索引位置上数据以链表的方式存储。

jdk 7 :元素a放到数组中，指向原来的元素。

jdk 8 :原来的元素在数组中保持不动，在链表的末尾添加a

总结：七上八下

HashSet底层：数组+链表的结构。

//SetItfTest.java
package com.ylaihui.setitf;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Objects;
class Order{
int id;
double price;
public Order() {
}
@Override
public String toString() {
return "Order{" +
"id=" + id +
", price=" + price +
'}';
}
public Order(int id, double price) {
this.id = id;
this.price = price;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Order order = (Order) o;
return id == order.id &&
Double.compare(order.price, price) == 0;
}
@Override
public int hashCode() {
return Objects.hash(id, price);
}
}
public class SetItfTest {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add(111);
hashSet.add(222);
hashSet.add("ylaihui");
hashSet.add("ylaihui");
hashSet.add(new Order(111,100.50));
hashSet.add(new Order(111,100.50));
Iterator iterator = hashSet.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
/*
ylaihui
Order{id=111, price=100.5}
222
111
*/

2. 为什么在hashCode方法中会出现31这个数？

以Eclipse/IDEA为例，在自定义类中可以调用工具自动重写equals和hashCode。

问题：为什么用Eclipse/IDEA复写hashCode方法，有31这个数字？

public static int hashCode(Object a[]) {
if (a == null)
return 0;
int result = 1;
for (Object element : a)
result = 31 * result + (element == null ? 0 : element.hashCode());
return result;
}

 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大，所谓的“冲突”就越少，查找起来效率也会提高。（减少冲突）

 31可以由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。（提高算法效率，2的多少次方，这样的计算，效率高）

 并且31只占用5bits,相乘造成数据溢出的概率较小。

 31是一个质数，质数作用就是如果我用一个数字来乘以这个素数，那么最终出来的结果只能被素数本身和被乘数还有1来整除！ (减少冲突)

最终选择了31这个数

3. LinkedHashSet的使用

LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据，对于频繁的遍历操作，LinkedHashSet效率高于HashSet

//LinkedHashSetTest.java
package com.ylaihui.setitf;
import java.util.LinkedHashSet;
import java.util.Objects;
class Book{
int id;
double price;
public Book() {
}
@Override
public String toString() {
return "Book{" +
"id=" + id +
", price=" + price +
'}';
}
public Book(int id, double price) {
this.id = id;
this.price = price;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Book book = (Book) o;
return id == book.id &&
Double.compare(book.price, price) == 0;
}
@Override
public int hashCode() {
return Objects.hash(id, price);
}
}
public class LinkedHashSetTest {
public static void main(String[] args) {
LinkedHashSet set = new LinkedHashSet();
set.add(111);
set.add(222);
set.add("ylaihui");
set.add("ylaihui");
set.add(new Order(111,100.50));
set.add(new Order(111,100.50));
for (Object o : set) {
System.out.println(o);
}
}
}
/*
111
222
ylaihui
Order{id=111, price=100.5}
添加的顺序与遍历的顺序一致，因为底层加了一个双向的链表
*/

4. TreeSet的使用

TreeSet 是 SortedSet 接口的实现类， TreeSet 可以确保集合元素处于排序状态。

TreeSet底层使用红黑树结构存储数据

TreeSet 两种排序方法：自然排序和定制排序。默认情况下， TreeSet 采用自然排序

 TreeSet和TreeMap采用红黑树的存储结构

 特点：有序，查询速度比List快

5. TreeSet的自然排序

自然排序： TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系，然后将集合元素按升序(默认情况)排列

如果试图把一个对象添加到 TreeSet 时，则该对象的类必须实现 Comparable接口。

实现 Comparable 的类必须实现 compareTo(Object obj) 方法，两个对象即通过compareTo(Object obj) 方法的返回值来比较大小。

 Comparable 的典型实现：

BigDecimal、 BigInteger 以及所有的数值型对应的包装类：按它们对应的数值大小进行比较

Character：按字符的 unicode值来进行比较

Boolean： true 对应的包装类实例大于 false 对应的包装类实例

String：按字符串中字符的 unicode 值进行比较

Date、 Time：后边的时间、日期比前面的时间、日期大

向 TreeSet 中添加元素时，只有第一个元素无须比较compareTo()方法，后面添加的所有元素都会调用compareTo()方法进行比较，也就是向TreeSet中添加的第一个元素决定了后续可添加的每个元素的类型。

因为只有相同类的两个实例才会比较大小，所以向 TreeSet 中添加的应该是同一个类的对象。

对于 TreeSet 集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过 compareTo(Object obj) 方法比较返回值。

当需要把一个对象放入 TreeSet 中，重写该对象对应的 equals() 方法时，应保证该方法与 compareTo(Object obj) 方法有一致的结果：如果两个对象通过equals() 方法比较返回 true，则通过 compareTo(Object obj) 方法比较应返回 0。否则，让人难以理解。

如果自定义类不实现Comparable接口那么该类的对象无法放入TreeSet中： java.lang.ClassCastException: com.ylaihui.setitf.Person cannot be cast to java.lang.Comparable

//TreeSetTest1.java
package com.ylaihui.setitf;
import java.util.TreeSet;
public class TreeSetTest1 {
public static void main(String[] args) {
TreeSet set = new TreeSet();
// error: 只能添加相同类的对象
//set.add(111);
//set.add(222);
//set.add("aa");
set.add("y");
set.add("lai");
set.add("hui");
for (Object obj : set) {
System.out.println(obj);
}
}
}

//TreeSetTest2.java
package com.ylaihui.setitf;
import java.util.Objects;
import java.util.TreeSet;
class Person{
String name;
int age;
public Person() {
}
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return age == person.age &&
Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}
public class TreeSetTest2 {
public static void main(String[] args) {
// java.lang.ClassCastException: com.ylaihui.setitf.Person cannot be cast to java.lang.Comparable
// 放入TreeSet中的对象要求是可比较的，需要实现Comparable接口
TreeSet set = new TreeSet();
set.add(new Person("Andy",6));
set.add(new Person("Caddy",12));
set.add(new Person("ylaihui",33));
set.add(new Person("Jim",22));
}
}