Java Map 和 Set（二）：剖析 HashSet

1. Set 的概念

• Set 表示的是没有重复元素、且不保证顺序的容器接口
• Set 扩展了 Collection，但没有定义任何新的方法。不过，对于其中的一些方法，它有自己的规范

2. HashSet 的实现原理

• HashSet 内部是用 HashMap 实现的。HashSet 内部有一个 HashMap 实例变量：private transient HashMap<E, Object> map;
• HashSet 相当于只有键，值都是相同的固定值。这个值的定义为：private static final Object PRESENT = new Object();
• 与 HashMap 类似，HashSet 要求元素重写 hashCode() 方法和 equals() 方法，且对于两个对象，如果 equals() 相同，则 hashCode() 也必须相同。如果元素是自定义的类，需要注意这一点

3. HashSet 的相关方法

• HashSet 的构造方法、add() 方法、remove() 方法等都是调用的 map 的相关方法

• add() 方法代码

  public boolean add(E e) {
  	return map.put(e, PRESENT) == null;
  }

  • 分析：就是调用 map 的 put() 方法，元素 e 用于键，值就是固定值 PRESENT。put() 返回 null 表示原来没有对应的键，添加成功了

• remove() 方法代码

  public boolean remove(Object o) {
  	return map.remove(o) == PRESENT;
  }

  • 分析：就是调用 map 的 remove() 方法，返回值为 PRESENT 表示原来有对应的键且删除成功了

4. HashSet 的特点

• HashSet 没有顺序，没有重复元素
• HashSet 可以高效地添加、删除元素、判断元素是否存在，效率都为 O(1)
• HashSet 可以方便高效地实现去重、集合运算等功能
  • 如果要保持添加的顺序，可以使用 HashSet 的一个子类 LinkedHashSet
  • Set 还有一个重要的实现类 TreeSet，它可以排序

5. HashSet 有哪些应用场景

• 去重：果对去重后的元素没有顺序要求，则 HashSet 可以方便地用于去重
• 保存特殊值：Set 可以用于保存各种特殊值，程序处理用户请求或数据记录时，根据是否为特殊值判断是否进行特殊处理。比如保存 IP 地址的黑名单或白名单
• 集合运算：使用 Set 可以方便地进行数据集合中的运算，如交集、并集等运算，这些运算有一些很现实的意义。比如，用户标签计算，每个用户都有一些标签，两个用户的标签交集就表示他们的共同特征，交集大小除以并集大小可以表示他们的相似程度