本文已收录《Java 常见面试题》系列，Git 开源地址：https://gitee.com/mydb/interview
HashSet 实现了 Set 接口，由哈希表（理论是 HashMap）提供反对。HashSet 不保障汇合的迭代程序，但容许插入 null 值。也就是说 HashSet 不能保障元素插入程序和迭代程序雷同。
HashSet 具备去重的个性，也就是说它能够将汇合中的反复元素主动过滤掉，保障存储在 HashSet 中的元素都是惟一的。
1.HashSet 根本用法
HashSet 基本操作办法有：add（增加）、remove（删除）、contains（判断某个元素是否存在）和 size（汇合数量）。这些办法的性能都是固定操作工夫，如果哈希函数是将元素扩散在桶中的正确地位。
HashSet 根本应用如下：
// 创立 HashSet 汇合
HashSet<String> strSet = new HashSet<>();
// 给 HashSet 增加数据
strSet.add("Java");
strSet.add("MySQL");
strSet.add("Redis");
// 循环打印 HashSet 中的所有元素
strSet.forEach(s -> System.out.println(s));2.HashSet 无序性
HashSet 不能保障插入元素的程序和循环输入元素的程序肯定雷同，也就是说 HashSet 其实是无序的汇合，具体代码示例如下：
HashSet<String> mapSet = new HashSet<>();
mapSet.add("深圳");
mapSet.add("北京");
mapSet.add("西安");
// 循环打印 HashSet 中的所有元素
mapSet.forEach(m -> System.out.println(m));以上程序的执行后果如下：
从上述代码和执行后果能够看出，HashSet 插入的程序是：深圳 -> 北京 -> 西安 ，而循环打印的程序却是： 西安 -> 深圳 -> 北京，所以 HashSet 是无序的，不能保障插入和迭代的程序统一。
PS：如果要保障插入程序和迭代程序统一，可应用 LinkedHashSet 来替换 HashSet。
3.HashSet 谬误用法
有人说 HashSet 只能保障根底数据类型不反复，却不能保障自定义对象不反复？这样说对吗？
咱们通过以下示例来阐明此问题。
3.1 HashSet 与根本数据类型
应用 HashSet 存储根本数据类型，实现代码如下：
HashSet<Long> longSet = new HashSet<>();
longSet.add(666l);
longSet.add(777l);
longSet.add(999l);
longSet.add(666l);
// 循环打印 HashSet 中的所有元素
longSet.forEach(l -> System.out.println(l));以上程序的执行后果如下：
从上述后果能够看出，应用 HashSet 能够保障根底数据类型不反复。
3.2 HashSet 与自定义对象类型
接下来，将自定义对象存储到 HashSet 中，实现代码如下：
public class HashSetExample {public static void main(String[] args) {HashSet<Person> personSet = new HashSet<>();
personSet.add(new Person("曹操", "123"));
personSet.add(new Person("孙权", "123"));
personSet.add(new Person("曹操", "123"));
// 循环打印 HashSet 中的所有元素
personSet.forEach(p -> System.out.println(p));
}
}
@Getter
@Setter
@ToString
class Person {
private String name;
private String password;
public Person(String name, String password) {
this.name = name;
this.password = password;
}
}以上程序的执行后果如下：
从上述后果能够看出，自定义对象类型的确没有被去重，那也就是说 HashSet 不能实现自定义对象类型的去重咯？
其实并不是，HashSet 去重性能是依赖元素的 hashCode 和 equals 办法判断的，通过这两个办法返回的都是 true 那就是雷同对象，否则就是不同对象。而后面的 Long 类型元素之所以能实现去重，正是因为 Long 类型中曾经重写了 hashCode 和 equals 办法，具体实现源码如下：
@Override
public int hashCode() {return Long.hashCode(value);
}
public boolean equals(Object obj) {if (obj instanceof Long) {return value == ((Long)obj).longValue();}
return false;
}
// 省略其余源码......更多对于 hashCode 和 equals 的内容，详见：https://mp.weixin.qq.com/s/40zaEJEkQYM3Awk2EwIrWA
那么，想让 HashSet 反对自定义对象去重，只须要在自定义对象中重写 hashCode 和 equals 办法即可，具体实现代码如下：
@Setter
@Getter
@ToString
class Person {
private String name;
private String password;
public Person(String name, String password) {
this.name = name;
this.password = password;
}
@Override
public boolean equals(Object o) {if (this == o) return true; // 援用相等返回 true
// 如果等于 null，或者对象类型不同返回 false
if (o == null || getClass() != o.getClass()) return false;
// 强转为自定义 Person 类型
Person persion = (Person) o;
// 如果 name 和 password 都相等，就返回 true
return Objects.equals(name, persion.name) &&
Objects.equals(password, persion.password);
}
@Override
public int hashCode() {
// 比照 name 和 password 是否相等
return Objects.hash(name, password);
}
}从新运行以上代码，执行后果如下图所示：
从上述后果能够看出，之前的反复项“曹操”曾经被去重了。
4.HashSet 如何保障元素不反复？
咱们只有理解了 HashSet 执行增加元素的流程，就能晓得为什么 HashSet 能保障元素不反复了？
HashSet 增加元素的执行流程是：当把对象退出 HashSet 时，HashSet 会先计算对象的 hashcode 值来判断对象退出的地位，同时也会与其余退出的对象的 hashcode 值作比拟，如果没有相符的 hashcode，HashSet 会假如对象没有反复呈现，会将对象插入到相应的地位中。然而如果发现有雷同 hashcode 值的对象，这时会调用对象的 equals() 办法来查看对象是否真的雷同，如果雷同，则 HashSet 就不会让反复的对象退出到 HashSet 中，这样就保障了元素的不反复。
为了更分明的理解 HashSet 的增加流程，咱们能够尝试浏览 HashSet 的具体实现源码，HashSet 增加办法的实现源码如下（以下源码基于 JDK 8）：
// hashmap 中 put() 返回 null 时，示意操作胜利
public boolean add(E e) {return map.put(e, PRESENT)==null;
}从上述源码能够看出 HashSet 中的 add 办法，理论调用的是 HashMap 中的 put，那么咱们持续看 HashMap 中的 put 实现：
// 返回值：如果插入地位没有元素则返回 null，否则返回上一个元素
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}从上述源码能够看出，HashMap 中的 put() 办法又调用了 putVal() 办法，putVal() 的源码如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {Node<K, V>[] tab;
Node<K, V> p;
int n, i;
// 如果哈希表为空，调用 resize() 创立一个哈希表，并用变量 n 记录哈希表长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 如果指定参数 hash 在表中没有对应的桶，即为没有碰撞
* Hash 函数，(n - 1) & hash 计算 key 将被搁置的槽位
* (n - 1) & hash 实质上是 hash % n 位运算更快
*/
if ((p = tab[i = (n - 1) & hash]) == null)
// 间接将键值对插入到 map 中即可
tab[i] = newNode(hash, key, value, null);
else {// 桶中曾经存在元素
Node<K, V> e;
K k;
// 比拟桶中第一个元素 (数组中的结点) 的 hash 值相等，key 相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给 e，用 e 来记录
e = p;
// 以后桶中无该键值对，且桶是红黑树结构，依照红黑树结构插入
else if (p instanceof TreeNode)
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 以后桶中无该键值对，且桶是链表构造，依照链表构造插入到尾部
else {for (int binCount = 0; ; ++binCount) {
// 遍历到链表尾部
if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
// 查看链表长度是否达到阈值，达到将该槽位节点组织模式转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 链表节点的 <key, value> 与 put 操作 <key, value>
// 雷同时，不做反复操作，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到或新建一个 key 和 hashCode 与插入元素相等的键值对，进行 put 操作
if (e != null) { // existing mapping for key
// 记录 e 的 value
V oldValue = e.value;
/**
* onlyIfAbsent 为 false 或旧值为 null 时，容许替换旧值
* 否则无需替换
*/
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 拜访后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 更新结构化批改信息
++modCount;
// 键值对数目超过阈值时，进行 rehash
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}从上述源码能够看出，当将一个键值对放入 HashMap 时，首先依据 key 的 hashCode() 返回值决定该 Entry 的存储地位。如果有两个 key 的 hash 值雷同，则会判断这两个元素 key 的 equals() 是否雷同，如果雷同就返回 true，阐明是反复键值对，那么 HashSet 中 add() 办法的返回值会是 false，示意 HashSet 增加元素失败。因而，如果向 HashSet 中增加一个曾经存在的元素，新增加的汇合元素不会笼罩已有元素，从而保障了元素的不反复。如果不是反复元素，put 办法最终会返回 null，传递到 HashSet 的 add 办法就是增加胜利。
总结
HashSet 底层是由 HashMap 实现的，它能够实现反复元素的去重性能，如果存储的是自定义对象必须重写 hashCode 和 equals 办法。HashSet 保障元素不反复是利用 HashMap 的 put 办法实现的，在存储之前先依据 key 的 hashCode 和 equals 判断是否已存在，如果存在就不在反复插入了，这样就保障了元素的不反复。
卒然临之而不惊，无端加之而不怒。
博主：80 后程序员。喜好：读书、写作和慢跑。
公众号：Java 面试真题解析