如何在源碼上添加自己的注釋打開jdk下載位置
解壓src文件夾,打開idea,
選擇jdk版本1.7,然后點(diǎn)擊Sourcepath
選擇剛剛解壓的src文件目錄,然后選擇src.zip的文件點(diǎn)擊
打開源碼,輸入時(shí)會(huì)出一個(gè)提示框,直接點(diǎn)擊ok即可,然后就可以輸入自己的注釋了
在開始前先了解一下JDK1.7的HashMap的數(shù)據(jù)結(jié)構(gòu),就算沒有研究過源碼也聽過JDK1.7中HashMap是數(shù)組加鏈表,1.8中是數(shù)組加鏈表加紅黑樹,今天我們主要研究1.7,首先數(shù)組肯定都知道,鏈表這個(gè)一聽以為是很難的東西,其實(shí)一點(diǎn)也不難 什么叫鏈表呢,以java代碼形式 假設(shè)現(xiàn)在有一個(gè)節(jié)點(diǎn),里有具體的值和下一個(gè)節(jié)點(diǎn)的引用 public class Node{
private int number;
private Node next;
}當(dāng)節(jié)點(diǎn)的next引用指向下一個(gè)Node節(jié)點(diǎn),許多的節(jié)點(diǎn)連接起來就叫做鏈表
JDK1.7的數(shù)據(jù)結(jié)構(gòu)就是如下圖所示
在開始前建議自己跟著打開對(duì)應(yīng)的類,方法來自己看一看源碼,不然很容易就不知道在哪里了 HashMap中的全局變量static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final Entry<?, ?>[] EMPTY_TABLE = {};
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;我們來看一下全局變量,簡(jiǎn)單描述一下它們的作用 DEFAULT_INITIAL_CAPACITY 默認(rèn)的初始容量,而大小使用了一個(gè)左移運(yùn)算符,怎么來看它的值呢?java中所有的位運(yùn)算都是在二進(jìn)制的情況下進(jìn)行的 首先1的二進(jìn)制是 0000 0001 而<< 4 符號(hào)的意思是將所有的數(shù)字往左邊移動(dòng)4位,移出來的位置用0替換 也就是 0001 0000 轉(zhuǎn)換為10進(jìn)制就是16,也就是HashMap的默認(rèn)容量 MAXIMUM_CAPACITY 最大容量,也是使用位運(yùn)算符,1<<30 轉(zhuǎn)換為10進(jìn)制就是1073741824 DEFAULT_LOAD_FACTOR 默認(rèn)的負(fù)載因子,默認(rèn)為0.75f,現(xiàn)在可能不太理解,先有個(gè)印象即可 Entry[] EMPTY_TABLE 初始化的一個(gè)空數(shù)組 Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE 真正存儲(chǔ)數(shù)據(jù)的數(shù)組 size 存儲(chǔ)元素的個(gè)數(shù),map.size()方法就是直接返回這個(gè)變量 public int size() {
return size;
}threshold 臨界值,當(dāng)容量到達(dá)這個(gè)容量是進(jìn)行判斷是否擴(kuò)容,而這個(gè)臨界值計(jì)算公式就是,容量大小乘以負(fù)載因子,如果初始化沒有設(shè)置map的大小和負(fù)載因子的話,默認(rèn)就是16*0.75=12 loadFactor 如果創(chuàng)建HashMap時(shí)設(shè)置了負(fù)載因子,那么會(huì)賦值給這個(gè)變量,沒有特殊需求的話一般不需要設(shè)置這個(gè)值,太大導(dǎo)致鏈表過長,影響get方法效率,太小會(huì)導(dǎo)致經(jīng)常進(jìn)行擴(kuò)容浪費(fèi)性能 modCount HashMap的結(jié)構(gòu)被修改的次數(shù)，用于迭代器 構(gòu)造方法首先來看無參構(gòu)造 public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}調(diào)用了重載的構(gòu)造,傳入的就是默認(rèn)大小(16)和默認(rèn)的負(fù)載因子大小(0.75f) 那么我們來看有參構(gòu)造 public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量是否大于最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
//如果大于最大容量,則將容量設(shè)置為最大容量
initialCapacity = MAXIMUM_CAPACITY;
//如果負(fù)載系數(shù)小于0或者不是一個(gè)數(shù)字拋出異常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 設(shè)置負(fù)載因子,，臨界值此時(shí)為容量大小，后面第一次put時(shí)由inflateTable(int toSize)方法計(jì)算設(shè)置
this.loadFactor = loadFactor;
threshold = initialCapacity;
//空方法,由其他實(shí)現(xiàn)類實(shí)現(xiàn)
init();
}put方法擴(kuò)容就是在put方法中實(shí)現(xiàn)的,來看代碼 public V put(K key, V value) {
// 如果table引用指向成員變量EMPTY_TABLE,，那么初始化HashMap（設(shè)置容量,、臨界值，新的Entry數(shù)組引用）
// 因?yàn)樵谶@個(gè)對(duì)象初始化時(shí),就是將EMPTY_TABLE這個(gè)空數(shù)組賦值給table,如果相等說明還沒有進(jìn)行過初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// HashMap 支持key為null
if (key == null)
//key為null單獨(dú)調(diào)用存儲(chǔ)空key的方法
return putForNullKey(value);
//計(jì)算key的hash值
int hash = hash(key);
// 根據(jù)hash值和表當(dāng)前的長度,，得到一個(gè)在數(shù)組中的下標(biāo),重點(diǎn)關(guān)注一下indexFor方法的實(shí)現(xiàn),。
// 該算法主要返回一個(gè)索引，0 到 table.length-1的數(shù)組下標(biāo),。
int i = indexFor(hash, table.length);
//接下來,，找到 table[i]處，以及該處的數(shù)據(jù)鏈表,，看是否存在相同的key;判斷key相同,，
// 首先判斷hash值是否相等，然后再 判斷key的equals方法是否相等
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//首先判斷hash,如果對(duì)象的hashCode方法沒有被重寫,那么hash值相等兩個(gè)對(duì)象一定相等
//并且判斷如果key相等或者key的值相等那么覆蓋并返回舊的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//進(jìn)行添加操作
addEntry(hash, key, value, i);
return null;
}我們來一步一步看,首先來看第一個(gè)判斷 // 如果table引用指向成員變量EMPTY_TABLE,，那么初始化HashMap（設(shè)置容量,、臨界值，新的Entry數(shù)組引用）
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}如果這個(gè)判斷成立,也就是說這個(gè)數(shù)組還沒有進(jìn)行過初始化,則調(diào)用 private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 首先計(jì)算容量, toSize 容量為 threshold,在構(gòu)造方法中,，threshold默認(rèn)等于初始容量,，也就是16
int capacity = roundUpToPowerOf2(toSize);
// 然后重新計(jì)算 threshold的值，默認(rèn)為 capacity * loadFactor
//Math.min 方法用于返回兩個(gè)參數(shù)中的最小值
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化數(shù)組 容量為 capacity
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}roundUpToPowerOf2方法,簡(jiǎn)單來看一下這個(gè)方法的作用 private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
//判斷參數(shù)的值是否大于最大容量
return number >= MAXIMUM_CAPACITY
//如果大于將返回最大容量
? MAXIMUM_CAPACITY
/**
* 如果小于1返回1
* highestOneBit方法可以簡(jiǎn)單理解為返回小于等于輸入的數(shù)字最近的2的次方數(shù)
* 例如
* 2的1次方 2
* 2的2次方 4
* 2的3次方 8
* 2的4次方 16
* 2的5次方 32
* 小于15,并且距離15最近的2的次方數(shù) : 8
* 小于16,并且距離16最近的2的次方數(shù) : 16
* 小于17,并且距離17最近的2的次方數(shù) : 16
*/
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}具體方法實(shí)現(xiàn)就不繼續(xù)研究了,不是這篇的主題,繼續(xù)來看 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 這一步操作是重新計(jì)算threshold的值,也就是臨界值,通過計(jì)算出的容量大小乘以負(fù)載因子大小來算出臨界值的大小 Math.min方法是判斷兩個(gè)值大小,返回小的那個(gè),如果參數(shù)具有相同的值,，則結(jié)果為相同的值,。如果任一值為NaN，則結(jié)果為NaN 之后將初始化一個(gè)Entry類型的數(shù)組賦值給table //初始化數(shù)組 容量為 capacity table = new Entry[capacity]; 那么我們現(xiàn)在來看一下這個(gè)Entry類 static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
int hash;
}那么和開頭舉的例子Node基本一樣的思路,在類中單獨(dú)定義一個(gè)用來存儲(chǔ)下一個(gè)節(jié)點(diǎn)的變量 回到put方法,來看下一個(gè)判斷 // HashMap 支持key為null if (key == null) //key為null單獨(dú)調(diào)用存儲(chǔ)空key的方法 return putForNullKey(value); 我們來看一下這個(gè)putForNullKey方法 private V putForNullKey(V value) {
//獲取下標(biāo)為0的Entry節(jié)點(diǎn)
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中,key為null的entry會(huì)存儲(chǔ)在下標(biāo)0的位置,上面進(jìn)行覆蓋操作,來看addEntry方法 void addEntry(int hash, K key, V value, int bucketIndex) {
/* JDK1.7的擴(kuò)容條件,；size大于等于threshold,并且新添加元素所在的索引值不等為空
也就是即使當(dāng)size達(dá)到或超過threshold,新增加元素,只要不會(huì)引起hash沖突則不擴(kuò)容;
JDK1.8去掉了為null的判斷
*/
if ((size >= threshold) && (null != table[bucketIndex])) {
//將大小擴(kuò)容到原來的兩倍
resize(2 * table.length);
//如果key為null,將放到index為0的位置,否則進(jìn)行取hash的操作
hash = (null != key) ? hash(key) : 0;
//根據(jù)獲取的hash值進(jìn)行獲取下標(biāo)
bucketIndex = indexFor(hash, table.length);
}
//創(chuàng)建entry
createEntry(hash, key, value, bucketIndex);
}來看擴(kuò)容resize()方法,傳入的是2倍的舊數(shù)組的長度 void resize(int newCapacity) {
//將舊table賦值給oldTable
Entry[] oldTable = table;
//獲取舊table長度
int oldCapacity = oldTable.length;
//如果長度已經(jīng)等于最大限制設(shè)置為Integer的最大值
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//創(chuàng)建新table,長度為參數(shù)為傳入的參數(shù)newCapacity
Entry[] newTable = new Entry[newCapacity];
//該方法將oldTable的數(shù)據(jù)復(fù)制到了newTable
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//將新擴(kuò)容的table改為當(dāng)前hashmap的存儲(chǔ)table
table = newTable;
//重新計(jì)算閾值
threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}在擴(kuò)容方法中主要關(guān)注將數(shù)據(jù)轉(zhuǎn)移的transfer方法 void transfer(Entry[] newTable, boolean rehash) {
//獲取新創(chuàng)建的table長度
int newCapacity = newTable.length;
//遍歷舊table
for (Entry<K, V> e : table) {
/*代碼第一次判斷如果當(dāng)前下標(biāo)entry是否為空,
如果為空則切換到下一個(gè)Entry節(jié)點(diǎn)
如果不為空,第二次就是判斷當(dāng)前下標(biāo)的entry是否形成鏈表
如果形成鏈表將一直判斷是否有下一個(gè)節(jié)點(diǎn),當(dāng)把該下標(biāo)鏈表遍歷完畢后,
然后切換到下一個(gè)entry節(jié)點(diǎn)進(jìn)行相同的操作
* */
while (null != e) {
//獲取下一個(gè)entry
Entry<K, V> next = e.next;
if (rehash) {
/**
* 判斷e.key是否為null,如果為null將e.hash賦值為0
* 否則調(diào)用hash()方法進(jìn)行計(jì)算hash
*/
e.hash = null == e.key ? 0 : hash(e.key);
}
//通過當(dāng)前遍歷舊表的entry的hash值和新table的長度來獲取在新表的下標(biāo)位置
int i = indexFor(e.hash, newCapacity);
/*
* jdk1.7是進(jìn)行頭插法,也就是不需要知道當(dāng)前下標(biāo)位置是否存在Entry
* 只需要將舊表中Entry節(jié)點(diǎn),通過計(jì)算出下標(biāo)位置
* 在新添加的Entry中直接將當(dāng)前下標(biāo)元素賦值給next屬性,然后新添加的節(jié)點(diǎn)賦值給當(dāng)前下標(biāo)
*/
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}其中有幾個(gè)需要關(guān)注的方法 //hash()======這個(gè)方法簡(jiǎn)單理解為來通過key來計(jì)算hash,在get時(shí)通過hash可以確保是同一個(gè)entry對(duì)象
final int hash(Object k) {
int h = hashSeed;
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);
}
//indexFor()===========
/**
這里使用&于運(yùn)算符,兩個(gè)相同為1返回1,否則返回0,例如
0010 1101
1010 1011
結(jié)果 0010 1001
*/
static int indexFor(int h, int length) {
return h & (length - 1);
}我們現(xiàn)在回到resize擴(kuò)容方法,這個(gè)方法中最主要的就是這個(gè)將舊數(shù)組中數(shù)據(jù)復(fù)制到新數(shù)組中這個(gè)transfer()方法了,其他的操作上面都有注釋,對(duì)應(yīng)著看應(yīng)該可以看懂 這里再主要說一下indexFor方法,在初始化HashMap時(shí)為什么在設(shè)置初始大小的時(shí)候必須為2的倍數(shù) 下面以HashMap初始化大小為16為例 首先&運(yùn)算符兩都為1才為1,否則為0 假設(shè)hash值為....1010 1010 而現(xiàn)在hashmap的長度為16,即(16-1)=15 hash:1010 1010 因?yàn)?5的低四位為1,也就是說通過&位運(yùn)算符能對(duì)結(jié)果造成影響的只有低四位的四個(gè)1,其他高為都為0 這也是hash()方法的用處盡量讓其他位參與hash運(yùn)算,達(dá)到更加分散的hash值 假設(shè)初始大小為單數(shù),例如15,那么通過 0000 1110 那么和計(jì)算出的hash進(jìn)行&運(yùn)算能對(duì)結(jié)果進(jìn)行影響的位數(shù)會(huì)減少1位,這還是好的情況,如果傳入的初始大小為17那么會(huì)怎樣? 17通過length-1的操作為16,16的二進(jìn)制為0001 0000,那么再和hash值進(jìn)行&的操作 JAVA開發(fā)者也想到這個(gè)問題,所以在上面的roundUpToPowerOf2()方法中進(jìn)行了一些操作,防止容量不是2的次方數(shù) 那我們回到addEntry()方法中 void addEntry(int hash, K key, V value, int bucketIndex) {
/* JDK1.7以后的擴(kuò)容條件,；size大于等于threshold,并且新添加元素所在的索引值不等為空
也就是當(dāng)size達(dá)到或超過threshold,新增加元素,只要不會(huì)引起hash沖突則不擴(kuò)容;
JDK1.8去掉了為null的判斷
*/
if ((size >= threshold) && (null != table[bucketIndex])) {
//將大小擴(kuò)容到原來的兩倍
resize(2 * table.length);
//如果key為null,將放到index為0的位置,否則進(jìn)行取hash的操作
hash = (null != key) ? hash(key) : 0;
//根據(jù)獲取的hash值進(jìn)行獲取下標(biāo)
bucketIndex = indexFor(hash, table.length);
}
//創(chuàng)建entry
createEntry(hash, key, value, bucketIndex);
}resize()方法下面取hash操作的hash()方法和獲取下標(biāo)的indexFor方法都已經(jīng)在上面寫過,這里就不再贅述 接下來主要來看createEntry方法 void createEntry(int hash, K key, V value, int bucketIndex) {
//先獲取當(dāng)前下標(biāo)entry節(jié)點(diǎn),也可能為null
Entry<K, V> e = table[bucketIndex];
//如果有entry節(jié)點(diǎn),那么在添加新的entry時(shí)將會(huì)形成鏈表
table[bucketIndex] = new Entry<>(hash, key, value, e);
//將hashmap的大小加1
size++;
}因?yàn)閔ash值,所在下標(biāo)位置都已經(jīng)獲取過了,所以方法傳入?yún)?shù)直接使用 到這里put方法中putForNullKey()添加null key的方法就完成了,我們返回put方法繼續(xù) //put方法,省略一些剛剛寫過的方法
int hash = hash(key);
int i = indexFor(hash, table.length);
//接下來，找到 table[i]處,，以及該處的數(shù)據(jù)鏈表,，看是否存在相同的key;判斷key相同，
// 首先判斷hash值是否相等,，然后再 判斷key的equals方法是否相等
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//首先判斷hash,如果對(duì)象的hashCode方法沒有被重寫,那么hash值相等兩個(gè)對(duì)象一定相等
//并且判斷如果key相等或者key的值相等那么覆蓋并返回舊的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//進(jìn)行添加操作
addEntry(hash, key, value, i);
return null;最上面hash()和indexFor()方法上面寫過,不再贅述,中間的判斷覆蓋參考注釋應(yīng)該可以理解,而下面的addEntry方法上面也寫過 get方法如果理解了put方法后,get方法會(huì)相對(duì)簡(jiǎn)單很多 public V get(Object key) {
//判斷如果key等于null的話,直接調(diào)用得到nullkey的方法
if (key == null)
return getForNullKey();
//通過getEntry方法的到entry節(jié)點(diǎn)
Entry<K, V> entry = getEntry(key);
//判斷如果為null返回null,否則返回entry的value
return null == entry ? null : entry.getValue();
}首先來看key為null的情況 private V getForNullKey() {
//如果hashmap的大小為0返回null
if (size == 0) {
return null;
}
/**
開始研究時(shí)有個(gè)問題困擾著我,寫博客時(shí)突然明白了,
問題就是既然已知key為null的entry都會(huì)被放入下標(biāo)0的位置,為什么還要循環(huán),直接獲取0下標(biāo)的entry覆蓋不行嗎
然后我在寫indexFor方法時(shí)想到,不僅僅為null的key下標(biāo)為0,如果一個(gè)hash算法算完后通過indexFor方法
算出的下標(biāo)正好是0呢,它就必須通過循環(huán)來找到那個(gè)key為null的entry
*/
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}邏輯比較簡(jiǎn)單,就不解釋了,我們回到get看下一個(gè)getEntry方法 final Entry<K, V> getEntry(Object key) {
//如果hashmap的大小為0返回null
if (size == 0) {
return null;
}
//判斷key如果為null則返回0,否則將key進(jìn)行hash
int hash = (key == null) ? 0 : hash(key);
//indexFor方法通過hash值和table的長度獲取對(duì)應(yīng)的下標(biāo)
//遍歷該下標(biāo)下的(如果有)鏈表
for (Entry<K, V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//判斷當(dāng)前entry的key的hash如果和傳入的key的hash相同返回當(dāng)前entry節(jié)點(diǎn)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}remove方法public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
//如果e為null返回null,否則返回entry里面的value
return (e == null ? null : e.value);
}來看removeEntryForKey方法 final Entry<K, V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
//取hash算index
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K, V> prev = table[i];
Entry<K, V> e = prev;
//如果當(dāng)前位置不為null
while (e != null) {
Entry<K, V> next = e.next;
Object k;
//判斷如果當(dāng)前entry的hash相同,key相同或key的內(nèi)容相同
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
//判斷如果這個(gè)entry是鏈表的頭結(jié)點(diǎn)
if (prev == e)
//將entry的下一個(gè)結(jié)點(diǎn)作為頭結(jié)點(diǎn)放入數(shù)組
table[i] = next;
else
//如果當(dāng)前結(jié)點(diǎn)不是頭結(jié)點(diǎn),那么就把當(dāng)前entry的下一個(gè)節(jié)點(diǎn)替換當(dāng)前entry的位置
prev.next = next;
//空方法
e.recordRemoval(this);
//返回被刪除的entry節(jié)點(diǎn)
return e;
}
//如果沒有找到對(duì)應(yīng)entry節(jié)點(diǎn),將繼續(xù)尋找當(dāng)前下標(biāo)下面的entry
prev = e;
e = next;
}
//沒有找到對(duì)應(yīng)的entry,返回null
return e;
}總結(jié)一下 HashMap在初始化時(shí)除了一些判斷數(shù)據(jù)正確性以外主要做了兩件事
Put方法
Get方法
存儲(chǔ)流程就是根據(jù)key算出的hash,然后根據(jù)hash計(jì)算出index,而取的時(shí)候key相同的話hash相同,index相同,找到下標(biāo)位置上所有的entry依次判斷key的hash相同,key的引用相同或值相同 |
|
|
