自定义一个HashSet

HashSet特点和底层实现

• HashSet底层是HashMap；

• 向Hashset中添加元素, 实际上是把这个元素作为键添加到底层的HashMap中；

• HashSet实际上就是底层HashMap的键的集合。

HashSet是采用哈希算法实现，底层实际是用HashMap实现的(HashSet本质就是一个简化版的HashMap)，因此，查询效率和增删效率都比较高。查看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;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }
    
     /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element <tt>e</tt> to this set if
     * this set contains no element <tt>e2</tt> such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns <tt>false</tt>.
     *
     * @param e element to be added to this set
     * @return <tt>true</tt> if this set did not already contain the specified
     * element
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    //以下代码省略
}

可以发现里面有个map属性，这就是HashSet的核心秘密。再看add()方法，可以发现增加一个元素，说白了就是在map中增加一个键值对，键对象就是这个元素，值对象是名为PRESENT的Object对象。说白了就是“往set中加入元素，本质就是把这个元素作为key加入到了内部的map中”。

由于map中key都是不可重复的，因此，Set天然具有“不可重复”的特性。

自定义一个HashSet，体会底层原理

代码如下：

package com.msl.mycollection;

import java.util.HashMap;

/**
 * 手动实现一个HashSet，深刻理解HashSet底层原理
 * @author Senley
 *
 */
public class MslHashSet {
    HashMap map;
    private static final Object PRESENT = new Object();
    
    public static void main(String[] args) {
        MslHashSet set = new MslHashSet();
        set.add("aaa");
        set.add("bbb");
        set.add("ccc");
        System.out.println(set);
    }
    
    public MslHashSet(){
        map = new HashMap();
    }
    
    public int size() {
        return map.size();
    }
    
    public void add(Object o) {
        map.put(o, PRESENT);
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(Object key:map.keySet()) {
            sb.append(key+",");
        }
        sb.setCharAt(sb.length()-1, ']');
        return sb.toString();
    }
}

结果如下：

[aaa,ccc,bbb]