59 java集合和泛型_9 _Set实现类 _HashSet

文章目录

• ​​Set实现类​​
• ​​存储结构：哈希表（散列表）​​
• ​​HashSet的使用​​
• ​​HashSet的存储过程​​
• ​​HashSet补充​​

Set实现类

HashSet 【重点】 :

• 基于HashCode计算元素存放位置，实现元素不重复。（存储结构是一个哈希表）
• 当存入元素的哈希码相同时，会调用equals进行确认， 如结果为true, 则拒绝后者存入。

TreeSet：

• 基于排列顺序实现元素不重复。
• 实现了SortedSet接口，对集合元素自动排序。
• 元素对象的类型必须实现Comparable接口，指定排序规则。
• 通过CompareTo方法确定是否为重复元素。

存储结构：哈希表（散列表）

（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的​​数据结构​​。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做​​散列函数​​，存放记录的​​数组​​叫做​​散列表​​。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

基本概念:

• 若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。
• 对不同的关键字可能得到同一散列地址，即k1≠k2，而 f(k1)=f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数**f(k)**和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
• 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

HashSet的使用

代码1:

package com.wlw.collection.set;

import java.util.HashSet;
import java.util.Iterator;

/**
* HashSet 的使用
* 存储结构：哈希表（数组+链表+红黑树（jdk1.8之后））
*/
public class HashSet_Demo01 {
public static void main(String[] args) {

//新建集合
HashSet<String> hashSet = new HashSet<>();

//1.添加
hashSet.add("阿斯顿");
hashSet.add("刘德华");
hashSet.add("护发素");
hashSet.add("阿萨啊");
//hashSet.add("刘德华"); //不会再添加
System.out.println("元素个数："+hashSet.size());
System.out.println(hashSet.toString());

//2.删除
/*
hashSet.remove("护发素");
System.out.println("删除之后，元素个数："+hashSet.size());
*/

//3.遍历
//3.1 增强for
System.out.println("----------3.1 增强for---------");
for (String s : hashSet) {
System.out.println(s);
}

//3.2迭代器
System.out.println("----------3.2迭代器---------");
Iterator<String> iterator = hashSet.iterator();
while (iterator.hasNext()){
String s = iterator.next();
System.out.println(s);
}

//4.判断
System.out.println(hashSet.contains("hhhhh")); //false
System.out.println(hashSet.isEmpty()); //false
}
}
/*
元素个数：4
[阿萨啊, 阿斯顿, 刘德华, 护发素]
----------3.1 增强for---------
阿萨啊
阿斯顿
刘德华
护发素
----------3.2迭代器---------
阿萨啊
阿斯顿
刘德华
护发素
false
false
*/

代码2:

package com.wlw.collection.set;

import java.util.HashSet;
import java.util.Iterator;

/**
* HashSet 的使用
* 存储结构：哈希表（数组+链表+红黑树（jdk1.8之后））
* 存储过程（判断重复依据）：
* （1）根据hashcode计算保存的地址（数组），如果此位置为空，则直接保存，如果不为空，执行第二步
* （2）再执行euqals方法，如果equals方法返回true，则认为重复，不保存，否则形成链表
*/
public class HashSet_Demo02 {
public static void main(String[] args) {

//新建集合
HashSet<Person> hashSet = new HashSet<>();
Person p1 = new Person("刘德华",10);
Person p2 = new Person("林画图",20);
Person p3 = new Person("刘思达",30);

//1.添加
hashSet.add(p1);
hashSet.add(p2);
hashSet.add(p3);
//hashSet.add(p3); //重复，不会再添加

hashSet.add(new Person("刘思达",30));
/*
假如，执行这一条语句，我想让他不加进去（认为和之前p3相同），
就需要在该类型中重写hashCode方法与equals方法,
只重写hashCode方法是不行的
*/

System.out.println("元素个数："+hashSet.size());
System.out.println(hashSet.toString());

//2.删除
/*
//hashSet.remove(p1);
hashSet.remove(new Person("刘德华",10));
//因为重写了hashCode方法与equals方法,所以是能删除掉上面的p1的

System.out.println("删除之后，元素个数："+hashSet.size());
*/

//3.遍历
//3.1 增强for
System.out.println("----------3.1 增强for---------");
for (Person person : hashSet) {
System.out.println(person.toString());
}

//3.2迭代器
System.out.println("----------3.2迭代器---------");
Iterator<Person> iterator = hashSet.iterator();
while (iterator.hasNext()){
Person person = iterator.next();
System.out.println(person.toString());
}
//4.判断
System.out.println(hashSet.contains(p1)); //true
System.out.println(hashSet.isEmpty()); //false
}
}

/*
元素个数：3
[Person{name='林画图', age=20}, Person{name='刘思达', age=30}, Person{name='刘德华', age=10}]
----------3.1 增强for---------
Person{name='林画图', age=20}
Person{name='刘思达', age=30}
Person{name='刘德华', age=10}
----------3.2迭代器---------
Person{name='林画图', age=20}
Person{name='刘思达', age=30}
Person{name='刘德华', age=10}
true
false
*//*
重写了hashCode方法与equals方法
*/
package com.wlw.collection.set;

import java.util.Objects;

public class Person {
private String name;
private int age;

//无参构造
public Person() {
}

//有参构造
public Person(String name, int age) {
this.name = name;
this.age = age;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public int getAge() {
return age;
}

public void setAge(int age) {
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);
}

/* 自己写的
@Override
public int hashCode() {
int i1 = this.name.hashCode();
int i2 = this.name.hashCode();
return i1 + i2;
}

@Override
public boolean equals(Object o) {
//1.判断是否一样
if (this == o){
return true;
}
//2.判断是否为空
if (o == null){
return false;
}
//3.判断是否是Person类型
if(this.getClass() == o.getClass()){

}
if(o instanceof Person){
//4.类型转换
Person p = (Person) o;
//5.比较数据
if(this.name.equals(p.getName()) && this.age == p.getAge()){
return true;
}
}
return false;

}
*/


}

HashSet的存储过程

存储过程（判断重复依据）：

（1）根据hashcode计算保存的地址（数组），如果此位置为空，则直接保存，如果不为空，执行第二步

（2）再执行euqals方法，如果equals方法返回true，则认为重复，不保存，否则形成链表

HashSet补充

hashCode（）重写方法：

@Override
public int hashCode() {
return Objects.hash(name, age);
}

public static int hash(Object... values) {
return Arrays.hashCode(values);
}

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;
}

/*
31 这个数
（1）31是一个质数，可以减少散列冲突
（2）31可以提高执行效率， 31*i = (i << 5)-i