浅谈集合HashSet

HashSet

简介

HashSet集合继承于Collection集合，Collection集合的常用方法也在HashSet中同样适用。

• 底层原理：HashSet集合底层采用哈希表存储数据，底层是new 了一个HashMap，add方法是利用map.put()方法。

  public HashSet() {
      map = new HashMap<>();
  }
  

  HashSet是用HashMap来保存数据，而主要使用到的就是HashMap的key。

  // 底层使用HashMap来保存HashSet的元素
  private transient HashMap<E,Object> map;
  // 由于Set只使用到了HashMap的key，所以此处定义一个静态的常量Object类，来充当HashMap的value
  private static final Object PRESENT = new Object();
  

  看到 private static final Object PRESENT = new Object();不知道你有没有一点疑问呢。

  这里使用一个静态的常量Object类来充当HashMap的value，既然这里map的value是没有意义的，为什么不直接使用null值来充当value呢？

  比如写成这样子 private final Object PRESENT = null ;

  我们都知道的是，Java首先将变量PRESENT分配在栈空间，而将new出来的Object分配到堆空间，这里的new Object()是占用堆内存的（一个空的Object对象占用8byte），而null值我们知道，是不会在堆空间分配内存的。

  那么想一想这里为什么不使用null值。想到什么吗，看一个异常类 java.lang.NullPointerException，这绝对是Java程序员的一个噩梦，这是所有Java程序猿都会遇到的一个异常，你看到这个异常你以为很好解决，但是有些时候也不是那么容易解决，Java号称没有指针，但是处处碰到NullPointerException。所以啊，为了从根源上避免NullPointerException的出现，浪费8个byte又怎么样，在下面的代码中我再也不会写这样的代码了if (xxx == null) { … } else {….}。

• 哈希表是一种对于增删改查数据性能都较好的数据结构

哈希表组成：

• JDK8之前：数组 + 链表
• JDK8开始：数组 + 链表 + 红黑树（后面会出一期红黑树的文章）

哈希值：对象的整数表示形式

• 根据HashCode方法算出来的int类型的整数
• 该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算。
• 一般情况下，会重写HashCode方法，利用对象内部的属性值计算哈希值。

对象的哈希值特点：

• 如果没有重写HashCode方法，不同对象计算出来的哈希值是不同的。
• 如果已经重写hashcode方法，不同的对象只要属性值相同，计算出的哈希值就是一样的
• 在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。(哈希碰撞)
• 如果集合存储的是自定义的对象，必须要重写hashCode方法和equals方法

public class A01_HashSetDemo1 {
    public static void main(String[] args) {

        Student s1 = new Student("zhangsan",19);
        Student s2 = new Student("zhangsan",19);

        //没有重写HashCode方法
        System.out.println(s1.hashCode());//哈希值为460141958
        System.out.println(s2.hashCode());//哈希值为1163157884
    }
}

重写HashCode方法：

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

得到新的哈希值：

		Student s1 = new Student("zhangsan",19);
        Student s2 = new Student("zhangsan",19);

        System.out.println(s1.hashCode());//-1461067296
        System.out.println(s2.hashCode());//-1461067296

可以发现重写HashCode方法后只要属性值相同，计算出来的哈希值是相同的。

哈希碰撞（小概率事件）：

		System.out.println("abc".hashCode());//96354
        System.out.println("acD".hashCode());//96354

HashSet JDK8 以前的底层原理

HashSet<String> hm = new HashSet<>();

1. 创建一个默认长度16，默认加载因子0.75的数组，数组名为table

   • 当元素 为 16 * 0.75 = 12 时，就会触发扩容机制，扩大为原来数组的两倍。也就是32。
   • 当链表长度大于8而且数组数组长度大于等于64。就会将数组转成红黑树，从而提高查找效率。

2. 根据元素的哈希值跟数组的长度计算出应存入的位置。

   int index = （数组长度 - 1）& 哈希值 ;

3. 判断当前位置是否为null，如果是null直接存入。

4. 如果位置不为null，表示有元素，则调用equals方法比较属性值。

5. 一样：不存入 不一样：存入数组，形成链表（单链表）。

   JDK8以前：新元素存入数组，老元素挂在新元素下面

   JDK8以后：新元素直接挂在老元素下面

HashSet的三个问题：

问题1：HashSet为什么存和取的顺序一样？

问题2：HashSet为什么没有索引？

问题3：HashSet是利用什么机制保证数据去重的？（HashCode方法、equals方法）

利用HashSet集合去除重复元素

需求：创建一个存储学生对象的集合，存储多个学生对象。

使用程序实现在控制台遍历集合。

要求：学生对象的成员变量值相同，我们就认为是同一个对象。

关键：学生类重写hashCode方法和equals方法即可。