問(wèn)答專欄Q & A COLUMN
Java中的HashMap可以說(shuō)是平時(shí)開(kāi)發(fā)中最常用的數(shù)據(jù)結(jié)構(gòu)之一了，經(jīng)常使用的集合類還有ArrayList、HashSet，基本上用好HashMap、ArrayList、HashSet這三大集合類，大多數(shù)的業(yè)務(wù)場(chǎng)景就滿足了，掌握這三大集合類也是作為一名Java程序員的基礎(chǔ)能力。
平時(shí)開(kāi)發(fā)大多數(shù)的業(yè)務(wù)場(chǎng)景都是CRUD，且數(shù)據(jù)量都很小，所以基本上不會(huì)有什么問(wèn)題。那么還需要知道其底層實(shí)現(xiàn)原理嗎？還需要知道這些集合類的數(shù)據(jù)結(jié)構(gòu)嗎？
當(dāng)然需要，這很重要！這里就拿HashMap來(lái)具體說(shuō)一說(shuō)了解它的設(shè)計(jì)思想多么的重要！
HashMap的底層數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單來(lái)說(shuō)就是數(shù)組+鏈表+紅黑樹(shù)，這個(gè)大家都知道，面試也是高頻面試題，用一張圖來(lái)形容就是：
那這個(gè)時(shí)候你就得知道數(shù)組的好處了，基于下標(biāo)的隨機(jī)訪問(wèn)和賦值數(shù)組元素的時(shí)間復(fù)雜度都是O(1)，這就能保證HashMap數(shù)據(jù)沒(méi)有哈希沖突的時(shí)候它的set/put方法都是O(1)的，這也是HashMap要追求的極致目標(biāo)（盡管會(huì)有哈希沖突）。這就是HashMap查詢性能快、插入數(shù)據(jù)快的主要原因，是一個(gè)空間換時(shí)間的思想。
但前提是我們得知道我們要把一個(gè)數(shù)據(jù)插入到數(shù)組的哪個(gè)下標(biāo)，因此就采用了哈希的思想。一個(gè)對(duì)象一定有一個(gè)唯一的hash值，但是兩個(gè)對(duì)象也有可能有相同的hash值，這叫“哈希沖突”。所以為了更好的利用數(shù)組，哈希值計(jì)算要盡可能的避免沖突，也就是追求“低碰撞率”。
這也涉及到另外一個(gè)問(wèn)題，比較一個(gè)對(duì)象的時(shí)候?yàn)槭裁匆貙?xiě)它的hashcode()方法和equals()方法。
那業(yè)內(nèi)除了Java自帶的Hashcode()方法還有哪些hash算法你了解嗎？比如MurmurHash算法。他們都在哪些開(kāi)源軟件中應(yīng)用到？各種哈希算法的性能比較又如何？我們平時(shí)開(kāi)發(fā)能不能借鑒這種思想？
當(dāng)哈希沖突的時(shí)候，HashMap就會(huì)使用到鏈表，即數(shù)組+鏈表，那你知道數(shù)組和鏈表的區(qū)別嗎？LinkedHashMap和HashMap的區(qū)別呢？都適合在哪些場(chǎng)景用到？如果讓你手寫(xiě)一個(gè)LRU緩存，你會(huì)怎么寫(xiě)？
你可能想說(shuō)我不需要知道數(shù)組和鏈表的數(shù)據(jù)結(jié)構(gòu)，我也沒(méi)有手寫(xiě)LRU緩存的場(chǎng)景，我只想做一條安靜的咸魚(yú)，簡(jiǎn)簡(jiǎn)單單CRUD就好。
大家都說(shuō)平時(shí)開(kāi)發(fā)都是CRUD，那你知道如何把CRUD寫(xiě)的高大上一點(diǎn)嗎？比如其中的C（查詢）應(yīng)該是最為頻繁的。學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的都知道，高效查找主要的兩種算法：有序查找（二分）和哈希查找。HashMap的數(shù)組就是用到了哈希查找，時(shí)間復(fù)雜度是O(1)，那么你理解了HashMap的原理是不是就基本掌握了哈希查找算法的原理？另外當(dāng)哈希沖突導(dǎo)致鏈表節(jié)點(diǎn)數(shù)量達(dá)到8時(shí)候，就會(huì)變成紅黑樹(shù)，紅黑樹(shù)就是有序查找的變種。如果你又進(jìn)一步掌握了紅黑樹(shù)的查找原理，是不是就基本掌握了有序查找算法的原理？所以HashMap的原理重不重要？掌握了HashMap的原理是不是就掌握了高效查找的方法？如果你沒(méi)掌握這些原理，你覺(jué)得掌握了沒(méi)有用，但是當(dāng)你掌握了，在日常業(yè)務(wù)開(kāi)發(fā)中你會(huì)發(fā)現(xiàn)受用無(wú)窮。
HashMap中還有很多思想值得大家學(xué)習(xí)，掌握這些思想后，其實(shí)才是你編程能力的質(zhì)的提升。手里有武器不用和手里沒(méi)有武器不是一回事。
評(píng)論0
加載中...
我覺(jué)得底層他更多的是思想，理解思想有利于更快的學(xué)習(xí)其他知識(shí)，另一個(gè)對(duì)于排錯(cuò)也會(huì)有容易一些！
評(píng)論0
加載中...0
回答0
回答0
回答0
回答0
回答0
回答0
回答0
回答0
回答0
回答
