又突然想看源码了，继续深入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类）。
|
1 2 3 |
//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()方法
（二）基本操作：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
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应用及源码详解本系列上篇文章讲到其源码：
|
1 2 3 |
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位置的那个数据了，然后第一个线程那边就没了。但是删除的话，没了倒问题不大。
再看另一种情况，当多个线程同时操作同一个数组位置的时候，也都会先取得现在状态下该位置存储的头结点，然后各自去进行计算操作，之后再把结果写会到该数组位置去，其实写回的时候可能其他的线程已经就把这个位置给修改过了，就会覆盖其他线程的修改。
例子验证：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
//（注释的方式为线程不安全，没注释的是线程安全做法） 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对应
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
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 进行意外的不同步访问：
|
1 2 |
Set s = Collections.synchronizedSet(new HashSet(...)); |
4）HashSet通过iterator()返回的迭代器是fail-fast的。
5）HashSet继承于AbstractSet，并且实现了Set接口。HashSet中含有一个”HashMap类型的成员变量”map，HashSet的操作函数，实际上都是通过map实现的。
（二）基本操作：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
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线程安全问题讨论：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
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还没更新到红黑树结构）。不同的只是做了一些值限定。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 |
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中添加一个已经存在的元素，新添加的集合元素不会覆盖原来已有的集合元素。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 |
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的博客
码字很辛苦，转载请注明来自JackFrost的《深入Java基础（四）–哈希表（2）HashTable与HashSet应用及源码详解》
Leave a Reply