深入Java基础（四）--哈希表（2）HashTable与HashSet应用及源码详解

内容简介：深入Java基础（四）--哈希表（2）HashTable与HashSet应用及源码详解

又突然想看源码了，继续深入 Java 基础系列。今天是研究JavaAPI的HashTable和HashSet（顺带讨论线程安全问题）。

本系列：

（1） 深入Java基础（一）——基本数据类型及其包装类

（2） 深入Java基础（二）——字符串家族

（3） 深入Java基础（三）–集合（1）集合父类以及父接口源码及理解

（4） 深入Java基础（三）–集合（2）ArrayList和其继承树源码解析以及其注意事项

（5） 深入Java基础（四）–哈希表（1）HashMap应用及源码详解

文章结构：（1）HashTable和HashSet概述与基本操作（含线程安全讨论）；（2）HashTable源码分析；（3）HashSet源码分析。

一、HashTable和HashSet概述与基本操作（含线程安全讨论）：

（1）HashTable：

（一）概述（与HashMap对比进行讲述）： 此概述大部分参考此博客

1）同是散列表，存储的内容是键值对(key-value)映射。（相同点）

HashMap 是基于“拉链法”实现的散列表。

Hashtable 也是基于“拉链法”实现的散列表。

存取的模式也是相同

2）继承与实现的不同：

HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。

Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。

Dictionary是一个抽象类，它直接继承于Object类，没有实现任何接口。Dictionary类是JDK 1.0的引入的。虽然Dictionary也支持“添加key-value键值对”、“获取value”、“获取大小”等基本操作，但它的API函数比Map少；而且Dictionary一般是通过Enumeration(枚举类)去遍历，Map则是通过Iterator(迭代器)去遍历。 然而由于Hashtable也实现了Map接口，所以，它即支持Enumeration遍历，也支持Iterator遍历。

AbstractMap是一个抽象类，它实现了Map接口的绝大部分API函数；为Map的具体实现类提供了极大的便利。它是JDK 1.2新增的类。

3）线程安全不同：

Hashtable的几乎所有函数都是同步的，即它是线程安全的，支持多线程。

而HashMap的函数则是非同步的，它不是线程安全的。若要在多线程中使用HashMap，需要我们额外的进行同步处理（Collections类提供的synchronizedMap静态方法或者使用ConcurrentHashMap类）。

//HashMap可以通过下面的语句进行同步：
Map m = Collections.synchronizeMap(hashMap);

4）对null的处理不同：（一会源码解析，在put方法里）

HashMap的key、value都可以为null。

Hashtable的key、value都不可以为null。

Hashtable的key或value，都不能为null！否则，会抛出异常NullPointerException。

HashMap的key、value都可以为null。 当HashMap的key为null时，HashMap会将其固定的插入table[0]位置(即HashMap散列表的第一个位置)；而且table[0]处只会容纳一个key为null的值，当有多个key为null的值插入的时候，table[0]会保留最后插入的value。

5）支持的遍历种类不同：

HashMap只支持Iterator(迭代器)遍历。

而Hashtable支持Iterator(迭代器)和Enumeration(枚举器)两种方式遍历。

6）通过Iterator迭代器遍历时，遍历的顺序不同：

HashMap是“从前向后”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。

Hashtabl是“从后往前”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。

7）容量的初始值 和 增加方式都不一样：

HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”。

Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”。

8）添加key-value时的hash值算法不同

HashMap添加元素时，是使用自定义的哈希算法。

Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。

9）部分API不同：

Hashtable支持contains(Object value)方法，而且重写了toString()方法；

而HashMap不支持contains(Object value)方法，没有重写toString()方法。

但两者都有containsKey()方法

（二）基本操作：

