public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable
{
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
擴(kuò)容臨界點(diǎn)【當(dāng)size>threshold蚁廓，將resize】
* The next size value at which to resize (capacity * load factor).
* @serial
*/
int threshold;
/**
總結(jié)：當(dāng)負(fù)載因子較大時(shí)销斟，【threshold較大】尘惧，去給table數(shù)組擴(kuò)容的可能性就會(huì)少城侧，所以相對(duì)占用內(nèi)存較少（空間上較少），但是每條entry鏈上的元素會(huì)相對(duì)較多恶复，查詢的時(shí)間也會(huì)增長(zhǎng)（時(shí)間上較多）胆筒。反之就是朽色，負(fù)載因子較少的時(shí)候，【threshold較大】齿兔，給table數(shù)組擴(kuò)容的可能性就高橱脸，那么內(nèi)存空間占用就多，但是entry鏈上的元素就會(huì)相對(duì)較少分苇，查出的時(shí)間也會(huì)減少添诉。所以才有了負(fù)載因子是時(shí)間和空間上的一種折中的說法。所以設(shè)置負(fù)載因子的時(shí)候要考慮自己追求的是時(shí)間還是空間上的少医寿。
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
//HashMap多線程處理之 Fail-Fast機(jī)制：http://www.cnblogs.com/alexlo/archive/2013/03/14/2959233.html
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash).? This field is used to make iterators on Collection-views of
* the HashMap fail-fast.? (See ConcurrentModificationException).
*/
transient int modCount;
//內(nèi)存可見性：通俗來(lái)說就是栏赴，線程A對(duì)一個(gè)volatile變量的修改，對(duì)于其它線程來(lái)說是可見的靖秩，即線程每次獲取volatile變量的值都是最新的须眷。
? ? /** Float.isNaN()
*static public boolean isNaN(float v) {
*? ? ? ? return (v != v);
*? ? }
*/
/**
* Constructs an empty HashMap with the specified initial
* capacity and the default load factor (0.75).
*
* @param? initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
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);
//這里做了一個(gè)移位運(yùn)算竖瘾，保證了初始容量一定為2的冪，假如你傳的是5花颗，那么最終的初始容量為8
//設(shè)置initCapacity的時(shí)候捕传，盡量設(shè)置為2的冪，這樣會(huì)去掉計(jì)算比initCapactity大捎稚，且為2的冪的數(shù)的運(yùn)算
// Find a power of 2 >= initialCapacity
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();
}
/**
* Constructs an empty HashMap with the specified initial
* capacity and the default load factor (0.75).
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty HashMap with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
private void putAllForCreate(Map m) {
for (Map.Entry e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
private void putForCreate(K key, V value) {
int hash = null == key ? 0 : hash(key);
int i = indexFor(hash, table.length);
/**
* Look for preexisting entry for key.? This will never happen for
* clone or deserialize.? It will only happen for construction if the
* input Map is a sorted map whose ordering is inconsistent w/ equals.
*/
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
createEntry(hash, key, value, i);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
static class Entry implements Map.Entry {
final K key;
V value;
Entry next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
/**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions.? This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
//Null鍵的散列碼總是0
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* Returns the number of key-value mappings in this map.
*
* @return the number of key-value mappings in this map
*/
public int size() {
return size;
}
/**
* Returns true if this map contains no key-value mappings.
*
* @return true if this map contains no key-value mappings
*/
public boolean isEmpty() {
return size == 0;
}
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//HashMap底層結(jié)構(gòu)是Entry數(shù)組乐横，而數(shù)組中每個(gè)元素又是一個(gè)Entry鏈表，元素的位置由hash code決定
//對(duì)于Null作為k的Entry, hash code始終是0今野，index也為0，但index為0的位置的鏈表中還有非Null鍵的元素罐农，所以要遍歷鏈表
private V getForNullKey() {
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
final Entry getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);//獲取到key的散列碼
? ? ? ? //根據(jù)散列碼找到Entry在數(shù)組中存放的位置条霜，再遍歷該位置上的Entry鏈表
? ? ? ? for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
/**
* Returns index for hash code h.
*根據(jù)hash code返回Entry在數(shù)組中的存放位置
*/
//當(dāng)容量一定是2^n時(shí)，h & (length - 1) == h % length涵亏，它倆是等價(jià)不等效的宰睡，位運(yùn)算效率非常高，
//實(shí)際開發(fā)中气筋，很多的數(shù)值運(yùn)算以及邏輯判斷都可以轉(zhuǎn)換成位運(yùn)算拆内，但是位運(yùn)算通常是難以理解的，因?yàn)槠浔旧砭褪墙o電腦運(yùn)算的宠默，運(yùn)算的是二進(jìn)制麸恍，
//而不是給人類運(yùn)算的，人類運(yùn)算的是十進(jìn)制搀矫，這也是位運(yùn)算在普遍的開發(fā)者中間不太流行的原因(門檻太高)抹沪。
static int indexFor(int h, int length) {
return h & (length-1);
}
//是否包含指定的key
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.【相同key,value會(huì)被覆蓋】
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
//每次put都要遍歷table[i],確保不存在才添加
? ? ? ? for (Entry 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;
}
private V putForNullKey(V value) {
for (Entry 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;
}
/**
下面來(lái)看看addEntry方法，參數(shù)bucketIndex就是當(dāng)前元素應(yīng)該插入到entry數(shù)組的下標(biāo)瓤球，先取出放在此位置的entry融欧，然后把當(dāng)前元素放入該數(shù)組中，當(dāng)前元素的next指向之前取出元素卦羡，形成entry鏈表噪馏。（描述的不是很清楚，大概就是把新加入的entry當(dāng)成頭放入到數(shù)組當(dāng)中绿饵，然后指向之前的鏈表）欠肾，放入之后就去判斷當(dāng)前的size是否達(dá)到了threshold極限值，若達(dá)到了蝴罪，將會(huì)進(jìn)行擴(kuò)容董济。
*/
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 e = table[bucketIndex];//將該位置舊的鏈表取出
? ? ? ? //將要添加的k,v構(gòu)成entry,作為鏈表中頭節(jié)點(diǎn)，再將整個(gè)新的鏈表放到該位置
? ? ? ? table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
/**
* Removes the mapping for the specified key from this map if present.
*/
public V remove(Object key) {
Entry e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry prev = table[i];
Entry e = prev;
while (e != null) {//循環(huán)
? ? ? ? ? ? ? Entry 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;
}
/**
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
public void clear() {
modCount++;
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
tab[i] = null;
size = 0;
}
//要重載元素的equals()
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
static class Entry implements Map.Entry {
final K key;
V value;
Entry next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
private abstract class HashIterator implements Iterator {
Entry next;? ? ? ? // next entry to return
int expectedModCount;? // For fast-fail
int index;? ? ? ? ? ? ? // current slot
Entry current;? ? // current entry
//KeySet和 Values都是內(nèi)部類
? ? ? public Set keySet() {
Set ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
private final class KeySet extends AbstractSet {
public Iterator iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
public Collection values() {
Collection vs = values;
return (vs != null ? vs : (values = new Values()));
}
private final class Values extends AbstractCollection {
public Iterator iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
//EntrySet也是內(nèi)部類
? public Set> entrySet() {
return entrySet0();
}
private Set> entrySet0() {
Set> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet> {
public Iterator> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
Entry candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}
