重寫hashmap源碼

❶ java集合：關於hashmap存儲一個對象，中間改變對象的值，為什麼再remove不能用新名字來刪除

這個得看hashset的源碼了，內部會以hashcode或其經過某種演算法得到的二次hash值為key來組織存儲數據。

你重寫了book的hashcode方法，並且內部用到了name來計算hashcode,那麼當你修改了name後，它的hashcode自然變了，那麼它就在原來的hashset里找不到了，自然刪除不掉。

❷ 作為一個面試官，我會問初級java工程師哪些問題

初級java工程師多數是剛畢業或者工作1,2年的新人。對於新人，面試中基礎問題會問道很多，因為先要考察這個人的基礎。

關於基礎類的題目，我在面試初級java工程師的時候一般會問下面兩大類問題，每類5個題目，這樣下來我就基本可以了解這位工程師的程度了。

java基礎類

面向對象基礎類

最後，如果前面問題回答的不錯，會補充兩個編程習慣問題。

1.在你寫過的代碼中，你寫過超過2層的循環嗎，怎麼實現的？

回答：沒有，就算ok；如果回答有，聽一下實現，如果原因說不出來，扣分。

2.在你寫過的代碼中，if語句最多嵌套了幾層，最多有多少分支，怎麼實現的？

回答：3層以下，就算ok；如果回答3層以上，聽一下實現，如果原因說不出來，扣分。

4，5個分支，就算ok；如果回答5個分支以上，聽一下實現，如果原因說不出來，扣分。

最後兩個題其實比較陷阱，但是正是一個反向的思考才能了解面試者之前的工作狀態。

如果面試者在平日里就有好的習慣，自然不用擔心。

❸ HashMap是什麼東西

HashMap，中文名哈希映射，HashMap是一個用於存儲Key-Value鍵值對的集合，每一個鍵值對也叫做Entry。這些個鍵值對（Entry）分散存儲在一個數組當中，這個數組就是HashMap的主幹。HashMap數組每一個元素的初始值都是Null。

HashMap是基於哈希表的 Map 介面的實現。此實現提供所有可選的映射操作，並允許使用 null 值和 null 鍵。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序，特別是它不保證該順序恆久不變。

(3)重寫hashmap源碼擴展閱讀：

因為HashMap的長度是有限的，當插入的Entry越來越多時，再完美的Hash函數也難免會出現index沖突的情況。

HashMap數組的每一個元素不止是一個Entry對象，也是一個鏈表的頭節點。每一個Entry對象通過Next指針指向它的下一個Entry節點。當新來的Entry映射到沖突的數組位置時，只需要插入到對應的鏈表即可。

❹ HashMap源碼分析

HashMap（jdk 1.8）
  使用哈希表存儲鍵值對，底層是一個存儲Node的table數組。其基本的運行邏輯是，table數組的每一個元素是一個槽，用於存儲Node對象，向Hash表中插入鍵值對時，首先計算鍵的hash值，並對數組容量（即數組長度）取余，定位該鍵值對應放在哪個槽中，若槽中已經存在元素（即哈希沖突），將Node節點插入到沖突鏈表尾端，當該槽中結點超過一定數量（默認為8）並且哈希表容量超過一定值（默認為64）時，對該鏈表進行樹化。低於一定數量（默認為6）後進行resize時，樹形結構又會鏈表化。當哈希表的總節點數超過閾值時，對哈希表進行擴容，容量翻倍。

由於哈希表需要用到key的哈希函數，因此對於自定義類作為key使用哈希表時，需要重寫哈希函數，保證相等的key哈希值相同。

由於擴容或樹化過程Node節點的位置會發生改變，因此哈希表是無序的，不同時期遍歷同一張哈希表，得到的節點順序會不同。

成員變數

    Hash表的成員變數主要有存儲鍵值對的table數組，size，裝載因子loadFactory，閾值theshold，容量capacity。

table數組：

哈希表的實質就是table數組，它用來存儲鍵值對。哈希表中內部定義了Node類來封裝鍵值對。

 Node類實現了Map的Entry介面。包括key，value，下一個Node指針和key的hash值。

 容量Capacity：