public class TestHashTable {
   public static void main(String[] args){
       Hashtable <String, String> hashtable = new Hashtable();

       hashtable.put("1", "aa");
       hashtable.put("2", "bb");
       hashtable.put("3", "cc");
       hashtable.put("4", "dd");
        //[1]contains与containsKey方法
       if (hashtable.contains("aa")){
           System.out.println("contains");
       }
       if (hashtable.containsKey("1")){
           System.out.println("containsKey");
       }

       System.out.println("====================================");
       //[2]toString()方式打印
       System.out.println(hashtable.toString());
       System.out.println("====================================");
       //[3]Iterator遍历方式1--键值对遍历entrySet()
       Iterator<Map.Entry<String, String>> iter = hashtable.entrySet().iterator();
       while(iter.hasNext()){
           Map.Entry<String, String> entry = (Map.Entry<String, String>)iter.next();
           String key = entry.getKey();
           String value = entry.getValue();
           System.out.println("entrySet:"+key+" "+value);
       }

       System.out.println("====================================");

       //[4]Iterator遍历方式2--key键的遍历
       Iterator<String> iterator = hashtable.keySet().iterator();
       while(iterator.hasNext()){
           String key = (String)iterator.next();
           String value = hashtable.get(key);
           System.out.println("keySet:"+key+" "+value);
       }

       System.out.println("====================================");

       //[5]通过Enumeration来遍历Hashtable
       Enumeration<String> enu = hashtable.keys();
       while(enu.hasMoreElements()) {
           System.out.println("Enumeration:"+hashtable.keys()+" "+enu.nextElement());
       }


   }
}

（三）线程安全的讨论（含例子）：

1）我们先去测试探讨hashmap：

HashMap应用及源码详解 本系列上篇文章讲到其源码：

HashMap实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示： 
Map m = Collections.synchronizedMap(new HashMap(...));

可知大致是三个操作块是会出现并发问题：

1. HashMap中插入数据的时候

假如A线程和B线程同时进入addEntry，然后计算出了相同的哈希值对应了相同的数组位置，因为此时该位置还没数据，然后对同一个数组位置调用createEntry，两个线程会同时得到现在的头结点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。

2.HashMap扩容的时候

当多个线程同时进来，检测到总数量超过门限值的时候就会同时调用resize操作，各自生成新的数组并rehash后赋给该map底层的数组table，结果最终只有最后一个线程生成的新数组被赋给table变量，其他线程的均会丢失。而且当某些线程已经完成赋值而其他线程刚开始的时候，就会用已经被赋值的table作为原始数组，这样也会有问题。

3. 删除HashMap中数据的时候都容易出现线程安全问题。

删除这一块可能会出现两种线程安全问题，第一种是一个线程判断得到了指定的数组位置i并进入了循环，此时，另一个线程也在同样的位置已经删掉了i位置的那个数据了，然后第一个线程那边就没了。但是删除的话，没了倒问题不大。

再看另一种情况，当多个线程同时操作同一个数组位置的时候，也都会先取得现在状态下该位置存储的头结点，然后各自去进行计算操作，之后再把结果写会到该数组位置去，其实写回的时候可能其他的线程已经就把这个位置给修改过了，就会覆盖其他线程的修改。

例子验证：

//（注释的方式为线程不安全，没注释的是线程安全做法）
public class TestHashMapConcurrent {

    public static final HashMap<String, String> hashMap = new HashMap<String, String>();

    public static void main(String[] args) throws InterruptedException {
//就是在这里使用集合 工具 类，包装hashmap，使其线程安全
        //Collections.synchronizedMap(hashMap);
        //线程一
        Thread t1 = new Thread() {
            public void run() {
                for (int i = 0; i < 25; i++) {
                    hashMap.put(String.valueOf(i), String.valueOf(i));
                }
            }
        };
        //线程二
        Thread t2 = new Thread() {
            public void run() {
                for (int j = 25; j < 50; j++) {
                    hashMap.put(String.valueOf(j), String.valueOf(j));
                }
            }
        };

        t1.start();
        t2.start();

        //主线程休眠1秒钟，以便t1和t2两个线程将firstHashMap填装完毕。
        Thread.currentThread().sleep(1000);

        for (int l = 0; l < 50; l++) {
            //如果key和value不同，说明在两个线程put的过程中出现异常。
            if (!String.valueOf(l).equals(hashMap.get(String.valueOf(l)))) {
                System.err.println(String.valueOf(l) + ":" + hashMap.get(String.valueOf(l)));
            }
        }

    }
}

用这个例子跑多几次，就可以发现：key与value不对应。也可发现，是扩容或者增加键值导致的线程问题。

2）我们说过Hashtable是线程安全的,，例子说明，无论跑多少次都是key与value对应

public class ConcurrentTestHashTable {
    private static Map<String, String> hashtable = new Hashtable<String, String>();//定义个属性变量，方便内部多线程访问

