这么做输入文字的网站,wordpress爬虫ca,做外包的网站,情侣做记录网站源码我们区分list和set集合的标准是三个#xff1a;有无顺序#xff0c;可否重复#xff0c;有无索引。
list的答案是#xff1a;有顺序#xff0c;可重复#xff0c;有索引。这也就是ArrayList和LinkedList的共性
set的答案是#xff1a;顺序内部再区分,不可以重复#xf…
我们区分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.7512元素满时添加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可排序*/SetString Hash new HashSet();SetString LinkedHash new LinkedHashSet();SetString TreeSet new TreeSet();Hash.add(张三);Hash.add(李四);Hash.add(王五);//1.ForEachlambda表达式遍历Hash.forEach(s-System.out.println(s));//2.加强for循环遍历for(String s:Hash){System.out.println(s);}//3.迭代器遍历IteratorString 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 s1new Student(小明,23);Student s2new Student(小明,23);//2.如果没有重写hashcode s1和s2返回的哈希值是不一样的System.out.println(s1.hashCode());System.out.println(s2.hashCode());//你会发现在Student重写hashcode后的返回哈希值是一样的//这里的重写我们用altinsert的便捷键来进行重写//哈希碰撞的特例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.7512元素满时添加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.7512元素满时添加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);}