HashMap中沒有專門的屬性存儲容量，容量等於table.lenth，即數組的長度，默認初始化容量為16。初始化時，可以指定哈希表容量，但容量必須是2的整數次冪，在初始化過程中，會調用tableSizeFor函數，得到一個不小於指定容量的2的整數次冪，暫時存入到threshold中。

注意，若容量設置過大，那麼遍歷整個哈希表需要耗費更多的時間。

    閾值threshold：

指定當前hash表最多存儲多少個鍵值對，當size超過閾值時，hash表進行擴容，擴容後容量翻倍。

   loadFactory：

threshold=capacity*loadFactory。

裝填因子的大小決定了哈希表存儲鍵值對數量的能力，它直接影響哈希表的查找性能。初始化時可以指定loadFactory的值，默認為0.75。

 初始化過程

哈希表有3個構造函數，用戶可以指定哈希表的初始容量和裝填因子，但初始化過程只是簡單填入這兩個參數，table數組並沒有初始化。注意，這里的initialCapacity會向上取2的整數次冪並暫時保存到threshold中。

table數組的初始化是在第一次插入鍵值對時觸發，實際在resize函數中進行初始化。

hash過程與下標計算

哈希表是通過key的哈希值決定Node放入哪個槽中， 在java8中 ，hash表沒有直接用key的哈希值，而是自定義了hash函數。

哈希表中的key可以為null，若為null，哈希值為0，否則哈希值（一共32位）的高16位不變，低16位與高16位進行異或操作，得到新的哈希值。（h >>> 16，表示無符號右移16位，高位補0，任何數跟0異或都是其本身，因此key的hash值高16位不變。）

之所以這樣處理，是與table的下標計算有關

因為，table的長度都是2的冪，因此index僅與hash值的低n位有關（n-1為0000011111的形式），hash值的高位都被與操作置為0了，相當於hash值對n取余。

由於index僅與hash值的低n位有關，把哈希值的低16位與高16位進行異或處理，可以讓Node節點能更隨機均勻得放入哈希表中。

get函數：

V  get(Object key) 通過給定的key查找value

先計算key的哈希值，找到對應的槽，遍歷該槽中所有結點，如果結點中的key與查找的key相同或相等，則返回value值，否則返回null。

注意，如果返回值是null，並不一定是沒有這種KV映射，也有可能是該key映射的值value是null，即key-null的映射。也就是說，使用get方法並不能判斷這個key是否存在，只能通過containsKey方法來實現。

put函數

V put(K key, V value) 存放鍵值對

計算key的哈希值，找到哈希表中對應的槽，遍歷該鏈表，如果發現已經存在包含該key的Node，則把新的value放入該結點中，返回該結點的舊value值（舊value可能是null），如果沒有找到，則創建新結點插入到 鏈表尾端 （java7使用的是頭插法），返回null。插入結點後需要判斷該鏈表是否需要樹化，並且判斷整個哈希表是否需要擴容。

由該演算法可以看出，哈希表中不會有兩個key相同的鍵值對。

resize函數

    resize函數用來初始化或擴容table數組。主要做了兩件事。

1.根據table數組是否為空判斷初始化還是擴容，計算出相應的newCap和newThr，新建table數組並設置新的threshold。

2.若是進行擴容，則需要將原數組中的Node移植到新的數組中。

由於數組擴容，原來鍵值對可能存儲在新數組不同的槽中。但由於鍵值對位置是對數組容量取余（index=hash(key)&(Capacity-1)）,由於Capacity固定為2的整數次冪，並新的Capacity（newCap）是舊的兩倍（oldCap）。因此，只需要判斷每個Node中的hash值在oldCap二進制那一位上是否為0(hash&oldCap==0)，若為0，對newCap取余值與oldCap相同，Node在新數組中槽的位置不變，若為1，新的位置是就得位置加一個oldCap值。

因此hashMap的移植演算法是，遍歷舊的槽：

若槽為空，跳過。

若槽只有一個Node，計算該Node在新數組中的位置，放入新槽中。

若槽是一個鏈表，則遍歷這個鏈表，分別用loHead，loTail,hiHead,hiTail兩組指針建立兩個鏈表，把hash值oldCap位為0的Node節點放入lo鏈表中，hash值oldCap位為1的節點放入hi鏈表中，之後將兩個鏈表分別插入到新數組中，實現原鍵值對的移植。