    public static void main(String[] args) throws InterruptedException {

        //线程一
        Thread t1 = new Thread() {
            public void run() {
                for (int i = 0; i < 25; i++) {
                    hashtable.put(String.valueOf(i), String.valueOf(i));
                }
            }
        };
        //线程二
        Thread t2 = new Thread() {
            public void run() {
                for (int j = 25; j < 50; j++) {
                    hashtable.put(String.valueOf(j), String.valueOf(j));
                }
            }
        };

        t1.start();
        t2.start();

        //主线程休眠1秒钟，以便t1和t2两个线程将firstHashMap填装完毕。
        Thread.currentThread().sleep(1000);

        for (int l = 0; l < 50; l++) {
            //如果key和value不同，说明在两个线程put的过程中出现异常。
            if (!String.valueOf(l).equals(hashtable.get(String.valueOf(l)))) {
                System.err.println(String.valueOf(l) + ":" + hashtable.get(String.valueOf(l)));
            }
        }

    }
}

（2）HashSet：

（一）概述：

1）一个没有重复元素的集合。

2）由HashMap实现的，不保证元素的顺序，而且HashSet允许使用 null 元素。

3）HashSet是非同步的。如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须 保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作，以防止对该 set 进行意外的不同步访问：

Set s = Collections.synchronizedSet(new HashSet(...));

4）HashSet通过iterator()返回的迭代器是fail-fast的。

5）HashSet继承于AbstractSet，并且实现了Set接口。HashSet中含有一个”HashMap类型的成员变量”map，HashSet的操作函数，实际上都是通过map实现的。

（二）基本操作：

public class TestHashSet {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("a");
        hashSet.add("b");
        hashSet.add("c");
        hashSet.add("d");
        hashSet.add("e");
        System.out.println("创建一个ArrayList对象，添加两个元素");
        ArrayList list = new ArrayList();
        list.add("第6个元素");
        list.add("第7个元素");
        System.out.println("把ArrayList对象添加到HashSet中");
        hashSet.addAll(list);
        System.out.println("添加一个null元素");
        hashSet.add(null);
        System.out.println("==================Iterator遍历==================");
        /*
          * 通过Iterator遍历HashSet。推荐方式
          */
        Iterator iter = hashSet.iterator();
        while(iter.hasNext()){
            String value = (String)iter.next();
            System.out.println(value);
        }
        System.out.println("==================for-each遍历==================");
        /*
            通过for-each遍历HashSet。不推荐！此方法需要先将Set转换为数组
         */
        String[] arr = (String[])hashSet.toArray(new String[0]);
        for (String str:arr) {
            System.out.printf("for each : %s\n", str);
        }
    }
}

（三）关于HashSet线程安全问题讨论：

public class ConcurrentTestHashSet {
    private static final HashSet hashSet = new HashSet();
    public static void main(String[] args) throws InterruptedException {
        //线程一
        Thread t1 = new Thread() {
            public void run() {
                for (int i = 0; i < 50; i++) {
                    hashSet.add( String.valueOf(i));
                }
            }
        };

        //线程二
        Thread t2 = new Thread() {
            public void run() {
                Iterator iter = hashSet.iterator();
                while(iter.hasNext()){
                    String value = (String)iter.next();
                    System.out.print(value+"  ");
                }
                System.out.println();
            }
        };
        //线程3
        Thread t3 = new Thread() {
            public void run() {
                for (int i = 50; i < 100; i++) {
                    hashSet.add( String.valueOf(i));
                }
            }
        };

        t1.start();
        t2.start();
        t3.start();

        //主线程休眠1秒钟，以便t1、t2两个线程将firstHashMap填装完毕。
        Thread.currentThread().sleep(1000);


    }
}

当我们跑多几次就容易遇到。

如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么就很容易发送以下异常：

二、HashTable源码分析：

我们来看下hashtable的重要代码：

