1、HashSet-底层数据结构

  1. 1、HashSet-底层数据结构：
  2.     1-1、HashSet这个类实现了Set集合，实际为一个HashMap的实例。
  3.     1-2、HashSet，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet 的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成。
  4.     1-3、HashSet属性字段有：
  5.         //底层使用HashMap来保存HashSet中所有元素。
  6.         private transient HashMap<E,Object> map;
  7.         //定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
  8.         private static final Object PRESENT = new Object();

2、HashSet-构造方法

  1. 1、HashSet底层是通过HashMap实现的。
  3.     /** 
  4.      * 默认的无参构造器，构造一个空的HashSet。 
  5.      *  
  6.      * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。 
  7.      */  
  8.     public HashSet() {  
  9.         map = new HashMap<E,Object>();  
  10.     }  
  12.     /** 
  13.      * 构造一个包含指定collection中的元素的新set。 
  14.      * 
  15.      * 实际底层使用默认的加载因子0.75和足以包含指定 
  16.      * collection中所有元素的初始容量来创建一个HashMap。 
  17.      * @param c 其中的元素将存放在此set中的collection。 
  18.      */  
  19.     public HashSet(Collection<? extends E> c) {  
  20.         map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));  
  21.         addAll(c);  
  22.     }  
  24.     /** 
  25.      * 以指定的initialCapacity和loadFactor构造一个空的HashSet。 
  26.      * 
  27.      * 实际底层以相应的参数构造一个空的HashMap。 
  28.      * @param initialCapacity 初始容量。 
  29.      * @param loadFactor 加载因子。 
  30.      */  
  31.     public HashSet(int initialCapacity, float loadFactor) {  
  32.         map = new HashMap<E,Object>(initialCapacity, loadFactor);  
  33.     }  
  35.     /** 
  36.      * 以指定的initialCapacity构造一个空的HashSet。 
  37.      * 
  38.      * 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。 
  39.      * @param initialCapacity 初始容量。 
  40.      */  
  41.     public HashSet(int initialCapacity) {  
  42.         map = new HashMap<E,Object>(initialCapacity);  
  43.     }  
  45.     /** 
  46.      * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。 
  47.      * 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。 
  48.      * 
  49.      * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。 
  50.      * @param initialCapacity 初始容量。 
  51.      * @param loadFactor 加载因子。 
  52.      * @param dummy 标记。 
  53.      */  
  54.     HashSet(int initialCapacity, float loadFactor, boolean dummy) {  
  55.         map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);  
  56.     }

3、HashSet-添加元素

  1. 1、HashSet的add方法时通过HashMap的put方法实现的，不过HashMap是key-value键值对，而HashSet是集合。
  2. 2、源码代码：
  3.     private static final Object PRESENT = new Object();
  5.     //HashSet添加的元素是存放在HashMap的key位置上，而value取了默认常量PRESENT，是一个空对象
  6.     public boolean add(E e) {
  7.         return map.put(e, PRESENT)==null;
  8.     }

