HashSet
当初始化一个HashSet的时候，HashSet的底层实现其实是HashMap：
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}在每一个方法里面都是会通过map去调用HashMap的方法来实现。那么map是键值对类型的，那在HashSet中是怎么添加数据的呢？下面是HashSet中的添加方法。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}put的时候，e是要保存的key值，那后边的final变量呢是什么？
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();Dummy的意思就是‘虚假的’意思，也就是说当使用add方法将对象添加到Set当中时，实际上是将该对象作为底层所维护的Map对象的key，而value则都是同一个Object对象（该对象我们用不上）。
HashMap
HashMap在初始化的时候，会制定初始容量（16）和加载因子（扩容临界值0.75，意思就是当容量达到10*0.75=12的时候就会扩容）：
//默认初始化化容量,即16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//默认装载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap(int initialCapacity, float loadFactor) {//可手动设置初始容量和装载因子的构造器
if (initialCapacity < 0) //参数有效性检查
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) //参数有效性检查
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor)) //参数有效性检查
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
// Find a power of 2 >= initialCapacity
//找出“大于initialCapacity”的最小的2的幂
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化桶数组
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();//一个钩子函数，默认实现是空
}
//通过扩容因子构造HashMap,容量去默认值，即16
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//使用默认的初始容量和默认的加载因子构造HashMap
public HashMap() {
//制定初始容量和加载因子
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//通过其他Map来初始化HashMap,容量通过其他Map的size来计算，装载因子取0.75
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);//初始化HashMap底层的数组结构
putAllForCreate(m);//添加m中的元素
} 在HashMap的内部通过Entry数组来保存键值对，那个这个Entry是怎么实现的呢？
static class Entry<K,V> implements Map.Entry<K,V> {//实现Map.Entry接口
final K key;//键,final类型，不可更改/
V value;//值
Entry<K,V> next;//HashMap通过链表法解决冲突，这里的next指向链表的下一个元素
int hash;//hash值
/**
* Creates new entry.
*/
//构造器需指定链表的下一个结点,所有冲突结点放到一个链表上
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
//允许设置value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
//保证键值都相等
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {//键为空则hash值为0，否则通过通过hashcode计算
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
} HashMap内部数组存储的是键值对，也就是Entry对象，Entry对象保存了键、值，并持有一个next指针指向下一个Entry对象（HashMap通过链表法解决冲突）：
我们都知道HashMap是通过数组来存储的，那如何通过链表法来解决冲突的呢？举个栗子，定义一个HashMap，当调用put的时候，会根据key的hashCode值计算出一个位置，也就是要存储在数组中的位置，如果这个位置没有对象，就将该对象直接放进数组中：
如果该位置已经有对象了，则顺着此存在的对象的链开始寻找（Entry类有一个Entry类型的next成员变量，指向了该对象的下一个对象）：
如果此链上有对象的话，就去使用equals方法进行比较，如果对此链上某个对象的equals方法比较为false，就把改对象放到数组中，将数组中该位置以前存在的那个对象链接到次对象的后面。
HashMap存值的时候，遵循的是LRU（Least Recently Used）算法，就是最近最少使用，意思就是系统认为最近使用的值可能会被系统经常用到，而添加的早的值用到的几率会小。
着重的说一说HashMap核心的东西，就是HashMap在存数据的时候，也就是当你进行put操作的时候，HashMap是如何来进行存的。
//添加元素
public V put(K key, V value) {
if (table == EMPTY_TABLE) {//如果底层表为空，则初始化
inflateTable(threshold);
}
if (key == null)//如果key为空，则执行空的逻辑
return putForNullKey(value);
int hash = hash(key);//获取key的Hash值
int i = indexFor(hash, table.length);//定位Hash桶
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);//调用value的回调函数，其实这个函数也为空实现
return oldValue;
}
}
modCount++;//更新修改次数
addEntry(hash, key, value, i);//添加到对应Hash桶的链接表中
return null;
}
//添加key为空的元素，key为null的元素添加到第0号Hash桶中
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {//判断元素
V oldValue = e.value;//如果已经存在，修改值
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;//更新修改次数
addEntry(0, null, value, 0);//执行链表插入
return null;
} 不允许两个键相同，如果相同，则后插入的键所对应的值会覆盖掉之前的值。
HashMap是通过调用hash()方法获得键的hash值，并通过indexFor方法找到实际插入位置，具体的代码如下：
final int hash(Object k) {//根据键生成hash值
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//根据hash值计算键在桶数组的位置
static int indexFor(int h, int length) {
return h & (length-1);//由put方法可知，这个length就是数组长度，而且由构造器发现数组长度始终为2的整数次方，那么这个&操作实际上就是是h%length的高效表示方式,可以使结果小于数组长度.
} put方法通过addEntry方法将键值插入到合适的位置，当容量查过阈值（threshold）时，会发生扩容，扩容一倍。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {//容量超过阈值
resize(2 * table.length);//数组扩容为原来的两倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];//获取原来在该位置上的Entry对象
table[bucketIndex] = new Entry<>(hash, key, value, e);//将当前的键值插到该位置，并作为链表的起始结点。其next指针指向先前的Entry
size++;
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];//创建新数组
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
transfer(newTable, rehash);//将原数组中所有键值对转移至新数组
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {//需遍历每个Entry,耗时
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
} 扩容操作需要开辟新数组，并对原数组中所有键值对重新散列，非常耗时。我们应该尽量避免HashMap扩容。
