[数据结构]HashSet与LinkedHashSet的底层原理学习心得

我们区分list和set集合的标准是三个：有无顺序，可否重复，有无索引。
list的答案是：有顺序，可重复，有索引。这也就是ArrayList和LinkedList的共性
set的答案是：顺序内部再区分,不可以重复，无索引
我们接下来可以通过顺序的标准在set集合中进行再区分：
1.HashSet无顺序
2.LinkedHashSet有顺序
3.TreeSet可排序

Hashset的底层是哈希表->一种对于增删改查数据性能较好的数据结构
分析哈希表的构成：
Before JDK8:数组+链表
After JDK8:数组+链表+红黑树
哈希值：哈希表的灵魂所在->对象的整数表现形式
我们可以使用Object类中的hashcode方法来计算某个对象,运算结果是int类型的整数
问题来了：我们会拿对象的什么来进行计算？答案是：地址值
举个简单的例子：
现在有一个对象的地址值是0x0011 我通过这个地址值算出来一个哈希值:6794651616
然后我们在哈希表内添加元素的时候，注意，是在有索引的哈希表内添加元素的时候
这里我们避免一个认识误区:Hashset是没有索引的，但是构成Hashset的底层数据结构-哈希表是有索引的
我们将添加的元素在哈希表上的索引index的公式给出：
int index=(数组长度-1)&哈希值; 这里又证明了先前我们提出的哈希表底层原理：数组+链表+红黑树（JDK8以前）
那么此时我们会有一个问题：在Object类下的hashcode和复写后的hashcode产生的哈希值是一样的么？
答案是不一样的->
如果没有重写hashcode方法:不同对象计算出的哈希值是不同的
如果已经重写hashcode方法：不同的对象只要属性值相同，计算出的哈希值是一样的
这句话有点晦涩难懂，我们举个例子：
我需要构建一个学生信息管理系统，需要添加两个学生的名字进去 两个"小明"
如果我使用了object的hashcode 那么计算出的哈希值两次是不一样的 于是两个小明会被分配到不同的空间
但是如果我使用了重写后的hashcode 那么计算出的哈希值两次都是一样的 小明都会被储存到同一块区域当中去
但是注意：在小部分的情况下 不同的属性值或者不同的属性值计算机出的哈希值是一样的
这样的情况就是：哈希碰撞。因为int的范围是-21E到+21E 但是我现在创建50E个对象
一点有8E对象的哈希值是一样的 这样就会发生哈希碰撞 但是这样的极端概率是不高的

1.首先创建一个默认长度为16 默认加载因子是0.75的数组 数组名叫table
2.根据元素的哈希值跟数组的长度进行计算 计算出当前元素应存入的位置
公式: int index= (数组元素-1)&哈希值; 注意&是按位与
3.判断当前这个index对应的位置是否是Null 如果是null直接存入
4.如果当前位置不是Null 就说明已经有元素了 调用equals方法来比较属性值
例子:比如我要在Index为4的位置存入一个新的数据 但是4位置已经有数据了
5.如果属性值是一样：不存属性值不一样：存入数组，形成链表（JDK8以前 新的元素存入数组 老的元素挂在新元素下面）(JDK8以后 新元素挂在老元素下面)加载因子是什么：数组的扩容时机：16x0.75=12元素满时添加6.红黑树的出现：我们先前谈到了在哈希表的相同位置添加元素会触发equals方法然后新的数据会挂载在哈希表的下面，其中红黑树就是一种jdk8以后产生的新挂载方法JDK8满足条件：a.链表长度超过8 b.数组长度>=647.集合中储存的是自定义对象，必须要重写hashcode和equals方法前者的目的是为了属性值取代地址值，后者的目的是用属性值去进行比较我们构造链表和树的目的就是为了减少哈希碰撞Hashset为什么没有索引 Hash表上挂着许多的链表和红黑树 无法准确的表示具体的索引 因为一个index上可以挂着红黑树和链表 你如何确定二者的索引呢?学习问答题：Q1:Hashset的集合的底层数据结构是什么样的答案：HashTable（散列表）在JDK8以前 HashTable由数组和链表构成的 在JDK8以后由数组 链表 红黑树构成一个HashTable的所谓索引也就是Hashbucket（哈希桶），每一个哈希桶上可以挂载链表和红黑树Q2:Hashset添加元素的过程是如何的答案：如果哈希值对应的Hashbucket为Null 直接添加 else 再调用equals进行判断 一样就不存 不一样就存Q3 Hashset为什么取和存的顺序不一样答案：我遍历一个hashset其实是从hashtable的序号为0的hashbucket开始的 但是我存入一个元素到hashbucket是根据hashcode算出来的读取和存入执行的过程是不一样的Q4:HashSet为什么没有索引：答案:使用到了链表和红黑树挂在hashbucket上面 过于复杂无法用索引表示Q5:HashSet是用什么机制去保证去重复的？答案：重写后的equals方法————————————————————————————————————————————
LinkedHashSet底层原理
有序，不重复，无索引
底层数据结构：哈希表+链表

