百度网站降权,游戏网站设计论文,php网站开发 vip,怎么自己做淘宝网站吗#x1f4a5;注#x1f4a5; #x1f497;阅读本博客需备的前置知识如下#x1f497; #x1f31f;数据结构常识#x1f31f;#x1f449;1️⃣八种数据结构快速扫盲#x1f31f;Java集合常识#x1f31f;#x1f449;2️⃣Java单列集合扫盲 ⭐️本博客知识点收录于… 注 阅读本博客需备的前置知识如下 数据结构常识1️⃣八种数据结构快速扫盲Java集合常识2️⃣Java单列集合扫盲 ⭐️本博客知识点收录于⭐️《JavaSE系列教程》:—11【泛型、Map、异常】 文章目录二、Set集合2.1 Set集合概述2.2 HashSet 集合2.2.1 HashSet数据结构1HashSet简介2Hash冲突13Hash冲突24HashSet底层存储原理5HashSet特点总结2.2.2 HashSet去重原理2.2.3 HashSet存储测试1hash冲突情况12hash冲突情况2二、Set集合
2.1 Set集合概述
Set接口和List接口一样继承与Collection接口也是一个单列集合Set集合中的方法和Collection基本一致并没有对Collection接口进行功能上的扩充只是底层实现的方式不同了采用的数据结构不一样
Set集合体系结构 2.2 HashSet 集合
2.2.1 HashSet数据结构
1HashSet简介
HashSet是Set接口的一个实现类它所存储的元素是不可重复的并且元素都是无序的即存取顺序不一致。
HashSet底层数据结构在JDK8做了一次重大升级JDK8之前采用的是Hash表也就是数组链表来实现到了JDK8之后采用数组链表红黑树来实现 Tips关于红黑树我们暂时理解为红黑树就是一颗平衡的二叉树即使他不是绝对平衡 HashSet简单使用
package com.dfbz.demo01;import java.util.HashSet;/*** author lscl* version 1.0* intro:*/
public class Demo01 {public static void main(String[] args) {//创建 Set集合HashSet set new HashSetString();//添加元素set.add(湖北);set.add(河北);set.add(河北); // HashSet带有去重特点,河北已经存储过了,不会再存储System.out.println(set); // [河北, 湖北]}
}HashSet判断两个元素是否重复的依据是什么呢下面案例代码HashSet将会存储几个元素呢
示例代码
package com.dfbz.demo01;import java.util.HashSet;/*** author lscl* version 1.0* intro:*/
public class Demo01 {public static void main(String[] args) {//创建 Set集合HashSetString set new HashSet();//添加元素set.add(new String(河北));set.add(湖北);set.add(河北);set.add(湖北);System.out.println(set.size()); // ?System.out.println(--------------------);HashSetA set2 new HashSet();set2.add(new A());set2.add(new A());System.out.println(set2.size()); // ?}
}class A{}要探究HashSet的去重原理我们需要继续往下看
2Hash冲突1
我们知道hash表数据结构的特点是根据元素的hash值来对数组的长度取余最终计算出元素所要存储的位置Object类中有一个特殊的方法hashCode()该方法被native关键字修饰不是采用Java语言实现
public native int hashCode()获取该对象的hash值默认情况下根据该对象的内存地址值来计算
默认情况下对象的hash值是根据对象的内存地址值来计算但是这种hash算法并不是特别完美有时候不同的两个对象内存地址值不一致计算出来的hash值可能会一样我们把这种情况称为hash冲突。尽管这种情况非常少但依旧存在
下面是String类对hashCode代码的实现
public int hashCode() {int h hash;if (h 0 value.length 0) {char val[] value;for (int i 0; i value.length; i) {h 31 * h val[i];}hash h;}return h;
}String默认情况下是获取每一个字符的ASCII码来参与hashCode的计算在上面算法中AB和BA得出的hashCode是不一致的有效的解决了一定情况下的hash冲突问题但是hash算法不能保证在所有情况下hash都能唯一
例如Aa和BB的hashCode却是一样的这种造成了Hash冲突问题
Aa:
h 31*065
h 31*6597
h 2112
BB:
h 31*066
H 31*6666
h 2112示例代码
package com.dfbz.demo01;/*** author lscl* version 1.0* intro:*/
public class Demo01 {public static void main(String[] args) {System.out.println(Aa.hashCode()); // 2112System.out.println(BB.hashCode()); // 2112}
}通过String类对hashCode的实现可以看出来hash算法并不能绝对的保证两个不同的对象算出来的hash值不一样当hash冲突时HashSet将会调用当前对象的equlas方法来比较两个对象是否一致如果一致则不存储该元素 3Hash冲突2
假设数组的长度为9当元素1的hash值为6元素2的hash值为15计算的数组槽位都是6同样的那么这个时候也会触发hash冲突问题
Integer对hashCode的实现
Override
public int hashCode() {return Integer.hashCode(value);
}Integer.hashCode()
public static int hashCode(int value) {// 就是返回元素本身return value;
}示例代码
package com.dfbz.demo01;/*** author lscl* version 1.0* intro:*/
public class Demo10 {public static void main(String[] args) {System.out.println(new Integer(15).hashCode()); // 15System.out.println(new Integer(6).hashCode()); // 6}
}TipsInteger的hashCode就是本身数值 HashSet存储时的Hash冲突情况假设散列表中的数组长度为9 发生上面这种Hash冲突时HashSet采用拉链法将新增的元素添加到上一个元素之后形成链表
需要注意的是
1hashCode一致的两个对象不能说明两个对象一定相同因为可能会造成hash冲突例如上面的Aa和BB2但是如果hashCode不同则一定能说明这两个对象肯定不同因为同一个对象计算的hashCode永远一样
因此在hash冲突的第二种情况下并不需要调用equals来去重而是采用拉链法直接将新添加的元素链在后面形成链表
4HashSet底层存储原理
我们前面了解过HashSet底层采用的是散列表这种数据结构数组链表并且在JDK1.8对传统的散列表进行了优化增加了红黑树来优化链表查询慢的情况在默认情况下HashSet中散列表的数组长度为16并通过负载因子来控制数组的长度HashSet中负载因子默认为0.75
负载因子HashSet中存储的元素/数组的长度由此可以得出当HashSet中的元素个数为12个时16*0.7512将进行数组的扩容默认情况下将会扩容到原来的2倍数组长度将会变为32由公式可以推算出下一次HashSet数组扩容时元素个数将为32*0.7524以此类推…
负载因子是控制数组扩容的一个重要参数并且HashSet允许我们在创建时指定负载因子和数值的默认容量大小
HashSet底层存储如图所示 上述图中是一个hash表数据结构数组链表也是JDK8之前的HashSet底层存储结构或者说还未达到阈值转换为红黑树的时候
当存储的元素越来越多hash也越来越多时势必造成链表长度非常长查找元素时性能会变得很低在JDK8中当链表长度到达指定阈值8并且数组容量达到了64时将链表转换为红黑树这样大大降低了查询的时间
如图所示 5HashSet特点总结
1存取无序元素唯一先比较hashCode 1Hash冲突情况1hash值直接冲突了当hash冲突时再比较equalsequals返回true则不存2Hash冲突情况2hash值没有冲突但是%数组的长度得到槽位冲突了使用拉链法形成链表 2底层采用Hash表数据结构当数组长度大于等于64并且链表长度大于等于8时链表将会转换为红黑树当长度降到6时将会重新转换为链表3HashSet默认数组长度为16默认的负载因子为0.754每次数组扩容时默认扩容到原来的2倍
2.2.2 HashSet去重原理
前面在分析hash冲突时就得出了结论HashSet保证元素唯一性的方式依赖于hashCode与equals方法。
来解释我们之前的问题
package com.dfbz.demo01;import java.util.HashSet;/*** author lscl* version 1.0* intro:*/
public class Demo01 {public static void main(String[] args) {//创建 Set集合HashSetString set new HashSet();//添加元素set.add(new String(河北));set.add(河北);System.out.println(set.size()); // ?}
}分析
HashSet在存储元素时都会调用对象的hashCode()方法计算该对象的hash值如果hash值与集合中的其他元素一样则调用equals方法对冲突的元素进行对比如果equals方法返回true说明两个对象是一致的HashSet并不会存储该对象反之则存储该元素
一般情况下不同对象的hash值计算出来的结果是不一样的但还是有某些情况下不同一个对象的hash值计算成了同一个这种情况我们称为hash冲突当hash冲突时HashSet会调用equals方法进行对比默认情况下equals方法对比的是对象内存地址值因此如果对象不是同一个equals返回的都是false 另外Java中的HashSet还进行了优化如果两个字符串都是存储在常量池那么直接在常量池中进行判断不需要调用equals来判断是否重复
示例代码
package com.dfbz.demo01;import java.util.HashSet;/*** author lscl* version 1.0* intro:*/
public class Demo02 {public static void main(String[] args) {//创建 Set集合HashSetString set new HashSet();set.add(河北);/*存储第二个河北时,hashSet发现两个hashCode一致并且都是存储在常量池,因此都不需要调用equals来判断这个元素是否存在hashSet*/set.add(河北);System.out.println(set.size()); // 2}
}2.2.3 HashSet存储测试
1hash冲突情况1
HashSet的去重原理是依靠对象的hashCode和equals方法来决定是否要存储这个对象的如果不同的两个对象其hashCode是不同的即使hash冲突了equals也不可能相同默认情况下Object中的equals比较是两个对象的内存地址值
但是在实际开发中地址值并不是我们用来判断两个对象是否相等的依据我们的习惯是对象中的属性相等即判断两个对象是同一个对象
定义一个Person类
package com.dfbz.demo01;/*** author lscl* version 1.0* intro:*/
public class Person {private String name;private Integer age;Overridepublic String toString() {return Person{ name name \ , age age };}public Person() {}public Person(String name, Integer age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public Integer getAge() {return age;}public void setAge(Integer age) {this.age age;}
}测试类
package com.dfbz.demo01;import java.util.HashSet;
import java.util.Set;/*** author lscl* version 1.0* intro:*/
public class Demo02 {public static void main(String[] args) {Set persons new HashSet();persons.add(new Person(小灰, 20));persons.add(new Person(小灰, 20));System.out.println(persons.size()); // 2}
}默认情况下hashCode的值是根据对象的内存地址值计算的hashCode应该不一样即使hashCode一样hash冲突调用equals返回值也是false因为equlas默认的比较规则是比较两个对象的内存地址值
但是我们在实际开发中即使new了两个对象如果里面的属性是完全一样的我们就认为两个对象是同一个对象HashSet应该帮我们去除这样的重复对象
我们可以重写hashCode和equals方法
Override
public boolean equals(Object o) {System.out.println(equals执行了...);// 为了测试,这样固定死是毫无意义的return false;
}Override
public int hashCode() {System.out.println(hashCode执行了...);// 为了测试,这样固定死是毫无意义的return 1;
}测试代码
package com.dfbz.demo01;import java.util.HashSet;
import java.util.Set;/*** author lscl* version 1.0* intro:*/
public class Demo02 {public static void main(String[] args) {Set persons new HashSet();persons.add(new Person(小灰, 20));persons.add(new Person(小蓝, 18));System.out.println(persons.size()); // 1}
}运行结果 分析
1存储第一个Person对象时调用这个Person对象的hashCode方法得出1并将其存储起来
2存储第二个Person对象时调用这个Person对象的hashCode方法得出1发现集合中已经有了hashCode为1的对象因此调用Person对象的equals方法将冲突了的Person对象传入第一次添加的那个Person对象然后equals方法返回的是true因此不存这个Person对象第二个Person对象最终persons.size()为1
真正的hashCode与equals的方法内部逻辑应该是相同属性的对象的hashCode应该是一样的也就是说hashCode应该根据对象属性来计算并且equals对比的应该是对象属性的值
使用idea快捷键altinsert
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3WT8GGut-1677985759628)(media/96.png)]
一直回车生成hashCode和equals方法
Override
public boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Person person (Person) o;return Objects.equals(name, person.name) Objects.equals(age, person.age);
}Override
public int hashCode() {return Objects.hash(name, age);
}此时再执行测试类 将Person属性都改为一样的 2hash冲突情况2
当hashCode不一样但是%数组的长度得到的槽位是一样时也会产生hash冲突但是这种hash冲突并不需要调用equals来判断而是直接使用拉链法拼接在上一个元素的后面形成链表
示例代码
package com.dfbz.demo01;import java.util.HashSet;/*** author lscl* version 1.0* intro:*/
public class Demo01 {public static void main(String[] args) {HashSetA set new HashSet();set.add(new A(1)); // 1 % 16 1set.add(new A(17)); // 17 % 16 1System.out.println(set);}
}class A {private Integer num;Overridepublic boolean equals(Object o) {System.out.println(equals调用了...);return false;}Overridepublic int hashCode() {return this.num;}public A(Integer num) {this.num num;}
}运行程序发现并没有调用equals