lo鏈表放入新數組原來位置，hi鏈表放入新數組原來位置+oldCap中

樹化過程 ：

當一個槽中結點過多時，哈希表會將鏈表轉換為紅黑樹，此處挖個坑。

[總結] java8中hashMap的實現原理與7之間的區別：

1.hash值的計算方法不同 2.鏈表採用尾插法，之前是頭插法 3.加入了紅黑樹結構

❺ 如何閱讀concurrenthashmap源碼

nized是針對整張Hash表的，即每次鎖住整張表讓線程獨占，ConcurrentHashMap允許多個修改操作並發進行，其關鍵在於使用了鎖分離技術。它使用了多個鎖來控制對hash表的不同部分進行的修改。ConcurrentHashMap內部使用段(Segment)來表示這些不同的..

❻ HashMap底層實現原理剖析

Hashmap是一種非常常用的、應用廣泛的數據類型，最近研究到相關的內容，就正好復習一下。網上關於hashmap的文章很多，但到底是自己學習的總結，就發出來跟大家一起分享，一起討論。

1.HashMap的數據結構：在java 中 數據結構，最基本 也就兩種 一種數組 一種模擬指針。所有的數據結構都可以用這兩個基本結構來構造的，hashmap也不例外。Hashmap實際上是一個數組和鏈表的結合體。數組的默認長度為16，

2.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 = {}; //null 的hashMap

transient Entry[] table = (Entry[]) EMPTY_TABLE;///動態擴大容器時使用的一個hashMap

transient int size;//當前數據量

int threshold;//擴大容器時的大小 為 capacity * load factor

final float loadFactor;//使用率閥值，默認為：DEFAULT_LOAD_FACTOR

存取元素 ：調用put方法

public V put(K key, V value) { 

//判斷當前table 為Null 第一次Put 

 if (table == EMPTY_TABLE) {

     inflateTable(threshold);  //初始化容器的大小

 }

 if (key == null) 

 return putForNullKey(value); //判斷當前key 為null 將Null key添加到數組的第一個位置

 int hash = hash(key); //將當前key進行hash 詳情見下方

 int i = indexFor(hash, table.length); //調用完hash演算法後，詳情見下方

 for (Entry e = table[i]; e != null; e = e.next) { //循環判斷當前數組下標為Entry的實體 將當前key相同的替換為最新的值

            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); //如果key都不同 則添加Entry.詳情見下方

        return null;

    }

hashMap的hash演算法剖析

final int hash(Object k) {

        int h = hashSeed;

        if (0 != h && k instanceof String) {  //判斷當前k是否為string 和

            return sun.misc.Hashing.stringHash32((String) k); //使用stringHash32演算法得出key   的hash值

        }

        h ^= k.hashCode(); //調用key的hashCode 得出值 後使用"或"運算符 

        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

前面說過HashMap的數據結構是數組和鏈表的結合，所以我們當然希望這個HashMap裡面的 元素位置盡量的分布均勻些，盡量使得每個位置上的元素數量只有一個，那麼當我們用hash演算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去遍歷鏈表，這樣就大大優化了查詢的效率。

一個十進制數32768(二進制1000 0000 0000 0000)，經過上述公式運算之後的結果是35080(二進制1000 1001 0000 1000)。看出來了嗎？或許這樣還看不出什麼，再舉個數字61440(二進制1111 0000 0000 0000)，運算結果是65263(二進制1111 1110 1110 1111)，現在應該很明顯了，它的目的是讓「1」變的均勻一點，散列的本意就是要盡量均勻分布。使用上述演算法後 "1"就變得很均勻了。

我們用table[index]表示已經找到的元素需要存儲的位置。先判斷該位置上有沒有元素（這個元素是HashMap內部定義的一個類Entity， 基本結構它包含三個類，key，value和指向下一個Entity的next）,沒有的話就創建一個Entity對象，在 table[index]位置上插入，這樣插入結束；如果有的話，通過鏈表的遍歷方式去逐個遍歷，看看有沒有已經存在的key，有的話用新的value替 換老的value；如果沒有，則在table[index]插入該Entity，把原來在table[index]位置上的Entity賦值給新的 Entity的next，這樣插入結束

    }

indexFor 返回當前數組下標 ，

