内江规划建设教育网站,长沙谷歌seo收费,深圳5区发布通知,天助网站#x1f40c;个人主页#xff1a; #x1f40c; 叶落闲庭 #x1f4a8;我的专栏#xff1a;#x1f4a8; c语言 数据结构 javaEE 操作系统 Redis 石可破也#xff0c;而不可夺坚#xff1b;丹可磨也#xff0c;而不可夺赤。 HashSet 一、 HashSet 集合的底层数据结构二… 个人主页 叶落闲庭 我的专栏 c语言 数据结构 javaEE 操作系统 Redis 石可破也而不可夺坚丹可磨也而不可夺赤。 HashSet 一、 HashSet 集合的底层数据结构二、 HashSet 添加元素的过程三、 HashSet 为什么存和取的顺序不一样四、 HashSet 为什么没有索引五、 HashSet 的去重机制 Set 系列集合 无序存取顺序不一致 不重复可以去除重复 无索引没有带索引的方法所以不能使用普通fo循环遍历也不能通过索引来获取元素
一、 HashSet 集合的底层数据结构
HashSet 无序、不重复、无索引HashSet 底层是采用哈希表存储数据的哈希表是一种对于增删改查数据性能都较好的结构哈希表在JDK8之前是由数组链表组成的在JDK8之后是由数组链表红黑树组成的在哈希表中最重要的是哈希值哈希值就是对象的整数表现形式HashSet 在存数据的时候会根据数组长度和哈希值计算出要存入的位置哈希值是根据hashCode()方法计算出来的int型的整数hashCode()方法定义在Object类中所有对象都可以调用默认使用地址值进行计算一般情况下自定义的对象都要重写hashCode()方法利用对象内部的属性值计算哈希值。
int index (数组长度 - 1) 哈希值;对象的哈希值特点 如果没有重写hashCode()方法同一个类创建的不同对象计算出的哈希值是不同的
public class Student {private String name;private int age;public Student() {}public Student(String name, int age) {this.name name;this.age age;}/*** 获取* return name*/public String getName() {return name;}/*** 设置* param name*/public void setName(String name) {this.name name;}/*** 获取* return age*/public int getAge() {return age;}/*** 设置* param age*/public void setAge(int age) {this.age age;}public String toString() {return Student{name name , age age };}
}public static void main(String[] args) {//创建对象//没有重写hashCode方法计算出的哈希值是不同的Student s1 new Student();Student s2 new Student();System.out.println(s1.hashCode());//460141958System.out.println(s2.hashCode());//1163157884}如果已经重写hashcode方法不同的对象只要属性值相同计算出的哈希值就是一样的
public class Student {private String name;private int age;Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Student student (Student) o;return age student.age Objects.equals(name, student.name);}Overridepublic int hashCode() {return Objects.hash(name, age);}public Student() {}public Student(String name, int age) {this.name name;this.age age;}/*** 获取* return name*/public String getName() {return name;}/*** 设置* param name*/public void setName(String name) {this.name name;}/*** 获取* return age*/public int getAge() {return age;}/*** 设置* param age*/public void setAge(int age) {this.age age;}public String toString() {return Student{name name , age age };}
}public static void main(String[] args) {//创建对象//如果已经重写hashcode方法不同的对象只要属性值相同计算出的哈希值就是一样的Student s1 new Student();Student s2 new Student();System.out.println(s1.hashCode());//961System.out.println(s2.hashCode());//961}在小部分情况下不同的属性值或者不同的地址值计算出来的哈希值也有可能一样哈希碰撞
public static void main(String[] args) {//在小部分情况下不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。哈希碰撞System.out.println(abc.hashCode());//96354System.out.println(acD.hashCode());//96354}二、 HashSet 添加元素的过程
HashSet在JDK8以后的底层原理
创建一个默认长度为16默认加载因子为0.75的数组数组名为table根据元素的哈希值跟数组长度计算处应存入的位置
int index (数组长度 - 1) 哈希值;判断当前位置是否为null如果是null则直接存入如果当前位置不是null表示有元素则调用equals()方法与当前位置的属性进行比较 如果相同则舍弃不存 如果不同则存入数组形成链表 JDK8以前新元素存入数组老元素挂在新元素下面形成链表JDK8之后新元素挂在老元素下面形成链表当链表长度大于8且数组长度大于等于64时当前链表会自动转成红黑树如果集合中存储的是自定义对象必须重写 hashCode 和 equals 方法
三、 HashSet 为什么存和取的顺序不一样 HashSet 在遍历的时候是从数组的0索引开始遍历的每个索引下都要遍历该索引下对应的链表当遍历到一个索引这个索引的值为空时会跳过遍历下一个索引该索引下对应有链表时就会遍历这个链表若是红黑树也会遍历这个红黑树按这个原则遍历数组因为某个索引下对应的元素不一定就是存入时的顺序所以HashSet 在存和取时的顺序也不一定相同。 四、 HashSet 为什么没有索引 HashSet 是由数组链表红黑树组成的数组是有索引的但是存在HashSet 中的元素是通过链表或红黑树的形式挂在数组的每个索引下的也就是每个索引可能对应多个元素所以HashSet 不能由索引找到对应的元素。 五、 HashSet 的去重机制 HashSet 是通过HashCode计算出每个元素应该存放的位置然后通过equals方法去比较对象内部的属性值是否一致保证不会出现重复的元素。
