HashSet 去重原理知多少?

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类对象。

执行顺序:

  1. 首先比较哈希值是否相同

  2. 相同:继续执行equals()方法
    返回true:元素重复了,不添加
    返回false:直接把元素添加到集合

  3. 不同:就直接把元素添加到集合

元素唯一性由hashCode()和equals()保证的,二者缺一不可

上一篇:android – 在TabBar下面添加阴影 – Material Design


下一篇:Unity Shader 屏幕后效果——Bloom外发光