java集合----HashSet

发表于 | 更新于: | 阅读次数:

一.前言

java集合—-Set

HashSet 是 Set 接口的一个实现类，当然就具有 Set 接口指定的一些规范。
即所有在集合中的元素都是唯一的，那么 HashSet 是如何保证添加的元素的一个唯一性呢，这其中除了equals 还涉及到其他方法吗？ 下面对 HashSet 的源码进行一个深入的了解。

二.深入解析

1.简介

下面引用自源码中的注释

HashSet 实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序;(也就是添加顺序)特别是它不保证该顺序恒久不变。允许使用 null 元素。

注意，HashSet 不是同步的。如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须 保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作，以防止对该 set 进行意外的不同步访问：
Set s = Collections.synchronizedSet(new HashSet(…));

此类的 iterator 方法返回的迭代器是快速失败 的：在创建迭代器之后，如果对 set 进行修改，除非通过迭代器自身的 remove 方法，否则在任何时间以任何方式对其进行修改，Iterator 都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒将来在某个不确定时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器在尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误做法：迭代器的快速失败行为应该仅用于检测 bug。

2.变量

HashSet 自身增加的变量只有三个

1
2
3
4
5
6
7
8
9
10
//用于序列化和反序列化的 UID
 static final long serialVersionUID = -5024744406713321676L;

 //为 HashSet 提供具体实现的 map
 private transient HashMap<E,Object> map;

 //因为 HashSet 是保存一个简单元素
 //而Map 存储的 key--value 
 //所以就创建一个虚拟的 value 值
 private static final Object PRESENT = new Object();

3.构造器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
  //默认的构造器，内部是创建一个 HashMap
  public HashSet() {
      map = new HashMap<>();
  }

  //指定初始元素的构造器
  public HashSet(Collection<? extends E> c) {
      map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
      addAll(c);
  }

  
  //指定一个初始容量和增长因子的 HashSet
  public HashSet(int initialCapacity, float loadFactor) {
      map = new HashMap<>(initialCapacity, loadFactor);
  }

//指定一个初始容量的 HashSet
  public HashSet(int initialCapacity) {
      map = new HashMap<>(initialCapacity);
  }

  
  // default 权限的构造器
  //这个构造器只是用在创建 LinkedHashSet 
  HashSet(int initialCapacity, float loadFactor, boolean dummy) {
      map = new LinkedHashMap<>(initialCapacity, loadFactor);
  }

从 HashSet 的几个变量和构造器可以看出，内部的过程其实都是使用创建出一个 HashMap ，包括指定初始容量和增长因子等都是内部创建一个 HashMap 。

4.add 方法
1
2
3
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

HashSet 内部是由 HashMap 提供实现的，且 HashSet 中的元素都是作为 HashMap 的一个 key ,那么 value 就都是同一个对象，即 PRESENT 。

那么到这里，对于 HashSet 如何保证元素唯一的问题其实就转换为 HashMap 中 如何保证 key 的唯一性。

下面到 HashMap 的一个 put 方法中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public V put(K key, V value) {
    // 注意这里的前前两个参数
    //一个是 key 经过 hash 函数处理后的值
    //一个是 key 的原值
    return putVal(hash(key), key, value, false, true);
}

//这里对源码进行一些删除，只关注我们需要的地方即可
//版本 ：JDK 10

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
               
    Node<K,V>[] tab; 
    Node<K,V> p;
    int n, i;
    
    //如果table 为 null 或者
    //table 数组长度为 0 的话就进行
    //resize()  进行初始化。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
        
        
    //如果根据 key的 hashCode 处理后的 hash 值
    //定位到数组位置为 null 的话就直接创建一个节点。
    //不需要进行判断两个元素是否相等。
    if ((p = tab[i = (n - 1) & hash]) == null)
    
        tab[i] = newNode(hash, key, value, null);
        
    否则就需要进行判断
    else {
    
        Node<K,V> e; K k;
        //判断两个元素是否是同一个元素的判断就在这里
        //第一个情况是 两个对象处理 hash 值是相等的并且 key 也是同一个 key
        // 第二种是 key 的 equals 方法。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            //这是去红黑树插入
        else if (p instanceof TreeNode)
           //这是根据节点插入。
        else {
           
        }
        
        //e 不为null ,put 返回的参数就不为 null
        
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            ..
            return oldValue;
        }
    }
    //如果在第一次进行判断时数组对应位置没有被初始化，
    //就说明是第一次添加，也就是没有重复，这里就返回 null.
    //在 HashSet 的 add 方法中  map.put(e, PRESENT)==null; 
    //就返回 true ,也就是没有重复，添加成功。
    //否则就是上面 e != null 情况，就说明 重复添加了，
    //map.put(e, PRESENT)==null;  返回  false 
    
    return null;
    }
 
}

