又突然想看源码了，继续深入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);
}
}
}