import java.util.*;public class Main{public static void main(String[] args){/*我们区分list和set集合的标准是三个：有无顺序，可否重复，有无索引。list的答案是：有顺序，可重复，有索引。这也就是ArrayList和LinkedList的共性set的答案是：顺序内部再区分,不可以重复，无索引我们接下来可以通过顺序的标准在set集合中进行再区分：1.HashSet无顺序2.LinkedHashSet有顺序3.TreeSet可排序*/Set<String> Hash = new HashSet<>();Set<String> LinkedHash = new LinkedHashSet<>();Set<String> TreeSet = new TreeSet<>();Hash.add("张三");Hash.add("李四");Hash.add("王五");//1.ForEach+lambda表达式遍历Hash.forEach(s->System.out.println(s));//2.加强for循环遍历for(String s:Hash){System.out.println(s);}//3.迭代器遍历Iterator<String> it = Hash.iterator();while(it.hasNext()){System.out.println(it.next());}//现在我们开始系统学习set,第一课：Hashset/*Hashset的底层是哈希表->一种对于增删改查数据性能较好的数据结构分析哈希表的构成：Before JDK8:数组+链表After JDK8:数组+链表+红黑树哈希值：哈希表的灵魂所在->对象的整数表现形式我们可以使用Object类中的hashcode方法来计算某个对象,运算结果是int类型的整数问题来了：我们会拿对象的什么来进行计算？答案是：地址值举个简单的例子：现在有一个对象的地址值是0x0011 我通过这个地址值算出来一个哈希值:6794651616然后我们在哈希表内添加元素的时候，注意，是在有索引的哈希表内添加元素的时候这里我们避免一个认识误区:Hashset是没有索引的，但是构成Hashset的底层数据结构-哈希表是有索引的我们将添加的元素在哈希表上的索引index的公式给出：int index=(数组长度-1)&哈希值; 这里又证明了先前我们提出的哈希表底层原理：数组+链表+红黑树（JDK8以前）那么此时我们会有一个问题：在Object类下的hashcode和复写后的hashcode产生的哈希值是一样的么？答案是不一样的->如果没有重写hashcode方法:不同对象计算出的哈希值是不同的如果已经重写hashcode方法：不同的对象只要属性值相同，计算出的哈希值是一样的这句话有点晦涩难懂，我们举个例子：我需要构建一个学生信息管理系统，需要添加两个学生的名字进去 两个"小明"如果我使用了object的hashcode 那么计算出的哈希值两次是不一样的 于是两个小明会被分配到不同的空间但是如果我使用了重写后的hashcode 那么计算出的哈希值两次都是一样的 小明都会被储存到同一块区域当中去但是注意：在小部分的情况下 不同的属性值或者不同的属性值计算机出的哈希值是一样的这样的情况就是：哈希碰撞。因为int的范围是-21E到+21E 但是我现在创建50E个对象一点有8E对象的哈希值是一样的 这样就会发生哈希碰撞 但是这样的极端概率是不高的*///1.创建一个对象Student s1=new Student("小明",23);Student s2=new Student("小明",23);//2.如果没有重写hashcode s1和s2返回的哈希值是不一样的System.out.println(s1.hashCode());System.out.println(s2.hashCode());//你会发现在Student重写hashcode后的返回哈希值是一样的//这里的重写我们用alt+insert的便捷键来进行重写//哈希碰撞的特例：System.out.println("abc".hashCode());System.out.println("acD".hashCode());//Hashcode在JDK8以前的底层原理/*1.首先创建一个默认长度为16 默认加载因子是0.75的数组 数组名叫table2.根据元素的哈希值跟数组的长度进行计算 计算出当前元素应存入的位置公式: int index= (数组元素-1)&哈希值; 注意&是按位与3.判断当前这个index对应的位置是否是Null 如果是null直接存入4.如果当前位置不是Null 就说明已经有元素了 调用equals方法来比较属性值例子:比如我要在Index为4的位置存入一个新的数据 但是4位置已经有数据了5.如果属性值是一样：不存属性值不一样：存入数组，形成链表（JDK8以前 新的元素存入数组 老的元素挂在新元素下面）(JDK8以后 新元素挂在老元素下面)加载因子是什么：数组的扩容时机：16x0.75=12元素满时添加6.红黑树的出现：我们先前谈到了在哈希表的相同位置添加元素会触发equals方法然后新的数据会挂载在哈希表的下面，其中红黑树就是一种jdk8以后产生的新挂载方法JDK8满足条件：a.链表长度超过8 b.数组长度>=647.集合中储存的是自定义对象，必须要重写hashcode和equals方法前者的目的是为了属性值取代地址值，后者的目的是用属性值去进行比较我们构造链表和树的目的就是为了减少哈希碰撞Hashset为什么没有索引 Hash表上挂着许多的链表和红黑树 无法准确的表示具体的索引 因为一个index上可以挂着红黑树和链表 你如何确定二者的索引呢?学习问答题：Q1:Hashset的集合的底层数据结构是什么样的答案：HashTable（散列表）在JDK8以前 HashTable由数组和链表构成的 在JDK8以后由数组 链表 红黑树构成一个HashTable的所谓索引也就是Hashbucket（哈希桶），每一个哈希桶上可以挂载链表和红黑树Q2:Hashset添加元素的过程是如何的答案：如果哈希值对应的Hashbucket为Null 直接添加 else 再调用equals进行判断 一样就不存 不一样就存Q3 Hashset为什么取和存的顺序不一样答案：我遍历一个hashset其实是从hashtable的序号为0的hashbucket开始的 但是我存入一个元素到hashbucket是根据hashcode算出来的读取和存入执行的过程是不一样的Q4:HashSet为什么没有索引：答案:使用到了链表和红黑树挂在hashbucket上面 过于复杂无法用索引表示Q5:HashSet是用什么机制去保证去重复的？答案：重写后的equals方法————————————————————————————————————————————LinkedHashSet底层原理有序，不重复，无索引底层数据结构：哈希表+链表*/}
}

 1.首先创建一个默认长度为16 默认加载因子是0.75的数组 数组名叫table2.根据元素的哈希值跟数组的长度进行计算 计算出当前元素应存入的位置公式: int index= (数组元素-1)&哈希值; 注意&是按位与3.判断当前这个index对应的位置是否是Null 如果是null直接存入4.如果当前位置不是Null 就说明已经有元素了 调用equals方法来比较属性值例子:比如我要在Index为4的位置存入一个新的数据 但是4位置已经有数据了5.如果属性值是一样：不存属性值不一样：存入数组，形成链表（JDK8以前 新的元素存入数组 老的元素挂在新元素下面）(JDK8以后 新元素挂在老元素下面)加载因子是什么：数组的扩容时机：16x0.75=12元素满时添加6.红黑树的出现：我们先前谈到了在哈希表的相同位置添加元素会触发equals方法然后新的数据会挂载在哈希表的下面，其中红黑树就是一种jdk8以后产生的新挂载方法JDK8满足条件：a.链表长度超过8 b.数组长度>=647.集合中储存的是自定义对象，必须要重写hashcode和equals方法前者的目的是为了属性值取代地址值，后者的目的是用属性值去进行比较我们构造链表和树的目的就是为了减少哈希碰撞Hashset为什么没有索引 Hash表上挂着许多的链表和红黑树 无法准确的表示具体的索引 因为一个index上可以挂着红黑树和链表 你如何确定二者的索引呢?学习问答题：Q1:Hashset的集合的底层数据结构是什么样的答案：HashTable（散列表）在JDK8以前 HashTable由数组和链表构成的 在JDK8以后由数组 链表 红黑树构成一个HashTable的所谓索引也就是Hashbucket（哈希桶），每一个哈希桶上可以挂载链表和红黑树Q2:Hashset添加元素的过程是如何的答案：如果哈希值对应的Hashbucket为Null 直接添加 else 再调用equals进行判断 一样就不存 不一样就存Q3 Hashset为什么取和存的顺序不一样答案：我遍历一个hashset其实是从hashtable的序号为0的hashbucket开始的 但是我存入一个元素到hashbucket是根据hashcode算出来的读取和存入执行的过程是不一样的Q4:HashSet为什么没有索引：答案:使用到了链表和红黑树挂在hashbucket上面 过于复杂无法用索引表示Q5:HashSet是用什么机制去保证去重复的？答案：重写后的equals方法————————————————————————————————————————————LinkedHashSet底层原理有序，不重复，无索引底层数据结构：哈希表+链表

import java.util.Objects;public class Student
{private String name;private int age;public Student() {}@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(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 + "}";}
}

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