最近參與公司的實(shí)習(xí)生招聘工作窒盐，面試了幾位實(shí)習(xí)生，我有一道每次面試都必問(wèn)的題目【HasmMap的工作原理】，但很遺憾挑社，至今還沒(méi)遇到令我完全滿意的回答。今天這篇文章就來(lái)回答下HashMap相關(guān)的面試題巡揍。
1. 什么是HashMap痛阻？
java.util.HashMap是Java語(yǔ)言標(biāo)準(zhǔn)庫(kù)中的一個(gè)容器類，主要用來(lái)存儲(chǔ)鍵值對(duì)腮敌。是數(shù)據(jù)結(jié)構(gòu)中哈希表在Java語(yǔ)言的一個(gè)實(shí)現(xiàn)录平。
哈希表是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)概念麻车，可以存儲(chǔ)n個(gè)元素，取元素的時(shí)間復(fù)雜度為O(1).
一般情況下斗这，從n個(gè)元素中查找一個(gè)元素动猬，時(shí)間復(fù)雜度為O(n). 為何哈希表能有O(1)的時(shí)間復(fù)雜度？
因?yàn)樵卦诖鎯?chǔ)時(shí)已經(jīng)大致確定了位置表箭，查找的時(shí)候可以定位到對(duì)應(yīng)的位置赁咙，因此時(shí)間復(fù)雜度為O(1).
2. HashMap中的數(shù)據(jù)結(jié)構(gòu)
HashMap使用數(shù)組+鏈表的方式實(shí)現(xiàn)。
數(shù)組的作用主要是定位元素位置免钻。
鏈表的作用是解決哈希沖突問(wèn)題彼水。遇到hash值相等的key，就把相應(yīng)鍵值使用鏈表的方式全部保存下來(lái)极舔。
3. put操作
put方法定義
public V put(K key, V value)
put操作執(zhí)行過(guò)程：
a. 計(jì)算key的hashcode
b. 根據(jù)hashcode計(jì)算出需要將該鍵值對(duì)存儲(chǔ)的位置-即桶的位置
c. 找到桶的位置后凤覆，如果桶未被占用，則存入該鍵值對(duì)拆魏；若桶中已有數(shù)據(jù)盯桦，則需要遍歷桶中數(shù)據(jù)，并且比較key的equals方法渤刃。遇到key相同的拥峦，則用新的value，把舊值替換掉（put操作會(huì)將舊值覆蓋掉）卖子。若沒(méi)找到略号，則將該鍵值對(duì)存儲(chǔ)在鏈表的末尾。
4. get操作
get方法定義
public V get(Object key)
get操作執(zhí)行過(guò)程：
a. 計(jì)算key的hashcode
b. 根據(jù)hashcode洋闽，定位該元素所在桶的位置
c. 若桶為空玄柠，則返回null；若桶不空诫舅，則遍歷桶中數(shù)據(jù)随闪，比較key的equals方法，若遇到相同的元素骚勘，則返回對(duì)于的value中铐伴；沒(méi)遇到，則返回null
5. 什么樣的類型可以作為HashMap的key俏讹？
a. 重寫hashCode() 和 equals() 方法
HashMap在get/put數(shù)據(jù)時(shí)当宴，需要調(diào)用hashCode() 和 equals() 方法，因此只有重寫了hashCode() 和 equals() 方法的類泽疆，才可以作為HashMap的key户矢。
（hashCode相同，對(duì)象不一定相等殉疼；對(duì)象相等梯浪，則hashCode必然相同）
b. 不可變性
不可變性也是必要的捌年，若元素可變，則相應(yīng)hashCode也會(huì)發(fā)生變化挂洛，調(diào)用get()方法時(shí)礼预，可能找不到相應(yīng)的value，甚至可能找到錯(cuò)誤的value虏劲。
6. 如何計(jì)算數(shù)組下標(biāo)
在JDK1.8之前的版本中托酸，是通過(guò)key的hashCode()進(jìn)行hashing，然后將( n-1 & hash)來(lái)確定數(shù)組下標(biāo)柒巫，即桶的位置励堡。
在JDK1.8版本，將hash值的高16位與低16位進(jìn)行異或
JDK 1.8：
(h = key.hashCode()) ^ (h >>>16)
這樣做的目的主要是為了減少哈希沖突的可能性堡掏。特別是數(shù)據(jù)量較小時(shí)应结，舊的計(jì)算方式哈希沖突的可能比較大。
7. HashMap的兩個(gè)重要概念
容量(Capacity)泉唁，即HashMap中數(shù)組的大小鹅龄，也是桶的個(gè)數(shù)
負(fù)載因子(load factor)，也成裝載因子 = hashmap中實(shí)際保存鍵值對(duì)個(gè)數(shù) / hashmap中數(shù)組的大小
隨著HashMap中元素個(gè)數(shù)的增多游两，負(fù)載因子增大砾层。如果不做額外的處理漩绵，則桶中的鏈表會(huì)越來(lái)越長(zhǎng)贱案，因此HashMap就無(wú)法保證取元素時(shí)O(1)的時(shí)間復(fù)雜度。因此止吐，必須要調(diào)整HashMap中數(shù)組的大小
HashMap中定義的默認(rèn)負(fù)載因子大小為0.75宝踪，當(dāng)負(fù)載因子大于該值時(shí)，將對(duì)數(shù)組進(jìn)行擴(kuò)容
8. HashMap其他面試題
HashMap與HashTable區(qū)別：Hashtable中加入了鎖碍扔，線程安全瘩燥；HashMap線程不安全。也正因?yàn)镠ashtable中加入了鎖不同，導(dǎo)致性能上要差于HashMap厉膀。
ConcurrentHashMap：HashMap、Hashtable在性能和安全性上的一個(gè)折中方案二拐。實(shí)現(xiàn)原理是ConcurrentHashMap中將Map劃分為多個(gè)子Map服鹅，子Map分別加鎖。對(duì)一個(gè)子Map加鎖以后乡括，不影響對(duì)其他子Map的訪問(wèn)丘侠。
9. 為什么要面試這道題目
a. 考察求職者技術(shù)水平.
我一把把這道題目作為第一道面試題來(lái)考察求職者姑廉。根據(jù)回答情況，能大致推測(cè)到求職者的水平仗哨，方便后續(xù)的面試形庭。
零級(jí)水平：完全不知道。（當(dāng)然厌漂，這種可能性很少萨醒。畢竟HashMap是非常常用的一個(gè)工具類）
一級(jí)水平：可以回答HashMap的時(shí)間復(fù)雜度，容量桩卵，裝載因子等概念
二級(jí)水平：回答出get/put操作的完整過(guò)程验靡。（多數(shù)求職者都沒(méi)能完整的回答這個(gè)問(wèn)題。能完全回答出這個(gè)問(wèn)題雏节，說(shuō)明求職者對(duì)哈希的思想有完整的理解胜嗓，而且很可能閱讀過(guò)HashMap的源碼 - 要想寫好代碼，首先要閱讀優(yōu)秀源代碼的習(xí)慣）
三級(jí)水平：回答出hashCode钩乍，equals作用辞州，不可變性，線程安全的Map（基本上滿足公司實(shí)習(xí)生的要求寥粹，可以發(fā)offer了）
b. 考察求職者表達(dá)能力
能夠把一件復(fù)雜的事情講的清晰易懂变过，是件了不起的能力。（筆者在這方面能力有所欠佳）
注：
HashMap中其實(shí)允許null作為key涝涤，因?yàn)樵趃et/put操作時(shí)都會(huì)對(duì)null值做特殊的處理媚狰。
本文主要是從哈希表的角度來(lái)講述HashMap，因此這些細(xì)節(jié)問(wèn)題并未涉及阔拳。
