Set

Set接口

java.util.Set接口 extends Collection接口

Set接口的特点:

• 不可重复性：不允许存储重复的元素。不可重复性是指添加的元素按照 equals() 判断时 ，返回 false，需要同时重写 equals() 方法和 hashCode() 方法。

• 无序性：没有索引，没有带索引的方法，也不能使用普通的for循环遍历。无序性不等于随机性 ，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。

HashSet

java.util.HashSet implements Set，是Set接口的一个实现类，它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序不一致)。java.util.HashSet底层的实现其实是一个java.util.HashMap支持

HashSet特点:

• 不允许存储重复的元素
• 没有索引，没有带索引的方法，也不能使用普通的for循环遍历
• 是一个无序的集合，存储元素和取出元素的顺序有可能不一致
• 底层是一个哈希表结构(查询的速度非常的快)

tips：

• Set集合取出元素的方式可以采用：迭代器、增强for。
• HashSet是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。
• 保证元素唯一性的方式依赖于：hashCode与equals方法。

public static void main(String[] args) {
  Set<Integer> set = new HashSet<>();
  //使用add方法往集合中添加元素
  set.add(1);
  set.add(3);
  set.add(2);
  set.add(1);

  //使用迭代器遍历set集合
  Iterator<Integer> it = set.iterator();
  while (it.hasNext()){
    Integer n = it.next();
    System.out.println(n);//1,2,3
  }
  //使用增强for遍历set集合
  System.out.println("-----------------");
  for (Integer i : set) {
    System.out.println(i);
  }
}

HashSet集合存储数据的结构（哈希表）

在JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。

而JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

HashSet 如何检查重复?

在 JDK1.8 中，HashSet的add()方法只是简单的调用了HashMap的put()方法，并且判断了一下返回值以确保是否有重复元素。直接看一下HashSet中的源码：

// Returns: true if this set did not already contain the specified element
// 返回值：当 set 中没有包含 add 的元素时返回真
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

而在HashMap的putVal()方法中也能看到如下说明：

// Returns : previous value, or null if none
// 返回值：如果插入位置没有元素返回null，否则返回上一个元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
...
}

也就是说，在 JDK1.8 中，实际上无论HashSet中是否已经存在了某元素，HashSet都会直接插入，只是会在add()方法的返回值处告诉我们插入前是否存在相同元素。

HashSet加入元素时

• 先比较哈希值，再用equals比较是否相等，判断元素是否重复

• • 如果集合中没有发现哈希值冲突的元素，把元素加入到集合
  • 如果发生哈希冲突，则使用equals方法比较两个元素是否相同，不相同则加入

哈希值：是一个十进制的整数,由系统随机给出(就是对象的地址值,是一个逻辑地址,是模拟出来得到地址,不是数据实际存储的物理地址)

int hashCode() ：Object类的一个方法，返回该对象的哈希码值。

为什么HashSet存储自定义类型元素必须重写hashCode方法和equals方法

给HashSet中存放自定义类型元素时，需要重写对象中的hashCode和equals方法，建立自己的比较方式，才能保证HashSet集合中的对象唯一。

set集合报错元素唯一：存储的元素为(String,Integer,…Student,Person…)时，必须重写hashCode方法和equals方法，因为不同对象的地址值不相同

public class Demo01HashCode {
  public static void main(String[] args) {
    //Person类继承了Object类,所以可以使用Object类的hashCode方法
    Person p1 = new Person();
    int h1 = p1.hashCode();
    System.out.println(h1);//1967205423

    Person p2 = new Person();
    int h2 = p2.hashCode();
    System.out.println(h2);//42121758
    /*

    //toString方法的源码:
        return getClass().getName() + "@" + Integer.toHexString(hashCode());
     */
    System.out.println(p1);//com.itheima.demo03.hashCode.Person@75412c2f
    System.out.println(p2);//com.itheima.demo03.hashCode.Person@282ba1e
    System.out.println(p1==p2);//false


    /*
      String类的哈希值
        String类默认重写Obejct类的hashCode方法
     */
    String s1 = new String("abc");
    String s2 = new String("abc");
    System.out.println(s1.hashCode());//96354
    System.out.println(s2.hashCode());//96354
    System.out.println("重地".hashCode());//1179395
    System.out.println("通话".hashCode());//1179395
  }
}

例子

要求：同名同年龄的人视为同一个人，只能存储一次（若不重写，不同的对象必定可以重复存储）

public class Person {
  private String name;
  private int age;
  public Person() {
  }
  public Person(String name, int age) {
    this.name = name;
    this.age = age;
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Person person = (Person) o;
    return age == person.age &&Objects.equals(name, person.name);  //名字和年龄都相等
  }

  @Override
  public int hashCode() {
    return Objects.hash(name, age);
  }

 

  @Override
  public String toString() {
    return "Person{" +
        "name='" + name + '\'' +
        ", age=" + age +
        '}';
  }
}

 
public static void main(String[] args) {
  //创建HashSet集合存储Person
  HashSet<Person> set = new HashSet<>();
  Person p1 = new Person("小美女",18);
  Person p2 = new Person("小美女",18);
  Person p3 = new Person("小美女",19);
  System.out.println(p1.hashCode());//1967205423
  System.out.println(p2.hashCode());//42121758
  System.out.println(p1==p2);//false
  System.out.println(p1.equals(p2));//false
  set.add(p1);
  set.add(p2);
  set.add(p3);
  System.out.println(set);//[Person{name='小美女', age=19}, Person{name='小美女', age=18}]
}

LinkedHashSet

java.util.LinkedHashSet extends HashSet

底层是一个哈希表(数组+链表/红黑树)+链表：多了一条链表(记录元素的存储顺序)，保证元素有序（插入顺序和取出顺序相同）

HashSet<String> set = new HashSet<>();
set.add("www");
set.add("abc");
set.add("abc");
set.add("itcast");
System.out.println(set);//[abc, www, itcast] 无序

 
LinkedHashSet<String> linked = new LinkedHashSet<>();
linked.add("www");
linked.add("abc");
linked.add("abc");
linked.add("itcast");
System.out.println(linked);//[www, abc, itcast] 有序

TreeSet

java.util.TreeSet implements SortedSet

底层数据结构是二叉树（红黑树），采用自然排序或比较器排序保证元素有序（默认采用自认排序）

TreeSet<String> set = new TreeSet<>();
set.add("www");
set.add("abc");
set.add("abc");
set.add("itcast");
System.out.println(set);//[abc, itcast, www] 自然有序