Hashset 实现 set 接口,底层基于 Hashmap 实现, 但与 Hashmap 不同的实 Hashmap 存储键值对,Hashset 仅存储对象。
HashSet 使用成员对象来计算 hashcode 值。
在《Head fist java》一书中有描述:
当你把对象加入 HashSet 时,HashSet 会先计算对象的 hashcode 值来判断对象加入的位置,同时也会与其他加入的对象的 hashcode 值作比较,如果没有相符的 hashcode,HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象,这时会调用 equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同,则覆盖旧元素。
这里看到很多文章说:
。根据 hashmap 的 put()方法源码可知,实际上是覆盖操作,虽然覆盖对象的 key 和 value 都完全一致。
首先查看下源码结构,发现该类源码相对比较简单
/** * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has * default initial capacity (16) and load factor (0.75). */ // 内部存储在hashmap中 public HashSet() { map = new HashMap<>(); }
private static final Object PRESENT = new Object(); public boolean add(E e) { return map.put(e, PRESENT)==null; }
可以看到添加的对象直接作为 Hashmap 的 key, 而 value 是 final 修饰的空对象。
根据之前对 Java 面试必问之 Hashmap 底层实现原理(JDK1.8) 中 put()
方法的解读可以知道:
在 Hashmap 中首先根据 hashCode 寻找数组 bucket,当 hash 冲突时,需要比较 key 是否相等,相等则覆盖,否则通过拉链法进行处理。在 Hashset 中存储的对象作为 key,所以存储对象需要重写 hashCode()
和 equals()
方法。
再来看一组示例
public class Demo2 { public static void main(String[] args) { HashSet<Object> hashSet = new HashSet<>(); hashSet.add("a"); hashSet.add("b"); hashSet.add("c"); hashSet.add("a"); System.out.println(hashSet); } }
结果
[a, b, c]
查看字符串源码.字符串重写了 hashCode()和 equals 方法, 所以结果符合预期
public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } public boolean equals(Object anObject) { if (this == anObject) { return true; } if (anObject instanceof String) { String anotherString = (String)anObject; int n = value.length; if (n == anotherString.value.length) { char v1[] = value; char v2[] = anotherString.value; int i = 0; while (n-- != 0) { if (v1[i] != v2[i]) return false; i++; } return true; } } return false; } }
首先我们创建一个 user
对象
@Getter@Setter @AllArgsConstructor @ToString public class User { private String username; }
根据 set 集合的属性,set 中的元素是不重复的,现在测试下
public class Demo { public static void main(String[] args) { HashSet<Object> hashSet = new HashSet<>(); hashSet.add(new User("a")); hashSet.add(new User("b")); hashSet.add(new User("c")); hashSet.add(new User("a")); System.out.println(hashSet); } }
结果输出
[User(username=a), User(username=c), User(username=b), User(username=a)]
怎么会有重复的呢? 和预期结果不符呀。其实根据上边的源码我们已经知道原因了,打印 hash 值确认下
[901506536, 1513712028, 747464370, 1018547642]
java 中对象默认继承顶级父类 Object。在 Object 类中源码如下:
public native int hashCode(); // 比较内存地址 public boolean equals(Object obj) { return (this == obj); }
重写 equals()和 hashCode()方法。(这里偷了个懒,感兴趣的大家可以自己重写下这 2 个方法)
@Getter@Setter @AllArgsConstructor @ToString @EqualsAndHashCode public class User extends Object{ private String username; }
再次输出发现结果唯一了
[User(username=a), User(username=b), User(username=c)]
其实 HashSet 的一些东西都是用 HashMap 来实现的,如果 HashMap 的源码已经阅读过的话基本上没有什么问题。这可能是我写的最轻松的一篇文章。