HashSet 的特点
- 它是无序的,即添加的顺序和遍历出来的顺序是不同的
- 它里面不允许有重复元素,是因为它是基于HashMap实现的
- 实现了Set接口,由哈希表(实际上是一个HashMap实例)支持
- 底层数据结构是哈希表(散列表)
HashSet 的底层是用散列表实现的,散列表的大小默认为16,加载因子为0.75。
去重原理
依赖两个方法:hashCode()和equals()
如果我们希望一个集合有去重复的功能, 可以在它的add方法中检查要添加的对象在集合中是否存在,迭代集合中每个元素, 和要添加的比较, 如果相同, 就不存,所以我们来看看add()方法的部分源码解析:
private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
......
if (e.hash == hash && ((k = e.key) == key || key.equals(k))){
......//e.hash调用了hashCode()方法获得了e元素的hash值
}
它的add()方法实际上调用的是HashMap中的put()方法,把要添加进HashSet中的元素当做key存入,而value则是一个固定值:一个Object类对象。
执行顺序:
-
首先比较哈希值是否相同
-
相同:继续执行equals()方法
返回true:元素重复了,不添加
返回false:直接把元素添加到集合 -
不同:就直接把元素添加到集合
元素唯一性由hashCode()和equals()保证的,二者缺一不可