其实，跟HashMap差不多，扩容机制，增删原理等等，只不过就是在方法前加了synchronized 进行同步（注意hashtable在jdk1.8还没更新到红黑树结构）。不同的只是做了一些值限定。

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    // 保存key-value的数组。    
    // Hashtable同样采用单链表解决冲突，每一个Entry本质上是一个单向链表 
    private transient Entry<?,?>[] table;
     // Hashtable中键值对的数量 
    private transient int count;
    // 阈值，用于判断是否需要调整Hashtable的容量（threshold = 容量*加载因子）
    private int threshold;
     // 加载因子 
    private float loadFactor;
     // Hashtable被改变的次数，用于fail-fast机制的实现 
    private transient int modCount = 0;
    // 指定“容量大小”和“加载因子”的构造函数  
    public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }
    // 指定“容量大小”的构造函数
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }
    // 默认构造函数。    
    public Hashtable() {    
        // 默认构造函数，指定的容量大小是11；加载因子是0.75    
        this(11, 0.75f);    
    }    

    // 包含“子Map”的构造函数    
    public Hashtable(Map<? extends K, ? extends V> t) {    
        this(Math.max(2*t.size(), 11), 0.75f);    
        // 将“子Map”的全部元素都添加到Hashtable中    
        putAll(t);    
    }    

    public synchronized int size() {    
        return count;    
    }    

    public synchronized boolean isEmpty() {    
        return count == 0;    
    }    
    // 判断Hashtable是否包含“值(value)”    
    public synchronized boolean contains(Object value) {    
        //注意，Hashtable中的value不能是null，    
        // 若是null的话，抛出异常!    
        if (value == null) {    
            throw new NullPointerException();    
        }    

        // 从后向前遍历table数组中的元素(Entry)    
        // 对于每个Entry(单向链表)，逐个遍历，判断节点的值是否等于value    
        Entry tab[] = table;    
        for (int i = tab.length ; i-- > 0 ;) {    
            for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {    
                if (e.value.equals(value)) {    
                    return true;    
                }    
            }    
        }    
        return false;    
    }    
   public boolean containsValue(Object value) {    
        return contains(value);    
    } 
    // 判断Hashtable是否包含key    
    public synchronized boolean containsKey(Object key) {    
        Entry tab[] = table;    
        //计算hash值，直接用key的hashCode代替  
        int hash = key.hashCode();      
        // 计算在数组中的索引值   
        int index = (hash & 0x7FFFFFFF) % tab.length;    
        // 找到“key对应的Entry(链表)”，然后在链表中找出“哈希值”和“键值”与key都相等的元素    
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {    
            if ((e.hash == hash) && e.key.equals(key)) {    
                return true;    
            }    
        }    
        return false;    
    }    

    // 返回key对应的value，没有的话返回null    
    public synchronized V get(Object key) {    
        Entry tab[] = table;    
        int hash = key.hashCode();    
        // 计算索引值，    
        int index = (hash & 0x7FFFFFFF) % tab.length;    
        // 找到“key对应的Entry(链表)”，然后在链表中找出“哈希值”和“键值”与key都相等的元素    
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {    
            if ((e.hash == hash) && e.key.equals(key)) {    
                return e.value;    
            }    
        }    
        return null;    
    }    
    // 调整Hashtable的长度，将长度变成原来的2倍+1   
    protected void rehash() {    
        int oldCapacity = table.length;    
        Entry[] oldMap = table;    

        //创建新容量大小的Entry数组  
        int newCapacity = oldCapacity * 2 + 1;    
        Entry[] newMap = new Entry[newCapacity];    

        modCount++;    
        threshold = (int)(newCapacity * loadFactor);    
        table = newMap;    

        //将“旧的Hashtable”中的元素复制到“新的Hashtable”中  
        for (int i = oldCapacity ; i-- > 0 ;) {    
            for (Entry<K,V> old = oldMap[i] ; old != null ; ) {    
                Entry<K,V> e = old;    
                old = old.next;    
                //重新计算index  
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;    
                e.next = newMap[index];    
                newMap[index] = e;    
            }    
        }    
    }    
    // 将“key-value”添加到Hashtable中    
    public synchronized V put(K key, V value) {    
        // Hashtable中不能插入value为null的元素！！！    
        if (value == null) {    
            throw new NullPointerException();    
        }    

        // 若“Hashtable中已存在键为key的键值对”，    
        // 则用“新的value”替换“旧的value”    
        Entry tab[] = table;    
        int hash = key.hashCode();    
        int index = (hash & 0x7FFFFFFF) % tab.length;    
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {    
            if ((e.hash == hash) && e.key.equals(key)) {    
                V old = e.value;    
                e.value = value;    
                return old;    
                }    
        }    

        // 若“Hashtable中不存在键为key的键值对”，  
        // 将“修改统计数”+1    
        modCount++;    
        //  若“Hashtable实际容量” > “阈值”(阈值=总的容量 * 加载因子)    
        //  则调整Hashtable的大小    
        if (count >= threshold) {  
            rehash();    

            tab = table;    
            index = (hash & 0x7FFFFFFF) % tab.length;    
        }    

        //将新的key-value对插入到tab[index]处（即链表的头结点）  
        Entry<K,V> e = tab[index];           
        tab[index] = new Entry<K,V>(hash, key, value, e);    
        count++;    
        return null;    
    }    

    // 删除Hashtable中键为key的元素    
    public synchronized V remove(Object key) {    
        Entry tab[] = table;    
        int hash = key.hashCode();    
        int index = (hash & 0x7FFFFFFF) % tab.length;    

        //从table[index]链表中找出要删除的节点，并删除该节点。  
        //因为是单链表，因此要保留带删节点的前一个节点，才能有效地删除节点  
        for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {    
            if ((e.hash == hash) && e.key.equals(key)) {    
                modCount++;    
                if (prev != null) {    
                    prev.next = e.next;    
                } else {    
                    tab[index] = e.next;    
                }    
                count--;    
                V oldValue = e.value;    
                e.value = null;    
                return oldValue;    
            }    
        }    
        return null;    
    }    
     // 清空Hashtable    
    // 将Hashtable的table数组的值全部设为null    
    public synchronized void clear() {    
        Entry tab[] = table;    
        modCount++;    
        for (int index = tab.length; --index >= 0; )    
            tab[index] = null;    
        count = 0;    
    }  
    .
    .
    .
    .
    .
    //其余都是跟HashMap的处理基本一样的，只是加了同步锁。同样使用链地址法处理冲突。
}

