HashMap
参考：Java8 HashMap实现原理探究
特点
基于Hash表的Map接口实现线程非安全，并且允许key与value都为null值，HashTable与之相反，为线程安全，key与value都不允许null值。不保证映射的顺序，特别是它不保证顺序恒久不变，resize时会重排当数组没有链表存在时，HashMap性能最好为O(1)。而最差为O(threshould)即所有元素存在一个链表上。hashMap会根据存入的size和负载英子*数组初始容量进行扩容
数据结构
HashMap实际上是一个链表散列的数据结构，即数组和链表的结合体，HashMap底层就是一个数组结构，数组中的每一项又是一个链表
jdk8优化，如果数组某个位置链表长度超过8个会转成红黑树，jdk8之前一直是链表，链表查询的复杂度是O(n)，而红黑树由于其自身的特点，查询的复杂度是O(log(n))，会提高遍历性能
源码解析
构造函数初始化
1、initialCapacity：数组的初始化长度，2的n次方
2、loadFactor：负载英子，默认是0.75
3、threshold：最大容量，threshold=initialCapacity*loadFactor，当entry的数量超过capacity*loadFactor时，容器将自动扩容并重新哈希。
4、在对HashMap进行迭代时，需要遍历整个table以及后面跟的冲突链表。因此对于迭代比较频繁的场景，不宜将HashMap的初始大小设的过大。
5、增大负载因子可以减少数组所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作(HashMap 的 get() 与 put()方法都要用到查询)；减小负载因子会提高数据查询的性能，但会增加Hash表所占用的内存空间。
6、将对向放入到HashMap或HashSet中时，有两个方法需要特别关心：hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到HashMap或HashSet中，需要@Override hashCode()和equals()方法。
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(
loadFactor);
int capacity =
1;
while (capacity < initialCapacity)
capacity <<=
1;
this.loadFactor = loadFactor;
threshold = (
int)(capacity * loadFactor);
table =
new Entry[capacity];
init();
}
Entry对象，实现了单向链表
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
Entry(
int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final int hashCode() {
return (key==
null ?
0 : key.hashCode()) ^
(value==
null ?
0 : value.hashCode());
}
}
put方法
public V
put(K key, V
value) {
if (key ==
null)
return putForNullKey(
value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
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);
return oldValue;
}
}
modCount++;
addEntry(hash, key,
value, i);
return null;
}
处理key值为空的情况
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;
}
根据key的hash值进行hash运算，如果key的hash值一样，调用HashMap的hash运算后得到的结果是一样的
static int hash(
int h)
{
h ^= (h >>>
20) ^ (h >>>
12);
return h ^ (h >>>
7) ^ (h >>>
4);
}
HashMap对key值得hash值运算后获取table数组的下标table数组的长度总是2的n次方，默认是16，通过 & 运算得到的就是数组的下标，最大不会超过数组的长度,保证数组长度总是2的n次方，这样长度-1后二进制所有位置都是1，跟key的hash值进行&运算时会更加均匀的分布entry到数组上。
static
int indexFor(
int h,
int length)
{
return h & (
length-
1);
}
将entry存入数组中，如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上
void addEntry(
int hash, K key, V
value,
int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] =
new Entry<K,V>(hash, key,
value, e);
if (size++ >= threshold)
resize(
2 * table.length);
}
扩展数组的长度，每次扩展原数组长度的2倍，保证数组的长度为2的n次方，扩展的实质是创建一个2倍长度的新的数组，原数组中的entry必须重新计算其在新数组中的位置，并放进去，这就是resize。
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];
transfer(newTable);
table = newTable;
threshold = (
int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (
int j =
0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e !=
null) {
src[j] =
null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
while (e !=
null);
}
}
}
get方法
public V
get(Object key) {
if (key ==
null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e !=
null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.
value;
}
return null;
}
private V
getForNullKey() {
for (Entry<K,V> e = table[
0]; e !=
null; e = e.next) {
if (e.key ==
null)
return e.
value;
}
return null;
}
remove方法
public V
remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e ==
null ?
null : e.
value);
}
final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key ==
null) ?
0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e !=
null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key !=
null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(
this);
return e;
}
prev = e;
e = next;
}
return e;
}
迭代器实现
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() {
return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() {
return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() {
return nextNode(); }
}
abstract class HashIterator {
Node<K,V> next;
Node<K,V> current;
int expectedModCount;
int index;
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next =
null;
index =
0;
if (t !=
null && size >
0) {
do {}
while (
index < t.length && (next = t[
index++]) ==
null);
}
}
public final boolean hasNext() {
return next !=
null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e ==
null)
throw new NoSuchElementException();
if ((next = (current = e).next) ==
null && (t = table) !=
null) {
do {}
while (
index < t.length && (next = t[
index++]) ==
null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p ==
null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current =
null;
K key = p.key;
removeNode(hash(key), key,
null,
false,
false);
expectedModCount = modCount;
}
}
HashSet
hashSet是对HashMap的简单包装，对HashSet的函数调用都会转换成合适的HashMap方法，因此HashSet的实现非常简单，只有不到300行代码。这里不再赘述。
public class HashSet<E>
{
......
private transient HashMap<E,Object> map;
private static final Object PRESENT =
new Object();
public HashSet() {
map =
new HashMap<>();
}
......
public boolean
add(E e) {
return map.put(e, PRESENT)==
null;
}
......
}