static int indexFor(int h, int length) {

        return h & (length-1);

    }

那麼得到key 之後的hash如何得到數組下標呢 ？把h與HashMap的承載量（HashMap的默認承載量length是16，可以自動變長。在構造HashMap的時候也可以指定一個長 度。這個承載量就是上圖所描述的數組的長度。）進行邏輯與運算，即 h & (length-1)，這樣得到的結果就是一個比length小的正數，我們把這個值叫做index。其實這個index就是索引將要插入的值在數組中的 位置。第2步那個演算法的意義就是希望能夠得出均勻的index，這是HashTable的改進，HashTable中的演算法只是把key的 hashcode與length相除取余，即hash % length，這樣有可能會造成index分布不均勻。

首先來解釋一下為什麼數組大小為2的冪時hashmap訪問的性能最高？

看下圖，左邊兩組是數組長度為16（2的4次方），右邊兩組是數組長度為15。兩組的hashcode均為8和9，但是很明顯，當它們和1110「與」的時候，產生了相同的結果，也就是說它們會定位到數組中的同一個位置上去，這就產生了碰撞，8和9會被放到同一個鏈表上，那麼查詢的時候就需要遍歷這個鏈表，得到8或者9，這樣就降低了查詢的效率。同時，我們也可以發現，當數組長度為15的時候，hashcode的值會與14（1110）進行「與」，那麼最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數組可以使用的位置比數組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率！ 

void addEntry(int hash, K key, V value, int bucketIndex) {

  //// 若HashMap的實際大小 不小於 「閾值」，則調整HashMap的大小

        if ((size >= threshold) && (null != table[bucketIndex])) {

            resize(2 * table.length);

            hash = (null != key) ? hash(key) : 0;

          //// 設置「bucketIndex」位置的元素為「新Entry」，// 設置「e」為「新Entry的下一個節點」

            bucketIndex = indexFor(hash, table.length);

        }

        createEntry(hash, key, value, bucketIndex);

    }

//將當前key 和value添加到Entry[]中

void createEntry(int hash, K key, V value, int bucketIndex) { 

        Entry e = table[bucketIndex];  //將第一個就得table 復制個新的entry 

        table[bucketIndex] = new Entry<>(hash, key, value, e); //將當前新的Entry 復制個table[bucketIndex]  舊的table[bucketIndex] 和新的table[buckIndex]之間用next關聯。第一個鍵值對A進來，通過計算其key的hash得到的index=0，記做:table[0] = A。一會後又進來一個鍵值對B，通過計算其index也等於0，現在怎麼辦？HashMap會這樣做: B.next = A ,table[0] = B,如果又進來C,index也等於0,那麼 C.next = B ,table[0] = C；這樣我們發現index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起

        size++; //容量加1

    }

以上就是HashMap添加元素時的過程解析

那麼如何get元素呢？

public V get(Object key) {

 if (key == null) return getForNullKey(); //當前key是否為null 如果為null值返回table[0]這個value

    Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();

    }

final EntrygetEntry(Object key) {

 if (size == 0) { return null; }  //判斷容量是否大於0 

 int hash = (key == null) ? 0 : hash(key); //對當前key 進行hash hash後得到一個值

 for (Entry e = table[indexFor(hash, table.length)]; //獲取當前Entry 循環遍歷

            e != null;

            e = e.next) {

            Object k;

            if (e.hash == hash &&

                ((k = e.key) == key || (key != null && key.equals(k))))

                return e;

        }

        return null;

    }

擴展問題:

1.當前我們的hashMap中越來越大的之後，"碰撞"就越來越明顯，那麼如何解決碰撞呢？擴容！

當hashmap中的元素個數超過數組大小capti*loadFactor時，就會進行數組擴容，loadFactor的默認值為0.75，也就是說，默認情況下，數組大小為16，那麼當hashmap中元素個數超過16*0.75=12的時候，就把數組的大小擴展為2*16=32，即擴大一倍，然後重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知hashmap中元素的個數，那麼預設元素的個數能夠有效的提高hashmap的性能。比如說，我們有1000個元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合適，不過上面annegu已經說過，即使是1000，hashmap也自動會將其設置為1024。 但是new HashMap(1024)還不是更合適的，因為0.75*1000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合適，既考慮了&的問題，也避免了resize的問題

