1. HashSet 概述：
HashSet 实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。
2. HashSet 的实现：
对于 HashSet 而言，它是基于 HashMap 实现的， HashSet 底层使用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是 直接调用底层 HashMap 的相关方法来完成 ， 我们应该为保存到HashSet中的对象覆盖hashCode()和equals()，因为再将对象加入到HashSet中时，会首先调用hashCode方法计算出对象的hash值，接着根据此hash值调用HashMap中的hash方法，得到的值& (length-1)得到该对象在hashMap的transient Entry[] table中的保存位置的索引，接着找到数组中该索引位置保存的对象，并调用equals方法比较这两个对象是否相等，如果相等则不添加，如果不等，则添加到该数组索引对应的链表中。
------------------------------------------------------------------------------------------
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的集合对象中的自定义类必须覆盖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;
- // 底层使用HashMap来保存HashSet中所有元素。
- private transient HashMap<E,Object> map;
- // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
- private static final Object PRESENT = new Object();
- /**
- * 默认的无参构造器，构造一个空的HashSet。
- *
- * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。
- */
- public HashSet() {
- map = new HashMap<E,Object>();
- }
- /**
- * 构造一个包含指定collection中的元素的新set。
- *
- * 实际底层使用默认的加载因子0.75和足以包含指定
- * collection中所有元素的初始容量来创建一个HashMap。
- * @param c 其中的元素将存放在此set中的collection。
- */
- public HashSet(Collection<? extends E> c) {
- map = new HashMap<E,Object>(Math.max(( int ) (c.size()/.75f) + 1 , 16 ));
- addAll(c);
- }
- /**
- * 以指定的initialCapacity和loadFactor构造一个空的HashSet。
- *
- * 实际底层以相应的参数构造一个空的HashMap。
- * @param initialCapacity 初始容量。
- * @param loadFactor 加载因子。
- */
- public HashSet( int initialCapacity, float loadFactor) {
- map = new HashMap<E,Object>(initialCapacity, loadFactor);
- }
- /**
- * 以指定的initialCapacity构造一个空的HashSet。
- *
- * 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。
- * @param initialCapacity 初始容量。
- */
- public HashSet( int initialCapacity) {
- map = new HashMap<E,Object>(initialCapacity);
- }
- /**
- * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
- * 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。
- *
- * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
- * @param initialCapacity 初始容量。
- * @param loadFactor 加载因子。
- * @param dummy 标记。
- */
- HashSet( int initialCapacity, float loadFactor, boolean dummy) {
- map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
- }
- /**
- * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。
- *
- * 底层实际调用底层HashMap的keySet来返回所有的key。
- * 可见HashSet中的元素，只是存放在了底层HashMap的key上，
- * value使用一个static final的Object对象标识。
- * @return 对此set中元素进行迭代的Iterator。
- */
- public Iterator<E> iterator() {
- return map.keySet().iterator();
- }
- /**
- * 返回此set中的元素的数量（set的容量）。
- *
- * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。
- * @return 此set中的元素的数量（set的容量）。
- */
- public int size() {
- return map.size();
- }
- /**
- * 如果此set不包含任何元素，则返回true。
- *
- * 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。
- * @return 如果此set不包含任何元素，则返回true。
- */
- public boolean isEmpty() {
- return map.isEmpty();
- }
- /**
- * 如果此set包含指定元素，则返回true。
- * 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e))
- * 的e元素时，返回true。
- *
- * 底层实际调用HashMap的containsKey判断是否包含指定key。
- * @param o 在此set中的存在已得到测试的元素。
- * @return 如果此set包含指定元素，则返回true。
- */
- public boolean contains(Object o) {
- return map.containsKey(o);
- }
- /**
- * 如果此set中尚未包含指定元素，则添加指定元素。
- * 更确切地讲，如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2))
- * 的元素e2，则向此set 添加指定的元素e。
- * 如果此set已包含该元素，则该调用不更改set并返回false。
- *
- * 底层实际将将该元素作为key放入HashMap。
- * 由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key
- * 与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true），
- * 新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变，
- * 因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中，
- * 原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。
- * @param e 将添加到此set中的元素。
- * @return 如果此set尚未包含指定元素，则返回true。
- */
- public boolean add(E e) {
- return map.put(e, PRESENT)== null ;
- }
- /**
- * 如果指定元素存在于此set中，则将其移除。
- * 更确切地讲，如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e，
- * 则将其移除。如果此set已包含该元素，则返回true
- * （或者：如果此set因调用而发生更改，则返回true）。（一旦调用返回，则此set不再包含该元素）。
- *
- * 底层实际调用HashMap的remove方法删除指定Entry。
- * @param o 如果存在于此set中则需要将其移除的对象。
- * @return 如果set包含指定元素，则返回true。
- */
- public boolean remove(Object o) {
- return map.remove(o)==PRESENT;
- }
- /**
- * 从此set中移除所有元素。此调用返回后，该set将为空。
- *
- * 底层实际调用HashMap的clear方法清空Entry中所有元素。
- */
- public void clear() {
- map.clear();
- }
- /**
- * 返回此HashSet实例的浅表副本：并没有复制这些元素本身。
- *
- <span
发表评论
评论