HashMap
HashMap要聊的東西太多了，而且由于HashSet接口中底層實作就是用的HashMap,是以建議先看HashMap的源碼。這裡就直接轉載别人的文章中的總結；畢竟别人總結 的非常到位。先說下結構，對HashMap的結構有個大概的了解後，再說些其工作原理以及其中涉及到的雜湊演算法。
參考：【http://blog.csdn.net/qq_27093465/article/details/52207152】
public class HashMap<K,V>
extends
AbstractMap<K,V>
implements
Map<K,V>,
Cloneable,
Serializable
數組的特點是：尋址容易，插入和删除困難；而連結清單的特點是：尋址困難，插入和删除容易。那麼我們能不能
綜合兩者的特性，做出一種尋址容易，插入删除也容易的資料結構？答案是肯定的，這就是我們要提起的哈希表。
HashMap實作了Map接口，繼承AbstractMap。其中Map接口定義了鍵映射到值的規則，而AbstractMap類提供
Map 接口的骨幹實作，以最大限度地減少實作此接口所需的工作。
一 HashMap結構
上圖 可能很直覺清晰的介紹了HashMap的結構：從上圖我們可以發現哈希表是由數組+連結清單組成的，HashMap其實也是一個線性的數組實作的,是以可以了解為其存儲資料的容器就是一個線性數組。這可能讓我們很不解，一個線性的數組怎麼實作按鍵值對來存取資料呢？
1 .首先HashMap裡面實作一個靜态内部類Entry，其重要的屬性有 key , value, next，從屬性key,value。
我們就能很明顯的看出來Entry就是HashMap鍵值對實作的一個基礎bean，我們上面說到HashMap的基礎就是一個線性數組，
這個數組就是Entry[]，Map裡面的内容都儲存在Entry[]裡面。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;//鍵
V value;//值
Entry<K,V> next;//下個元素指針
int hash;//key的hash值
}
2 兩個概念：
1）.這裡面有個Hash沖突的概念：就像上面的一個數組的位置上出現了一條鍊，即一個連結清單的出現，這就是所謂的
hash沖突，解決hash沖突，就是讓連結清單的長度變短，或者幹脆就是不産生連結清單，一個好的hash算法應該是讓資料很好的
散列到數組的各個位置，即一個位置存一個資料就是最好的散列，下面說的鍊位址法，說的就是在hashmap裡面沖突的時候，
一個節點可以存多個資料。
2).還有個桶：bucket，就是上面的數組的每一個成員，數組的每個位置就叫一個桶。對應前面的單詞。
二 HashMap基本定義
HashMap也是我們使用非常多的Collection，它是基于哈希表的 Map 接口的實作，以key-value的形式存在。
HashMap可以接受null鍵值和值，而HashTable則不能；HashMap是非synchronized;HashMap很快；HashMap儲存的是鍵值對。
三 構造函數
HashMap提供了三個構造函數：
HashMap()：構造一個具有預設初始容量 (16) 和預設加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)：構造一個帶指定初始容量和預設加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：構造一個帶指定初始容量和加載因子的空 HashMap。
在這裡提到了兩個參數：初始容量，加載因子。這兩個參數是影響HashMap性能的重要參數，其中容量表示哈希表中桶的數量，初始容量是建立哈希表時的容量，加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度，它衡量的是一個散清單的空間的使用程度，負載因子越大表示散清單的裝填程度越高，反之愈小。
對于使用連結清單法的散清單來說，查找一個元素的平均時間是O(1+a)，是以如果負載因子越大，對空間的利用更充分，然而後果是查找效率的降低；如果負載因子太小，那麼散清單的資料将過于稀疏，對空間造成嚴重浪費。系統預設負載因子為0.75，一般情況下我們是無需修改的。
四、工作原理
1 存儲的實作put(K key,V value)
核心就是：根據key的hashcode得到桶的位置，往裡面添加值；若發現有對應的鍵存在就覆寫。
當我們想一個HashMap中添加一對key-value時，系統首先會計算key的hash值，然後根據hash值确認在table中存儲的位置。若該位置沒有元素，則直接插入。否則疊代該處元素連結清單并依此比較其key的hash值。如果兩個hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),則用新的Entry的value覆寫原來節點的value。如果兩個hash值相等但key值不等 ，則将該節點插入該連結清單的鍊頭。
①首先判斷key==null?,若為null，就調用putForNullKey方法。
②若 key != null ，對key調用hashCode()方法，根據hash值确認在table中存儲的位置，即桶的位置，确定資料要插入到那個桶中。(bucket位置來儲存Entry對象)。
若桶中有元素，(hash值相同時說明在同個桶中，這時再比較有沒有相同 的key(調用equals()))，
則周遊桶中元素，看看是否有相同的key，
若存在則覆寫原來key的value，否則将該元素儲存在鍊頭（最先儲存的元素放在鍊尾）。
若table在該處沒有元素，則直接儲存。
注意：
a 疊代處：此處疊代原因就是為了防止存在相同的key值，若發現兩個hash值（key）相同時，HashMap的處理方式是用新value替換舊value，
這裡并沒有處理key，這就解釋了HashMap中沒有兩個相同的key;
b 再看如何計算key的hash值，HashMap的精華所在。
//計算鍵key的hash值(String類的key做了優化)
final int hash(Object k) {
int h = hashSeed;
//這裡針對String類的key值做了優化，調用不同的函數(???)
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
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);
}
計算hash值後，怎麼才能保證table元素分布均與呢？我們會想到取模，但是由于取模的消耗較大，
HashMap是這樣處理的：調用indexFor方法。HashMap的底層數組長度總是2的n次方，在構造函數中存在：capacity <<= 1;這樣做總是能夠保證HashMap的底層數組長度為2的n次方。
當length為2的n次方時，h&(length - 1)就相當于對length取模，而且速度比直接取模快得多，這是HashMap在速度上的一個優化。
我們回到indexFor方法，該方法僅有一條語句：h&(length - 1)，這句話除了上面的取模運算外還有一個非常重要的責任：
均勻分布table資料和充分利用空間。
//??? 根據Hash值和Hash表的大小選擇合适的桶???
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}<span style="font-family: verdana, Arial, Helvetica, sans-serif; line-height: 25.2px; background-color: rgb(249, 249, 249);"> </span>
c “當兩個對象的hashcode相同會發生什麼？”
當hashcode相同時，它們的bucket位置相同，‘碰撞’會發生。
因為HashMap使用LinkedList存儲對象，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在LinkedList中。是以即使bucket位置相同，插入到同個bucket位置的結點以連結清單形式所連接配接。即：
打個比方， 第一個鍵值對A進來，通過計算其key的hash得到的index=0，記做:Entry[0] = A。一會後又進來一個鍵值對B，通過計算其index也等于0，現在怎麼辦？HashMap會這樣做:
B.next = A,Entry[0] = B,如果又進來C,index也等于0,那麼C.next = B,Entry[0] = C；(即将先加入的結點next指針指向新加入的結點)
這樣我們發現index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性連結在一起。是以疑問不用擔心。也就是說數組中存儲的是最後插入的元素。
下面是put的源碼;
//将指定value值存放在指定key處；若key處以前有值，就将其覆寫;
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);//是空表的話，就直接初始化底層結構
}
//key為null的時候，就放入null鍵（這裡可以看出hashmap集合中可以有null鍵）
if (key == null)
return putForNullKey(value);
//計算鍵的哈希值
int hash = hash(key);
//擷取桶的位置
int i = indexFor(hash, table.length);
//因為表中儲存的是桶中結點的頭指針；是以找到對應的桶以後就可以從頭指針開始進行周遊
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//先判斷該條鍊上有沒有hash相同的(hash相同後再比較key值)
//有相同的key,就直接覆寫其值
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);//将新加入的鍵值添加到指定位置i處，i為桶的位置;儲存在鍊頭部分
return null;
}<strong>
</strong>
2 讀取的實作：get(key)
核心：通過key的hash值找到在table數組中的索引處的Entry，然後傳回該key對應的value即可。
//根據鍵key值獲得對應的值
//若key==null，調用getForNullKey函數，傳回null鍵對應的值value
//若key！=null,先根據key得到對應的entry結點，再得到對應的值
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//根據指定的key找到對應的entry結點
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;//如果集合為空，就直接傳回null
}
//計算key的哈希值；
//key==null>>>0;
//key!= null >> hash(key),調用hash方法計算key值
int hash = (key == null) ? 0 : hash(key);
//先根據哈希值找到桶的位置,再周遊桶中的rntry結點
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//先比價哈希值，哈希值相同再調用equals
//這裡就是map中為什麼重寫equals方法時一定要重寫hashCode()方法；
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
在這裡能夠根據key快速的取到value除了和HashMap的資料結構密不可分外，還和Entry有莫大的關系，
在前面就提到過，HashMap在存儲過程中并沒有将key，value分開來存儲，而是當做一個整體key-value來處理的，這個整體就是Entry對象。
同時value也隻相當于key的附屬而已。在存儲的過程中，系統根據key的hashcode來決定Entry在table數組中的存儲位置，
在取的過程中同樣根據key的hashcode取出相對應的Entry對象。
注： “如果兩個鍵的hashcode相同，你如何擷取值對象？”
正常情況下擷取結點值是根據key的hashcode找到對應的entry結點，然後再傳回entry對應的結點。
若兩個鍵的hashcode相同時，找到bucket位置之後（兩個鍵的hashcode相同說明在同一個桶中），
會調用keys.equals()方法去找到LinkedList中正确的節點，最終找到要找的值對象。
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
3 再哈希操作：預設的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，
将會建立原來HashMap大小的兩倍的bucket數組，來重新調整map的大小，并将原來的對象放入新的bucket數組中。
這個過程叫作rehashing，因為它調用hash方法找到新的bucket位置。
現在我們需要看一下當資料量已經超過初始定義的負載因子時，HashMap如何處理？ 随着HashMap中元素的數量越來越多，發生碰撞的機率就越來越大，所産生的連結清單長度就會越來越長，這樣勢必 會影響HashMap的速度(為啥呢，原來是直接找到數組的index就可以直接根據key取到值了，但是沖突嚴重， 也就是說連結清單長，那就得循環連結清單了，時間就浪費在循環連結清單上了，也就慢了)， 為了保證HashMap的效率，系統必須要在某個臨界點進行擴容處理。該臨界點在當HashMap中元素的數量等于table數組長度*加載因子。但是擴容是一個非常耗時的過程，因為它需要重新計算這些資料在新table數組中的位置并進行複制處理。是以如果我們已經預知HashMap中元素的個數，那麼預設元素的個數能夠有效的提高HashMap的性能。
在HashMap中當資料量很多時，并且已經達到了負載限度時，會重新做一次哈希，也就是說會再散列。調用的方法為resize()，并且java預設傳入的參數為2*table.length。
//當集合到大門檻值threshold時，就對集合進行擴容
//在HashMap中當資料量很多時，并且已經達到了負載限度時，會重新做一次哈希，也就是說會再散列。
//調用的方法為resize()，并且java預設傳入的參數為2*table.length
//resize:再哈希是重建立一個指定容量的數組，然後将每個元素重新計算它要放的位置
void resize(int newCapacity) {
Entry[] oldTable = table;//老的表(集合)
int oldCapacity = oldTable.length;//擷取老的hashmap集合容量
if (oldCapacity == MAXIMUM_CAPACITY) {//若老的hashmap集合容量為最大值，就将門檻值設定為最大值并傳回
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];//建一個新的表結構
//将老的表中資料拷貝的新表中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;//修改表的底層結構
//修改門檻值：newCapacity * loadFactor(不能超過最大值)
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//将舊表中的entry結點拷貝到新表中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;//擷取新表容量
for (Entry<K,V> e : table) {//周遊表中結點
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {//如果需要重新計算hash值。就重新計算
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//擷取桶的位置
// ？？？元素連接配接到桶中，相當于單連結清單的插入
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
4.解決hash沖突的辦法
- 開放定址法（線性探測再散列，二次探測再散列，僞随機探測再散列）
- 再哈希法
- 鍊位址法
- 建立一個公共溢出區
Java中hashmap的解決辦法就是采用的鍊位址法。
5 重新調整HashMap大小存在什麼問題
當重新調整HashMap大小的時候，确實存在條件競争，因為如果兩個線程都發現HashMap需要重新調整大小了，它們會同時試着調整大小。
在調整大小的過程中，存儲在LinkedList中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會将元素放在LinkedList的尾部，
而是放在頭部，這是為了避免尾部周遊(tail traversing)。如果條件競争發生了，那麼就死循環了。
6 面試題
1為什麼String, Interger這樣的wrapper類适合作為鍵？
String, Interger這樣的wrapper類作為HashMap的鍵是再适合不過了，而且String最為常用。因為String是不可變的，也是final的，
而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。
不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和擷取時傳回不同的hashcode的話，
那麼就不能從HashMap中找到你想要的對象。
不可變性還有其他的優點如線程安全。如果你可以僅僅通過将某個field聲明成final就能保證hashCode是不變的，那麼請這麼做吧。
因為擷取對象的時候要用到equals()和hashCode()方法，那麼鍵對象正确的重寫這兩個方法是非常重要的。
如果兩個不相等的對象傳回不同的hashcode的話，那麼碰撞的幾率就會小些，這樣就能提高HashMap的性能。
2我們可以使用自定義的對象作為鍵嗎？
這是前一個問題的延伸。當然你可能使用任何對象作為鍵，隻要它遵守了equals()和hashCode()方法的定義規則，并且當對象插入到Map中
之後将不會再改變了。如果這個自定義對象時不可變的，那麼它已經滿足了作為鍵的條件，因為當它建立之後就已經不能改變了。
3我們可以使用CocurrentHashMap來代替HashTable嗎？
這是另外一個很熱門的面試題，因為ConcurrentHashMap越來越多人用了。我們知道HashTable是synchronized的，
但是ConcurrentHashMap同步性能更好，因為它僅僅根據同步級别對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，
但是HashTable提供更強的線程安全性。
整個HashMap的源碼：
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
//初始化容量;2^4=16;必須為2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量：2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//初始化加載因子：0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//HashMap内部的存儲結構是一個數組，在未初始化前數組為空
static final Entry<?,?>[] EMPTY_TABLE = {};
//建一個空的entry數組：即桶，添加entry結點（鍵值映射對）
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//集合中鍵值映射對的數量；永久化防止被序列化
transient int size;
//HashMap下次擴容的門檻值:即超過這個值就擴容
int threshold;
//加載因子
//final:一次指派就不再修改
final float loadFactor;
//Map集合中結構改變的次數
transient int modCount;
//預設的threshold值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//???不太懂這個
//通過虛拟機配置來修改threshold值
private static class Holder {
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));//讀取門檻值
int threshold;
try {
threshold = (null != altThreshold)//修改threshold值
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// disable alternative hashing if -1
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
//計算Hash值時的key
transient int hashSeed = 0;
//構造一個帶有指定初試容量和加載因子的HashMap
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);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
//構造一個有初始化大小的HashMap，此時加載因子預設為0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//構造一個空的HashMap,初試容量為預設的16，加載因子為0.75
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//建構一個指定映射關系與Map集合相同的新的HashMap
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中的元素
}
//選擇合适的容量值，取最接近number的2的幂
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
//初始化HashMap的底層資料結構
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);//選合适的容量:比toSize大的2的整數幂次方
//選取合适的threshold(擴容門檻值)
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];//初始化底層資料結構
initHashSeedAsNeeded(capacity);//選擇合适的Hash因子
}
//初始化
void init() {
}
//????選擇合适的Hash因子，這裡和虛拟機的配置有關
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
//計算鍵key的hash值(String類的key做了優化)
final int hash(Object k) {
int h = hashSeed;
//這裡針對String類的key值做了優化，調用不同的函數(???)
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//均勻分布table資料和充分利用空間。
//這個方法在HashMap中非常重要，凡是與查詢、添加、删除有關的方法中都有調用該方法，為什麼這麼短的一個代碼使用率這麼高？
//根據代碼注釋我們知道，
//這個方法是根據hashCode及目前table的長度（數組的長度，不是map的size）得到該元素應該存放的位置，或者在table中的索引。
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
//傳回集合的大小
public int size() {
return size;
}
//判斷集合是否非空
public boolean isEmpty() {
return size == 0;
}
//根據鍵key值獲得對應的值:先根據key得到結點entry，再擷取其對應的值
//若key==null，調用getForNullKey函數，傳回null鍵對應的值value
//*若key！=null,先根據key得到對應的entry結點，再得到對應的值
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//key==null時，分三種情況讨論
private V getForNullKey() {
if (size == 0) {//1 集合為空，value為null
return null;
}
//2 key==null,value!=null
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
//3 key==null,value==null
return null;
}
//判斷是否包含鍵key;實際上是調用getEntry，看key對應的entry結點是否存在
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
//根據指定的key找到對應的entry結點
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;//如果集合為空，就直接傳回null
}
//計算key的哈希值；
//key==null == 0;
//key!= null >> hash(key),調用hash方法計算key值
int hash = (key == null) ? 0 : hash(key);
//先根據哈希值找到桶的位置,再周遊桶中的rntry結點
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//因為在同個桶中，這裡的哈希值肯定相同：e.hash == hash
//再周遊桶中的結點；尋找結點中的key與要找到key相同的結點：
//調用equals方法(k = e.key) == key || (key != null && key.equals(k))
//這裡解釋了：當hashcode相同時(在同個桶中)，需要調用equals進一步進行比較，是以hashcode、equals都需要重寫
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
//将指定value值存放在指定key處；若key處以前有值，就将其覆寫;
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);//是空表的話，就直接初始化底層結構
}
//key為null的時候，就放入0号桶中中（這裡可以看出hashmap集合中可以有null鍵）
if (key == null)
return putForNullKey(value);
//計算鍵的哈希值
int hash = hash(key);
//擷取桶的位置
int i = indexFor(hash, table.length);
//因為表中儲存的是桶中結點的頭指針；是以找到對應的桶以後就可以從頭指針開始進行周遊
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//首先確定周遊結點的哈希值與要插入的鍵的哈希值相同：e.hash == hash
//有相同的key,就直接覆寫其值
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);//将新加入的鍵值添加到指定位置i處，i為桶的位置;儲存在鍊頭部分
return null;
}
//用來添加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;
}
/**
* This method is used instead of put by constructors and
* pseudoconstructors (clone, readObject). It does not resize the table,
* check for comodification, etc. It calls createEntry rather than
* addEntry.
*/
//添加元素???
private void putForCreate(K key, V value) {
int hash = null == key ? 0 : hash(key);//計算key的hash值
int i = indexFor(hash, table.length);//定位Hash桶
//周遊第i号hash桶
//table[i]中儲存的是第i号hash桶的頭指針，是以要周遊第i号hash桶的頭指針，即為e = e.next
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//先比價哈希值，哈希值相同再調用equals
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
//建立元素實體，這裡即添加到第i号Hash桶中
createEntry(hash, key, value, i);
}
//将m中元素全加到hashMap中
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
//當集合到大門檻值threshold時，就對集合進行擴容
//在HashMap中當資料量很多時，并且已經達到了負載限度時，會重新做一次哈希，也就是說會再散列。
//調用的方法為resize()，并且java預設傳入的參數為2*table.length
//resize:再哈希是重建立一個指定容量的數組，然後将每個元素重新計算它要放的位置
void resize(int newCapacity) {
Entry[] oldTable = table;//老的表(集合)
int oldCapacity = oldTable.length;//擷取老的hashmap集合容量
if (oldCapacity == MAXIMUM_CAPACITY) {//若老的hashmap集合容量為最大值，就将門檻值設定為最大值并傳回
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];//建一個新的表結構
//将老的表中資料拷貝的新表中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;//修改表的底層結構
//修改門檻值：newCapacity * loadFactor(不能超過最大值)
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//将舊表中的entry結點拷貝到新表中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;//擷取新表容量
for (Entry<K,V> e : table) {//周遊表中每個位置的頭指針
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {//如果需要重新計算hash值。就重新計算
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//擷取桶的位置
// ？？？元素連接配接到桶中，相當于單連結清單的插入
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
//添加指定集合中的元素
public void putAll(Map<? extends K, ? extends V> m) {
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)//集合為空，直接傳回
return;
if (table == EMPTY_TABLE) {//底層數組為空，執行初始化？？？？
inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
}
//若要添加的集合大小超過門檻值，就執行擴容
//擴容大小：
if (numKeysToBeAdded > threshold) {
//選擇容量
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;//超過最大值就設定為最大值
int newCapacity = table.length;//目前容量
while (newCapacity < targetCapacity)//目前容量小于目标容量，就擴容
newCapacity <<= 1;//每次擴容大小 為2的幂次方
if (newCapacity > table.length)
resize(newCapacity);//？？？？執行擴容
}
//開始添加元素
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
//移除集合中指定鍵，傳回key對應的值
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
//删除元素，傳回鍵對應的值
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;//集合為空，就傳回null
}
//計算Key的hash值
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);//擷取桶的位置
Entry<K,V> prev = table[i];//擷取頭指針，設為prev結點
Entry<K,V> e = prev;//儲存頭指針
//從頭指針開始周遊
while (e != null) {
Entry<K,V> next = e.next;//擷取下個結點
Object k;
//周遊桶中結點
//若桶中有指定結點的鍵key，就将其删除
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;
}
//删除一個Entry實體，通過o的key查找到元素後，删除(和上面方法類似)
final Entry<K,V> removeMapping(Object o) {
if (size == 0 || !(o instanceof Map.Entry))
return null;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
Object key = entry.getKey();
int hash = (key == null) ? 0 : hash(key);
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;
if (e.hash == hash && e.equals(entry)) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
//清空集合
public void clear() {
modCount++;
Arrays.fill(table, null);//底層數組設定為null
size = 0;
}
//判斷是否包含值為value的元素
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
//先擷取表中每個索引i所在位置，即每個桶
for (int i = 0; i < tab.length ; i++)
//再擷取第i個桶的頭指針：Entry e = tab[i]
//再周遊桶中的每個結點。判斷結點值是否與指定值相等
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
//判斷是否包含null
private boolean containsNullValue() {
Entry[] tab = table;
//周遊方法同上
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}
//淺複制HashMap
public Object clone() {
HashMap<K,V> result = null;
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
if (result.table != EMPTY_TABLE) {
result.inflateTable(Math.min(
(int) Math.min(
size * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY),
table.length));
}
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this);
return result;
}
//Entry結點，實作Map,Entry接口，是HashMap内部key和value的一個抽象
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;//鍵
V value;//值
Entry<K,V> next;//下個元素指針
int hash;//key的hash值
//建立一個Entry結點
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
//擷取key
public final K getKey() {
return key;
}
//擷取值
public final V getValue() {
return 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();//調用者的key
Object k2 = e.getKey();//比較對象的key
//比較key
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;
}
//傳回hashCode值：？？？怎麼傳回的？
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
//當集合中有鍵對應的值被覆寫時就執行這個空方法
//???這個方法是幹嘛用的
void recordAccess(HashMap<K,V> m) {
}
//當Entry結點被移除的時候就執行這個方法
void recordRemoval(HashMap<K,V> m) {
}
}
//将指定鍵值加入到指定桶中,bucketIndex：桶的位置
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);
}
//建立entry：是在連結清單頭加入新加的結點
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];//先擷取該桶的頭指針：table[bucketIndex]
table[bucketIndex] = new Entry<>(hash, key, value, e);//建立結點：hash, key, value, e
//頭指針指向此結點
size++;
}
//疊代器
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // 下一個傳回的實體
int expectedModCount; // 疊代器修改的次數
int index; // Hash桶的索引号
Entry<K,V> current; // 目前實體
HashIterator() {
expectedModCount = modCount;//擷取修改次數
if (size > 0) { // 集合不為空s
Entry[] t = table;
//尋找第一個不為空的桶
while (index < t.length && (next = t[index++]) == null);
}
}
//判斷是否有下一個元素
public final boolean hasNext() {
return next != null;
}
//傳回下一個元素
final Entry<K,V> nextEntry() {
//疊代期間，修改次數不同即又被修改，則抛出異常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;//從ｎｅｘｔ開始周遊
if (e == null)
throw new NoSuchElementException();
//如果下個結點為空，則找到下個不為空的桶???
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
//删除元素
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);//調用父類删除元素
expectedModCount = modCount;//修改并發修改次數
}
}
//HashMap值集疊代器，傳回的是nextEntry疊代器值
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
//HashMap鍵集疊代器，傳回的是nextEntry疊代器中鍵
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
// Subclass overrides these to alter behavior of views' iterator() method
//傳回鍵集疊代器
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
//傳回值集疊代器
Iterator<V> newValueIterator() {
return new ValueIterator();
}
//傳回Entry疊代器
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
// Views
//視圖集合，HashMap内部Entry集合
private transient Set<Map.Entry<K,V>> entrySet = null;
//傳回鍵集
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
//鍵集合的實作，實作了AbstractSet抽象類，調用了父類的方法
private final class KeySet extends AbstractSet<K> {
public Iterator<K> 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<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
//值集合的實作，實作了AbstractCollection抽象類，調用了父類的方法來實作
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
//entry集合
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
//傳回entry集合
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> 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();
}
}
//序列化
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
if (table==EMPTY_TABLE) {
s.writeInt(roundUpToPowerOf2(threshold));
} else {
s.writeInt(table.length);
}
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
if (size > 0) {
for(Map.Entry<K,V> e : entrySet0()) {
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private static final long serialVersionUID = 362498820763181265L;
//反序列化
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
}
// set other fields that need values
table = (Entry<K,V>[]) EMPTY_TABLE;
// Read in number of buckets
s.readInt(); // ignored.
// Read number of mappings
int mappings = s.readInt();
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
// capacity chosen by number of mappings and desired load (if >= 0.25)
int capacity = (int) Math.min(
mappings * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY);
// allocate the bucket array;
if (mappings > 0) {
inflateTable(capacity);
} else {
threshold = capacity;
}
init(); // Give subclass a chance to do its thing.
// Read the keys and values, and put the mappings in the HashMap
for (int i = 0; i < mappings; i++) {
K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}
// These methods are used when serializing HashSets
int capacity() { return table.length; }
float loadFactor() { return loadFactor; }
}
![JDK1.8源碼閱讀記錄lang包object類JDK1.8源碼閱讀記錄[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)