HashMap的兩種遍歷方式

第一種

Map map = newHashMap();

Iterator iter = map.entrySet().iterator();

while(iter.hasNext()) {

Map.Entry entry = (Map.Entry) iter.next();

Object key = entry.getKey();

Object val = entry.getValue();

}

效率高,以後一定要使用此種方式！

第二種

Map map = newHashMap();

Iterator iter = map.keySet().iterator();

while(iter.hasNext()) {

Object key = iter.next();

Object val = map.get(key);

}

效率低,以後盡量少使用！

歸納

簡單地說，HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層採用一個 Entry[] 數組來保存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據hash演算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的鏈表中的存儲位置；當需要取出一個Entry時，

也會根據hash演算法找到其在數組中的存儲位置，再根據equals方法從該位置上的鏈表中取出該Entry。

❼ 為什麼要重寫hashcode方法

重載equals比說基於象內容實現保留hashCode實現變能某兩象明明相等hashCode卻
用其作鍵保存hashMap、hasoTable或hashSet再相等找另作鍵值查找候則根本找
使用HashMapkey自定義類必須重寫hashcode()equals()
於每象通其hashCode()其整形值（散列碼）該整型值處理作數組標存放該象所應Entry（存放該象及其應值） equals()則HashMap插入值或查詢使用HashMap插入值或查詢值應散列碼與數組散列碼相等則通equals比較key值否相等所想自建象作HashMapkey必須重寫該象繼承objecthashCodeequals 2.本hashcode()equals()幹嘛要重寫直接用原行 HashMap要比較key否相等要同使用兩函數自定義類hashcode()繼承於Object類其hashcode碼默認內存址即便相同含義兩象比較相等例兩羊象理解兩象應該相等重寫 hashcode（）比較相等
HashMap比較key先求keyhashcode(),比較其值否相等若相等再比較equals(),若相等則認相等若equals()相等則認相等重寫hashcode()重寫equals()比較equals()看否同象（即進行內存址比較）,所必定要兩起重寫HashMap用判斷key否相等其實調用HashSet判斷加入元素否相等
引用別說段哈~
般說要類象放入容器通要其重寫equals()讓比較址值內容值特別要類象放入散列要重寫hashCode()；要放序容器要重寫compareTo()
equals()相等兩象hashcode()定相等；
equals（）相等兩象卻並能證明hashcode()相等換句說equals()相等兩象hashcode()能相等（我理解由於哈希碼候產沖突造）
反：hashcode()等定能推equals()等；hashcode()相等equals()能相等能等
我理解哈

❽ java查看hashmap的源碼發現並沒有向entrySet中裝入元素，而去可以如下遍歷。

首先hashmap保存了一個屬性
private transient Set<Map.Entry<K,V>> entrySet = null;
下面是hashmap的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;
}
在你put元素進去的時候就自動填進去了。在remove等操作也是包含的。
Entry是hashmap的一個內部類。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
}
方法我就不寫了。該內部類保存了一個當前的一個key值value值，還包含指向下一個Entry的引用。寫的不仔細，沒有工具查看，直接看源碼文件的不方便。

❾ HashMap源碼中put方法裡面e.hash == hash && ((k = e.key) == key || key.equals(k))

我認為這個是比較效率的問題，這樣寫可以盡量少的調用equals
如果把e.hash == hash去掉，只用equals比較，效率太低
(k = e.key) == key如果是true說明是同一個對象，就不用equals了，效率較高

❿ 同步的數據結構，例如concurrenthashmap的源碼理解以及內部實現原理，為什麼他是同

nized是針對整張Hash表的，即每次鎖住整張表讓線程獨占，ConcurrentHashMap允許多個修改操作並發進行，其關鍵在於使用了鎖分離技術。它使用了多個鎖來控制對hash表的不同部分進行的修改。ConcurrentHashMap內部使用段(Segment)來表示這些不同的部分，每個段其實就是一個小的hash table，它們有自己的鎖。只要多個修改操作發生在不同的段上，它們就可以並發進行。
有些方法需要跨段，比如size()和containsValue()，它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段，操作完畢後，又按順序釋放所有段的鎖。這里「按順序」是很重要的，否則極有可能出現死鎖，在ConcurrentHashMap內部，段數組