[java]
package java.util;
/*
1.HashSet中不允许重复元素
2.HashSet中大量调用了HashMap的方法，其内部封装了一个HashMap
*/
public class HashSet
extends AbstractSet
implements Set, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
//hashSet内部使用HashMap来存储元素，
private transient HashMap map;
//定义一个静态对象，作为所有key的value
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection< extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
public Iterator iterator() {
return map.keySet().iterator();
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
public Object clone() {
try {
HashSet newSet = (HashSet) super.clone();
newSet.map = (HashMap) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
}
HashSet内部封装了一个HashMap，将要存储的对象作为每个键值对中的key，然后采用静态变量对象PRESENT作为所有key的value。在看HashMap之前来讲讲什么叫做散列(hash) Hash的具体含义参见百度百科(hash)。简单的来说是指对所以的关键字，不直接采用关键字作为存储数组的下标，而是根据关键字计算出相应下标。hash的关键技术在于如何产生合适的hashcode，以及如何解决冲突(多个key映射到一个位置上)。hash表在查找方面上平均只需要O(1)的时间，也就是一找就到的节奏。在来看HashMap的内部实现。
[java]
package java.util;
import java.io.*;
/*
HashMap是线程不同步的，可以进行封装
Map m = Collections.synchronizedMap(new HashMap(...));
*/
public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable
{
/*
HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。
容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。
加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。
当哈希表中的条目数超出了加载因子与当前容量的乘积时，
则要对该哈希表进行 rehash 操作（即重建内部数据结构），
从而哈希表将具有大约两倍的桶数。
在Java
编程语言中，加载因子默认值为0.75，默认哈希表元为101
*/
//初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//用来存储键值对的Entry数组,用于设置刚刚初始化的HashMap对象,用来减少存储空间
static final Entry< , >[] EMPTY_TABLE = {};
//大小必须是2的倍数
transient Entry[] table = (Entry[]) EMPTY_TABLE;
//存储的键值对的数目
transient int si