4、HashSet-删除元素

  1. 1、HashSet的remove方法通过HashMap的remove方法来实现。
  2. 2、源码代码：
  3.     /**
  4.      * 底层实际调用HashMap的remove方法删除指定Entry。 
  5.      * @param o 如果存在于此set中则需要将其移除的对象。 
  6.      * @return 如果set包含指定元素，则返回true。
  7.      */
  8.     public boolean remove(Object o) {
  9.         return map.remove(o)==PRESENT;
  10.     }
  12.     //map的remove方法
  13.     public V remove(Object key) {
  14.         Node<K,V> e;
  15.         //通过hash(key)找到元素在数组中的位置，再调用removeNode方法删除
  16.         return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
  17.     }
  19.     //具体执行删除以及相关方法
  20.     final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {
  21.         Node<K,V>[] tab; Node<K,V> p; int n, index;
  22.         //步骤1.需要先找到key所对应Node的准确位置，首先通过(n - 1) & hash找到数组对应位置上的第一个node
  23.         if ((tab = table) != null && (n = tab.length) > 0 &&
  24.             (p = tab[index = (n - 1) & hash]) != null) {
  25.             Node<K,V> node = null, e; K k; V v;
  26.             //1.1 如果这个node刚好key值相同，运气好，找到了
  27.             if (p.hash == hash &&
  28.                 ((k = p.key) == key || (key != null && key.equals(k))))
  29.                 node = p;
  30.             /**
  31.              * 1.2 运气不好，在数组中找到的Node虽然hash相同了，但key值不同，很明显不对， 我们需要遍历继续
  32.              *     往下找；
  33.              */
  34.             else if ((e = p.next) != null) {
  35.                 //1.2.1 如果是TreeNode类型，说明HashMap当前是通过数组+红黑树来实现存储的，遍历红黑树找到对应node
  36.                 if (p instanceof TreeNode)
  37.                     node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
  38.                 else {
  39.                     //1.2.2 如果是链表，遍历链表找到对应node
  40.                     do {
  41.                         if (e.hash == hash &&
  42.                             ((k = e.key) == key ||
  43.                              (key != null && key.equals(k)))) {
  44.                             node = e;
  45.                             break;
  46.                         }
  47.                         p = e;
  48.                     } while ((e = e.next) != null);
  49.                 }
  50.             }
  51.             //通过前面的步骤1找到了对应的Node,现在我们就需要删除它了
  52.             if (node != null && (!matchValue || (v = node.value) == value ||
  53.                                  (value != null && value.equals(v)))) {
  54.                 /**
  55.                  * 如果是TreeNode类型，删除方法是通过红黑树节点删除实现的，具体可以参考【TreeMap原理实现
  56.                  * 及常用方法】
  57.                  */
  58.                 if (node instanceof TreeNode)
  59.                     ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
  60.                 /** 
  61.                  * 如果是链表的情况，当找到的节点就是数组hash位置的第一个元素，那么该元素删除后，直接将数组
  62.                  * 第一个位置的引用指向链表的下一个即可
  63.                  */
  64.                 else if (node == p)
  65.                     tab[index] = node.next;
  66.                 /**
  67.                  * 如果找到的本来就是链表上的节点，也简单，将待删除节点的上一个节点的next指向待删除节点的
  68.                  * next,隔离开待删除节点即可
  69.                  */
  70.                 else
  71.                     p.next = node.next;
  72.                 ++modCount;
  73.                 --size;
  74.                 //删除后可能存在存储结构的调整，可参考【LinkedHashMap如何保证顺序性】中remove方法
  75.                 afterNodeRemoval(node);
  76.                 return node;
  77.             }
  78.         }
  79.         return null;
  80.     }

5、HashSet-其他方法

  1. 1、HashSet-其他方法：.clear()、.clone()、.contains()、.iterator()、.size()、.isEmpty()等方法。
  2. 2、源码代码：
  4.     /** 
  5.      * 从此set中移除所有元素。此调用返回后，该set将为空。 
  6.      * 
  7.      * 底层实际调用HashMap的clear方法清空Entry中所有元素。 
  8.      */  
  9.     public void clear() {  
  10.         map.clear();  
  11.     }  
  13.     /** 
  14.      * 返回此HashSet实例的浅表副本：并没有复制这些元素本身。 
  15.      * 
  16.      * 底层实际调用HashMap的clone()方法，获取HashMap的浅表副本，并设置到HashSet中。 
  17.      */  
  18.     public Object clone() {  
  19.         try {  
  20.             HashSet<E> newSet = (HashSet<E>) super.clone();  
  21.             newSet.map = (HashMap<E, Object>) map.clone();  
  22.             return newSet;  
  23.         } catch (CloneNotSupportedException e) {  
  24.             throw new InternalError();  
  25.         }  
  26.     }  
  28.     /** 
  29.      * 如果此set包含指定元素，则返回true。 
  30.      * 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e)) 
  31.      * 的e元素时，返回true。 
  32.      * 
  33.      * 底层实际调用HashMap的containsKey判断是否包含指定key。 
  34.      * @param o 在此set中的存在已得到测试的元素。 
  35.      * @return 如果此set包含指定元素，则返回true。 
  36.      */  
  37.     public boolean contains(Object o) {  
  38.         return map.containsKey(o);  
  39.     }  
  41.     /** 
  42.      * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。 
  43.      *  
  44.      * 底层实际调用底层HashMap的keySet来返回所有的key。 
  45.      * 可见HashSet中的元素，只是存放在了底层HashMap的key上， 
  46.      * value使用一个static final的Object对象标识。 
  47.      * @return 对此set中元素进行迭代的Iterator。 
  48.      */  
  49.     public Iterator<E> iterator() {  
  50.         return map.keySet().iterator();  
  51.     }  
  53.     /** 
  54.      * 返回此set中的元素的数量（set的容量）。 
  55.      * 
  56.      * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。 
  57.      * @return 此set中的元素的数量（set的容量）。 
  58.      */  
  59.     public int size() {  
  60.         return map.size();  
  61.     }  
  63.     /** 
  64.      * 如果此set不包含任何元素，则返回true。 
  65.      * 
  66.      * 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。 
  67.      * @return 如果此set不包含任何元素，则返回true。 
  68.      */  
  69.     public boolean isEmpty() {  
  70.         return map.isEmpty();  
  71.     }