java面試都問知不知道hashmap的原理？

Java中的HashMap可以說是平時開發(fā)中最常用的數(shù)據(jù)結(jié)構(gòu)之一了，經(jīng)常使用的集合類還有ArrayList、HashSet，基本上用好HashMap、ArrayList、HashSet這三大集合類，大多數(shù)的業(yè)務(wù)場景就滿足了，掌握這三大集合類也是作為一名Java程序員的基礎(chǔ)能力。

平時開發(fā)大多數(shù)的業(yè)務(wù)場景都是CRUD，且數(shù)據(jù)量都很小，所以基本上不會有什么問題。那么還需要知道其底層實現(xiàn)原理嗎？還需要知道這些集合類的數(shù)據(jù)結(jié)構(gòu)嗎？

當(dāng)然需要，這很重要！這里就拿HashMap來具體說一說了解它的設(shè)計思想多么的重要！

HashMap的數(shù)據(jù)結(jié)構(gòu)

HashMap的底層數(shù)據(jù)結(jié)構(gòu)簡單來說就是數(shù)組+鏈表+紅黑樹，這個大家都知道，面試也是高頻面試題，用一張圖來形容就是：

那這個時候你就得知道數(shù)組的好處了，基于下標(biāo)的隨機訪問和賦值數(shù)組元素的時間復(fù)雜度都是O(1)，這就能保證HashMap數(shù)據(jù)沒有哈希沖突的時候它的set/put方法都是O(1)的，這也是HashMap要追求的極致目標(biāo)（盡管會有哈希沖突）。這就是HashMap查詢性能快、插入數(shù)據(jù)快的主要原因，是一個空間換時間的思想。

哈希

但前提是我們得知道我們要把一個數(shù)據(jù)插入到數(shù)組的哪個下標(biāo)，因此就采用了哈希的思想。一個對象一定有一個唯一的hash值，但是兩個對象也有可能有相同的hash值，這叫“哈希沖突”。所以為了更好的利用數(shù)組，哈希值計算要盡可能的避免沖突，也就是追求“低碰撞率”。

這也涉及到另外一個問題，比較一個對象的時候為什么要重寫它的hashcode()方法和equals()方法。

那業(yè)內(nèi)除了Java自帶的Hashcode()方法還有哪些hash算法你了解嗎？比如MurmurHash算法。他們都在哪些開源軟件中應(yīng)用到？各種哈希算法的性能比較又如何？我們平時開發(fā)能不能借鑒這種思想？

數(shù)組與鏈表

當(dāng)哈希沖突的時候，HashMap就會使用到鏈表，即數(shù)組+鏈表，那你知道數(shù)組和鏈表的區(qū)別嗎？LinkedHashMap和HashMap的區(qū)別呢？都適合在哪些場景用到？如果讓你手寫一個LRU緩存，你會怎么寫？

你可能想說我不需要知道數(shù)組和鏈表的數(shù)據(jù)結(jié)構(gòu)，我也沒有手寫LRU緩存的場景，我只想做一條安靜的咸魚，簡簡單單CRUD就好。

高效查找

大家都說平時開發(fā)都是CRUD，那你知道如何把CRUD寫的高大上一點嗎？比如其中的C（查詢）應(yīng)該是最為頻繁的。學(xué)過數(shù)據(jù)結(jié)構(gòu)的都知道，高效查找主要的兩種算法：有序查找（二分）和哈希查找。HashMap的數(shù)組就是用到了哈希查找，時間復(fù)雜度是O(1)，那么你理解了HashMap的原理是不是就基本掌握了哈希查找算法的原理？另外當(dāng)哈希沖突導(dǎo)致鏈表節(jié)點數(shù)量達到8時候，就會變成紅黑樹，紅黑樹就是有序查找的變種。如果你又進一步掌握了紅黑樹的查找原理，是不是就基本掌握了有序查找算法的原理？所以HashMap的原理重不重要？掌握了HashMap的原理是不是就掌握了高效查找的方法？如果你沒掌握這些原理，你覺得掌握了沒有用，但是當(dāng)你掌握了，在日常業(yè)務(wù)開發(fā)中你會發(fā)現(xiàn)受用無窮。

HashMap中還有很多思想值得大家學(xué)習(xí)，掌握這些思想后，其實才是你編程能力的質(zhì)的提升。手里有武器不用和手里沒有武器不是一回事。