59 java集合和泛型

java集合和泛型"/>

59 java集合和泛型

文章目录

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

Set实现类

1. HashSet 【重点】 :

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

2. TreeSet：

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

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

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

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

3. 基本概念:

   • 若关键字为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 增强forSystem.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")); //falseSystem.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 增强forSystem.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)); //trueSystem.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;}@Overridepublic String toString() {return "Person{" +"name='" + name + '\'' +", age=" + age +'}';}//自动生成的@Overridepublic 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);}//自动生成的@Overridepublic int hashCode() {return Objects.hash(name, age);}/* 自己写的@Overridepublic int hashCode() {int i1 = this.name.hashCode();int i2 = this.name.hashCode();return i1 + i2;}@Overridepublic 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