java集合（二）----HashSet源码解析

关于HashSet的图如下图所示：

从上图可以看出HashSet是Set接口的一个实现类，HashSet按Hash算法来存储集合中的元素，因此具有好的存取和查找性能。

HashSet具有以下特点：

1，不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也可能发生变化

2，HashSet不是同步的。就是说，如果多个线程同时访问一个HashSet，假设有两个或者两个以上的线程同时修改了HashSet集合时，则必须通过代码来保证其同步

3，集合元素值可以是null

以上是简单的介绍HashSet，下面来看看HashSet的源码：

一、HashSet源码介绍：

1，HashSet（）方法：

public HashSet() {
        map = new HashMap<>();
    }
           

源码解析：

*功能：无参构造函数

*源码思路：构造一个新的空的HashMap实例，它有默认的初始化容量，容量为16，负载数为0.75

2，public HashSet(Collection<? extends E> c)方法：

public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
           

源码分析：

-功能：构造一个新的set集合的构造函数，该构造函数包含集合c中的元素

-源码思路：

-如果c的值是null，则跑出异常

3，public HashSet(int initialCapacity, float loadFactor)方法

public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
           

源码解析：

• 功能：构造一个新的set集合的构造函数，参数initialCapacity为hash map的初始容量，loadFactor为hashset的装载系数

4. public HashSet(int initialCapacity)方法

public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
           

源码解析：

• 功能：构造一个新的set集合的构造函数，参数initialCapacity为hash map的初始容量

5. HashSet(int initialCapacity, float loadFactor, boolean dummy)方法：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
           

源码解析：

• 功能：构造一个新的，空的LinkedHashSet，这个构造函数只适用于LinkedHashSet

6. public Iterator iterator()方法：

public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
           

源码解析：

• 功能：返回集合的迭代器，通过调用map对象的keySet方法，获取set集合的所有值

源码思路：

• Set集合的操作都是通过map集合实现的，集合的返回元素的顺序是随机的，没有顺序

7. public int size()方法：

public int size() {
        return map.size();
    }
           

源码解析：

• 功能：返回集合中元素的个数

源码思路：

• 调用map的size方法

8. public boolean isEmpty()方法：

public boolean isEmpty() {
        return map.isEmpty();
    }
           

源码解析：

• 功能：判断集合是否为空

源码思路：

• 调用map的isEmpty方法，来判断集合是否为空

9. public boolean contains(Object o)方法：

public boolean contains(Object o) {
        return map.containsKey(o);
    }
           

源码解析：

• 功能：判断集合中是否包含元素o

源码思路：

• 调用map的containsKey方法，来判断o是否在集合中，Set集合实际存储在map中，set的值存储为map集合的键。

10. public boolean add(E e)方法：

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
           

源码解析：

• 功能：向集合中添加元素e
• 源码思路：
• （1）调用map的put方法，将元素e插入到集合中，作为map的键存储起来，键对应的值为HashSet类的PRESENT成员变量
• （2）如果集合中已经包含元素e，则不改变原集合，返回false；如果集合中不包含元素e，则向集合中添加元素e，返回true

11. public boolean remove(Object o)方法：

public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
           

源码解析：

• 功能：将集合中的元素o移除
• 源码思路：
• （1）如果集合中存在元素o，则将其从集合中移除；
• （2）这里面牵扯到一个问题：就是当容器类对象在调用remove、contains等方法时需要比较对象是否相等，这会涉及到对象类型的equals方法和hashCode方法。对于这一点稍后解释。

12. public void clear()方法：

源码解析：

• 功能：将集合中的全部元素移除
• 源码思路：
  • 通过map的clear方法将集合中的元素全部移除

13. public Object clone()方法：

@SuppressWarnings("unchecked")
    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(e);
        }
    }
           

源码解析：

• 功能：浅拷贝
• 源码思路：
  • 该方法只是完成了浅拷贝，集合中的元素本身没有被拷贝

二、HashSet注意事项：

1，当向集合中添加（add）、删除（remove）、是否包含（contains）：

• 当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode（）方法来得到该对象的hashCode值，然后根据该hashCode值决定在HashSet中的存储位置。如果两个元素通过equals（）方法比价返回true，但它们的hashCode（）方法返回值不相等，HashSet会将它们存储在不同的位置，仍然可以添加成功。
• 也就是说，HashSet集合判断两个元素是否相等的标准是两个对象通过equlas（）方法比较相等，并且两个对象的hashCode（）方法返回值也相等。
• 对于自定义类型，需要重写equals和hashCode方法（什么时候能用到hashCode方法？一般来说，当这个对象用在map接口里面，作为“键”使用时，会用到hashCode方法，因为hashCode的效率会更高。）

2，原则：

• 当把一个对象放入HashSet中时，如果需要重写该对象对应类的equals（）方法，则也应该需要重写其hashCode方法。规则就是：如果两个对象通过equals（）方法比较返回true，这两个对象的hashCode值也应该相同。

三、hashCode对于HahSet是个怎样的地位？

• 首先，hash算法的功能是：它能保证快速查找被检索的对象，hash算法的价值在于速度。当需要查询集合中某个元素时，hash算法可以直接根据元素的hashCode值计算出该元素的存储位置，从而快速定位该元素。就像数组里的索引，从表面看起来，HashSet集合里面的元素都没有索引，实际上当程序向HashSet集合中添加元素时，HashSet会根据该元素的hashCode值来计算它的存储位置，这样也可以快速定位该元素。
• 为什么不使用数组呢？因为数组元素的索引是连续的，而且数组的长度是固定的，无法自由添加数组的长度。而HashSet是采用每个元素的hashCode值来计算器存储位置，从而可以自由添加HashSet的长度，并可以根据元素的hashCode值来访问元素，因此，当以HashSet中访问元素时，HashSet先计算该元素的hashCode值（也就是调用该对象的hashCode方法的返回值），然后直接到该hashCode值对应的位置去取出该元素-------这就是HashSet速度很快的原因了。

四、重写hashCode（）方法的基本原则：

1，在程序运行过程中，同一个对象多次调用hashCode（）方法应该返回相同的值

2，当两个对象通过equals（）方法比较返回true时，这两个对象的hashCode（）方法应返回相等的值

3，对象中用作equals（）方法比较标准的实例变量，都应该用于计算hashCode值

注意：当向HashSet中添加可变对象时，必须十分小心。如果修改HahSet集合中的对象，有可能导致该对象与集合中的其他对象相等，从而导致HashSet无法准确访问对象。