HashSet與HashMap的關(guān)系用一句話概括為：披著羊皮的狼。其內(nèi)部實現(xiàn)實際上是用了HashMap的實例，將具體實現(xiàn)委托給HashMap進(jìn)行完成的。本文主要講解部分HashMap的相關(guān)方法。
HashMap采用了拉鏈法解決hash沖突問題，一部分為數(shù)組，可以通過hash后的值找到該數(shù)組處的鏈表。另一部分是鏈表，通過map實體組成的鏈表前后相連組成鏈表。 影響其性能的兩個主要的參數(shù)主要是初始值和負(fù)載因子，初始值設(shè)置為16，負(fù)載因子默認(rèn)為0.75。
求出該hash在數(shù)組中索引位置。通過該index即可找到該鏈表。
/* * 通過&求其映射的位置 * hash值映射的位置 */ static int indexFor(int h, int length) { return h & (length-1); }前部分需要計算其hash值，然后根據(jù)hash值求出其索引值，根據(jù)索引值找到要進(jìn)行查找的鏈表。進(jìn)而對鏈表進(jìn)行遍歷，看是不是存在該key，存在則覆蓋舊值，不存在則直接插入。
/* * 放入key和value * 如果當(dāng)前有這個鍵值對的話，就直接覆蓋并且返回舊的值 * 如果當(dāng)前沒有這個鍵值對的話，就返回null，將現(xiàn)在的值放進(jìn)去 * * @see java.util.AbstractMap#put(java.lang.Object, java.lang.Object) */ 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; }此方法主要是用于重新分配空間后將數(shù)據(jù)重新進(jìn)行散列。每一個鏈表中的元素都要重新進(jìn)行散列，不過每個元素的hash值不需要重新計算的，因為在插入的時候就已經(jīng)確保了按統(tǒng)一的規(guī)則設(shè)定了。
/* * 重新計算當(dāng)前hash值映射的位置 * 然后與newCapacity相&，由于重新計算了值，分配后的值不一定一樣 * 需要重新組織鏈表結(jié)構(gòu) */ 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; // 插入的時候就已經(jīng)計算出來其hash值了（hash方法），沒必要再次計算了 int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }新聞熱點
疑難解答
圖片精選
