Set 接口的实现类 HashSet 和 LinkedHashSet介绍

2020-11-19 0 By admin

二、HashSet中元素的添加过程

HashSet是Set 接口的典型实现,大多数时候使用Set 集合时都使用这个实现类。
HashSet按 Hash 算法来存储集合中的元素,因此具有很好的存取、查找、删除性能。

2.1、HashSet具有的特点

  1. 不能保证元素的排列顺序
  2. HashSet不是线程安全的
  3. 集合元素可以是null

底层也是数组,初始容量为16,当如果使用率超过0.75,(16*0.75=12)就会扩大容量为原来的2倍。(16扩容为32,依次为64,128…等)

2.2、HashSet 集合判断两个元素相等的标准

两个对象通过hashCode() 方法比较相等,并且两个对象的equals()方法返回值也相等。
对于存放在Set容器中的对象,对应的类一定要重写equals()和hashCode(Object obj)方法,以实现对象相等规则。即:“相等的对象必须具有相等的散列码”。

2.3、添加元素的过程:以HashSet为例

我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法,计算元素a的哈希值,
此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置(即为:索引位置),
  判断数组此位置上是否已经有元素:
    如果此位置上没有其他元素,则元素a添加成功。 --->情况1
    如果此位置上有其他元素b(或以链表形式存在的多个元素),则比较元素a与元素b的hash值:
        如果hash值不相同,则元素a添加成功。--->情况2
        如果hash值相同,进而需要调用元素a所在类的equals()方法:
              equals()返回true,元素a添加失败
              equals()返回false,则元素a添加成功。--->情况3
对于添加成功的情况2和情况3而言:元素a 与已经存在指定索引位置上数据以链表的方式存储。
-----------------元素不同的存储位置:------------
jdk 7 :元素a放到数组中,指向原来的元素。
jdk 8 :原来的元素在数组中,指向元素a
总结:七上八下
HashSet底层:数组+链表的结构。
HashSet底层:数组+链表的结构。

三、关于hashCode()和equals()的重写

3.1、重写hashCode() 方法的基本原则

  1. 在程序运行时,同一个对象多次调用hashCode()方法应该返回相同的值。
  2. 当两个对象的equals()方法比较返回true时,这两个对象的hashCode()方法的返回值也应相等。
  3. 对象中用作equals() 方法比较的Field,都应该用来计算hashCode值。

3.2、重写equals() 方法的基本原则

以自定义的Customer类为例,何时需要重写equals()?

  1. 当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候,总是要改写hashCode()。
  2. 根据一个类的equals方法(改写后),两个截然不同的实例有可能在逻辑上是相等的,但是,根据Object.hashCode()方法,它们仅仅是两个对象。
  3. 因此,违反了“相等的对象必须具有相等的散列码”。
  4. 结论:复写equals()方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。

3.3、Eclipse/IDEA工具里hashCode()的重写

以Eclipse/IDEA为例,在自定义类中可以调用工具自动重写equals和hashCode。问题:为什么用Eclipse/IDEA复写hashCode方法,有31这个数字?

  1. 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大,所谓的“冲突”就越少,查找起来效率也会提高。(减少冲突)
  2. 并且31只占用5bits,相乘造成数据溢出的概率较小。
  3. 31可以由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。(提高算法效率)
  4. 31是一个素数,素数作用就是如果我用一个数字来乘以这个素数,那么最终出来的结果只能被素数本身和被乘数还有1来整除!(减少冲突)

要求:向Set(主要指:HashSet、LinkedHashSet)中添加的数据,其所在的类一定要重写hashCode()和equals()
要求:重写的hashCode()和equals()尽可能保持一致性:相等的对象必须具有相等的散列码
重写两个方法的小技巧:对象中用作 equals() 方法比较的 Field,都应该用来计算 hashCode 值。

四、LinkedHashSet的使用

  1. LinkedHashSet是HashSet的子类。在添加数据的同时,每个数据还维护了两个引用,记录此数据前一个数据和后一个数据。
  2. LinkedHashSet根据元素的hashCode值来决定元素的存储位置,但它同时使用双向链表维护元素的次序,这使得元素看起来是以插入顺序保存的。
  3. LinkedHashSet插入性能略低于HashSet,但在迭代访问Set 里的全部元素时有很好的性能。
  4. LinkedHashSet不允许集合元素重复。
LinkedHashSet 底层结构
LinkedHashSet 底层结构