再次总结重申与HashMap的的比对：

1）二者的存储结构和解决冲突的方法都是相同的。（jdk1.7之前，jdk1.8后，hashmap加入了结构转化–红黑树）

2）HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。

3）Hashtable中key和value都不允许为null，而HashMap中key和value都允许为null（key只能有一个为null，而value则可以有多个为null）。但是如果在Hashtable中有类似put(null,null)的操作，编译同样可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常，这是JDK的规范规定的。

源码见上面。

如果value为null，会直接抛出NullPointerException异常，但源码中并没有对key是否为null判断！不过NullPointerException属于RuntimeException异常，是可以由JVM自动抛出的，也许对key的值在JVM中有所限制吧。

4）Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。

5）Hashtable计算hash值，直接用key的hashCode()，而HashMap重新计算了key的hash值，Hashtable在求hash值对应的位置索引时，用取模运算，而HashMap在求位置索引时，则用与运算，且这里一般先用hash&0x7FFFFFFF后，再对length取模，&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而&0x7FFFFFFF后，只有符号外改变，而后面的位都不变。

6）还有遍历方式，因为与HashMap继承不同。

三、HashSet源码分析：

它是基于HashMap实现的。HashSet底层采用HashMap来保存元素，请先阅读我的另一篇博客： 哈希表（1）HashMap应用及源码详解

注意：

对于HashSet中保存的对象，请注意正确重写其equals和hashCode方法，以保证放入的对象的唯一性。

所有放入HashSet中的集合元素实际上由HashMap的key来保存，而HashMap的value则存储了一个PRESENT，它是一个静态的Object对象。

