1. HashSet概述
HashSet实现Set接口,由哈希表(实际上是一个HashMap实例)支持。它不保证set 的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用null元素。
2. HashSet的实现
如果不等,则添加到该数组索引对应的链表中。
------------------------------------------------------------------------------------------
Set的实现类的集合对象中不能够有重复元素,HashSet也一样他是使用了一种标识来确定元素的不重复,HashSet用一种算法来保证
HashSet中的元素是不重复的, HashSet采用哈希算法,底层用数组存储数据。默认初始化容量16,加载因子0.75
Object类中的hashCode()的方法是所有子类都会继承这个方法,这个方法会用Hash算法算出一个Hash(哈希)码值返回,HashSet
会用Hash码值去和数组长度取模,
模(这个模就是对象要存放在数组中的位置)相同时才会判断数组中的元素和要加入的对象的内容是否相同,如果不同才会添加进去。
Hash算法是一种散列算法。
Set hs=new HashSet();
hs.add(o);
|
o.hashCode();
|
o%当前总容量 (0--15)
|
| 不发生冲突
是否发生冲突-----------------直接存放
|
| 发生冲突
| 假(不相等)
o1.equals(o2)-------------------找一个空位添加
|
| 是(相等)
不添加
覆盖hashCode()方法的原则:
1、一定要让那些我们认为相同的对象返回相同的hashCode值
2、尽量让那些我们认为不同的对象返回不同的hashCode值,否则,就会增加冲突的概率。
3、尽量的让hashCode值散列开(两值用异或运算可使结果的范围更广)
HashSet
的实现比较简单,相关HashSet的操作,基本上都是直接调用底层HashMap的相关方法来完成,我们应该为保存到HashSet中的对象覆盖
hashCode()和equals(),因为再将对象加入到HashSet中时,会首先调用hashCode方法计算出对象的hash值,接着根据此
hash值调用HashMap中的hash方法,得到的值& (length-1)得到该对象在hashMap的transient
Entry[]
table中的保存位置的索引,接着找到数组中该索引位置保存的对象,并调用equals方法比较这两个对象是否相等,如果相等则不添加,注意:所以要存
入HashSet的集合对象中的自定义类必须覆盖hashCode(),equals()两个方法,才能保证集合中元素不重复。在覆盖equals()和
hashCode()方法时,
要使相同对象的hashCode()方法返回相同值,覆盖equals()方法再判断其内容。为了保证效率,所以在覆盖hashCode()方法时,
也要尽量使不同对象尽量返回不同的Hash码值。
如果数组中的元素和要加入的对象的hashCode()返回了相同的Hash值(相同对象),才会用equals()方法来判断两个对象的内容是否相同。
------------------------------------------------------------------------------------------
HashSet的源代码如下:
- public class HashSet<E>
- extends AbstractSet<E>
- implements Set<E>, Cloneable, java.io.Serializable
- {
- static final long serialVersionUID = -5024744406713321676L;
-
-
- private transient HashMap<E,Object> map;
-
-
- private static final Object PRESENT = new Object();
-
-
-
-
-
-
- public HashSet() {
- map = new HashMap<E,Object>();
- }
-
-
-
-
-
-
-
-
- public HashSet(Collection<? extends E> c) {
- map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
- addAll(c);
- }
-
-
-
-
-
-
-
-
- public HashSet(int initialCapacity, float loadFactor) {
- map = new HashMap<E,Object>(initialCapacity, loadFactor);
- }
-
-
-
-
-
-
-
- public HashSet(int initialCapacity) {
- map = new HashMap<E,Object>(initialCapacity);
- }
-
-
-
-
-
-
-
-
-
-
- HashSet(int initialCapacity, float loadFactor, boolean dummy) {
- map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
- }
-
-
-
-
-
-
-
-
-
- public Iterator<E> iterator() {
- return map.keySet().iterator();
- }
-
-
-
-
-
-
-
- public int size() {
- return map.size();
- }
-
-
-
-
-
-
-
- public boolean isEmpty() {
- return map.isEmpty();
- }
-
-
-
-
-
-
-
-
-
-
- public boolean contains(Object o) {
- return map.containsKey(o);
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- public boolean add(E e) {
- return map.put(e, PRESENT)==null;
- }
-
-
-
-
-
-
-
-
-
-
-
- public boolean remove(Object o) {
- return map.remove(o)==PRESENT;
- }
-
-
-
-
-
-
- public void clear() {
- map.clear();
- }
-
-
-
-
-
-
- public Object clone() {
- try {
- HashSet<E> newSet = (HashSet<E>) super.clone();
- newSet.map = (HashMap<E, Object>) map.clone();
- return newSet;
- } catch (CloneNotSupportedException e) {
- throw new InternalError();
- }
- }
- }
|