从上面的注释已经可以知道 HashSet 是如果判断一个元素是否重复的，总结如下：

  • 通过 key 的 hashCode 定位到数组位置，如果刚好为 null,第一次添加，就不重复。
  • 如果不为 null, 因为 hashCode 可能存在着从重复（哈希冲突），所以需要结合 equals 进行判断。
  • key 为 null 或者 不为 null 的情况，如果 hash 相等，并且 key == 返回 true ,即是同一个对象 ，重复（这种情况判断了 key 为 null 和 同一个对象的情况）
  • key 不 null 的情况，且不是同一个对象（== 返回 false ）,但是 equals 返回 true , 仍然是重复（这种情况就盘判断了我们定义的 对象相等的情况 即 equals 返回 true ）。

因此这里就要注意，对于一个类，如果重写其 equals，就要保证 equals
返回 true 的时候，hashCode 返回相同的值 ，hashCode 返回不同的值的时候， equals
返回 false

因为 判断一个对象是否重复在 HashSet 中其实使用了这两个方法，进行判断。

5.其他
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

   
public void clear() {
    map.clear();
}

   
@SuppressWarnings("unchecked")
public Object clone() {
    try {
        HashSet<E> newSet = (HashSet<E>) super.clone();
        newSet.map = (HashMap<E, Object>) map.clone();
        return newSet;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}


private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();

    // Write out HashMap capacity and load factor
    s.writeInt(map.capacity());
    s.writeFloat(map.loadFactor());

    // Write out size
    s.writeInt(map.size());

    // Write out all elements in the proper order.
    for (E e : map.keySet())
        s.writeObject(e);
}

   
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();

    // Read capacity and verify non-negative.
    int capacity = s.readInt();
    if (capacity < 0) {
        throw new InvalidObjectException("Illegal capacity: " +
                                         capacity);
    }

    // Read load factor and verify positive and non NaN.
    float loadFactor = s.readFloat();
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new InvalidObjectException("Illegal load factor: " +
                                         loadFactor);
    }

    // Read size and verify non-negative.
    int size = s.readInt();
    if (size < 0) {
        throw new InvalidObjectException("Illegal size: " +
                                         size);
    }

    // Set the capacity according to the size and load factor ensuring that
    // the HashMap is at least 25% full but clamping to maximum capacity.
    capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
            HashMap.MAXIMUM_CAPACITY);

    // Constructing the backing map will lazily create an array when the first element is
    // added, so check it before construction. Call HashMap.tableSizeFor to compute the
    // actual allocation size. Check Map.Entry[].class since it's the nearest public type to
    // what is actually created.
    SharedSecrets.getJavaObjectInputStreamAccess()
                 .checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(capacity));

    // Create backing HashMap
    map = (((HashSet<?>)this) instanceof LinkedHashSet ?
           new LinkedHashMap<>(capacity, loadFactor) :
           new HashMap<>(capacity, loadFactor));

    // Read in all elements in the proper order.
    for (int i=0; i<size; i++) {
        @SuppressWarnings("unchecked")
            E e = (E) s.readObject();
        map.put(e, PRESENT);
    }
}

   
public Spliterator<E> spliterator() {
    return new HashMap.KeySpliterator<>(map, 0, -1, 0, 0);
}

其实只要清楚了 HashSet 的判断重复的原理，对于删除等其他操作，就很简单了，都是基于查找过程。对于其他方法，也就是通过 HashMap 结合使用，这里就不进行深究了。

0%