将一个key-value对放入HashMap中时，首先根据key的hashCode()返回值决定该Entry的存储位置，如果两个key的hash值相同，那么它们的存储位置相同。如果这个两个key的equalus比较返回true。那么新添加的Entry的value会覆盖原来的Entry的value，key不会覆盖。因此,如果向HashSet中添加一个已经存在的元素，新添加的集合元素不会覆盖原来已有的集合元素。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;
 // HashSet是通过map(HashMap对象)保存内容的
    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    // 定义一个虚拟的Object PRESENT是向map中插入key-value对应的value
    // 因为HashSet中只需要用到key，而HashMap是key-value键值对；
    // 所以，向map中添加键值对时，键值对的值固定是PRESENT
    private static final Object PRESENT = new Object();
    // 默认构造函数 底层创建一个HashMap
    public HashSet() {
    // 调用HashMap的默认构造函数，创建map
        map = new HashMap<>();
    }
    // 带集合的构造函数
    public HashSet(Collection<? extends E> c) {
        /* 创建map。
         为什么要调用Math.max((int) (c.size()/.75f) + 1, 16)，从 (c.size()/.75f) + 1 和 16 中选择一个比较大的树呢？        
         首先，说明(c.size()/.75f) + 1
           因为从HashMap的效率(时间成本和空间成本)考虑，HashMap的加载因子是0.75。
           当HashMap的“阈值”(阈值=HashMap总的大小*加载因子) < “HashMap实际大小”时，
           就需要将HashMap的容量翻倍。
           所以，(c.size()/.75f) + 1 计算出来的正好是总的空间大小。
         接下来，说明为什么是 16 。
           HashMap的总的大小，必须是2的指数倍。若创建HashMap时，指定的大小不是2的指数倍；
           HashMap的构造函数中也会重新计算，找出比“指定大小”大的最小的2的指数倍的数。
           所以，这里指定为16是从性能考虑。避免重复计算。
           */
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        // 将集合(c)中的全部元素添加到HashSet中
        addAll(c);
    }
    // 指定HashSet初始容量和加载因子的构造函数
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
    // 指定HashSet初始容量的构造函数
     public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
    // 返回HashSet的迭代器
    public Iterator<E> iterator() {
    // 实际上返回的是HashMap的“key集合的迭代器”
        return map.keySet().iterator();
    }
    //调用HashMap的size()方法返回Entry的数量，得到该Set里元素的个数
    public int size() {
        return map.size();
    }
    //调用HashMap的isEmpty()来判断HaspSet是否为空
   //HashMap为null。对应的HashSet也为空
     public boolean isEmpty() {
        return map.isEmpty();
    }
     //调用HashMap的containsKey判断是否包含指定的key
    //HashSet的所有元素就是通过HashMap的key来保存的
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    // 将元素(e)添加到HashSet中，也就是将元素作为Key放入HashMap中
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    // 删除HashSet中的元素(o)，其实是在HashMap中删除了以o为key的Entry
     public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
//清空HashMap的clear方法清空所有Entry
    public void clear() {
        map.clear();
    }

    // 克隆一个HashSet，并返回Object对象
    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);
        }
    }
    // java.io.Serializable的写入函数
    // 将HashSet的“总的容量，加载因子，实际容量，所有的元素”都写入到输出流中
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out HashMap capacity and load factor
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());

        // Write out size
        s.writeInt(map.size());

        // Write out all elements in the proper order.
        for (E e : map.keySet())
            s.writeObject(e);
    }

    // java.io.Serializable的读取函数
    // 将HashSet的“总的容量，加载因子，实际容量，所有的元素”依次读出
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read capacity and verify non-negative.
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }

        // Read load factor and verify positive and non NaN.
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }

        // Read size and verify non-negative.
        int size = s.readInt();
        if (size < 0) {
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }

        // Set the capacity according to the size and load factor ensuring that
        // the HashMap is at least 25% full but clamping to maximum capacity.
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                HashMap.MAXIMUM_CAPACITY);

        // Create backing HashMap
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));

        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
                E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }
}

再次总结重申与HashMap的的比对：

1）HashMap实现了Map接口，HashSet实现了Set接口

2）HashMap储存键值对，HashSet仅仅存储对象

3）HashMap使用put()方法将元素放入map中，HashSet使用add()方法将元素放入set中

4）HashMap中使用键对象来计算hashcode值，HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false

5）HashMap比较快，因为是使用唯一的键来获取对象；HashSet较HashMap来说比较慢

好了，深入Java基础（四）–哈希表（2）HashTable与HashSet应用及源码详解讲完了，又是一篇源码阅读记录，这是积累的必经一步，我会继续出这个系列文章，分享经验给大家。欢迎在下面指出错误，共同学习！！你的点赞是对我最好的支持！！

更多内容，可以访问JackFrost的博客

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• JDK SPI源码详解
• 【zookeeper源码】启动流程详解
• 详解RunLoop之源码分析
• 详解CopyOnWrite容器及其源码
• React Scheduler 源码详解（1）
• React Scheduler 源码详解（2）

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。