1? 哈希Map
今天要聊的，是一個(gè)在Java/Android面試中被問爛了的類: Hashmap.
這個(gè)類如此的被看重懈凹，上至阿里 高P面試蜀变，下到 數(shù)據(jù)結(jié)構(gòu)入門教材。??
甚至剛上門取件的快遞小哥都能跟你用背課文的語氣侃侃而談介评，hashmap的底層是數(shù)組加鏈表库北。
但是今天要聊的又有點(diǎn)不太一樣。你真的知道啥是hashmap们陆，為啥要數(shù)組加鏈表嗎寒瓦？
2? ? 散列表
一切都要從數(shù)據(jù)結(jié)構(gòu)說起 .? ?曾經(jīng)有一位大佬說過? 程序= 數(shù)據(jù)結(jié)構(gòu)+算法。
數(shù)據(jù)結(jié)構(gòu)分為兩類：
1? 是數(shù)據(jù)的邏輯結(jié)構(gòu)：? 也就是數(shù)據(jù)元素之間的邏輯關(guān)系
2? ?是數(shù)據(jù)的儲(chǔ)存結(jié)構(gòu)? ?是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示坪仇，又稱物理結(jié)構(gòu)杂腰。
數(shù)據(jù)的儲(chǔ)存結(jié)構(gòu)是邏輯結(jié)構(gòu)使用計(jì)算機(jī)語言的實(shí)現(xiàn)。
分為四類：? 順序椅文，鏈表喂很，索引和散列惜颇。?
這四類數(shù)據(jù)結(jié)構(gòu)又被廣大碼農(nóng)親切的稱為 "茴"字的四種寫法。
咱們今天要聊的HashMap 在邏輯邏輯上屬于廣義表少辣，在儲(chǔ)存結(jié)構(gòu)上散列凌摄。
合起來可以稱其為 散列表。
3? ? 散列表的特點(diǎn)和用途
講了這么多理論漓帅，那么Hashmap 有什么特點(diǎn)望伦，什么時(shí)候使用它啊。
hashmap的時(shí)間復(fù)雜度 為O(1)（理想情況）煎殷，空間復(fù)雜度 為? N / 擴(kuò)容因子
通俗一點(diǎn)來說屯伞， hashmap 是一個(gè)查詢速度快（常數(shù)級(jí)別），內(nèi)存占用多（內(nèi)存使用有效率低于擴(kuò)容因子）的數(shù)據(jù)結(jié)構(gòu)豪直。
良心的說劣摇，Hashmap 和他的近親 treemap 相比，其實(shí)并不適合在內(nèi)存緊張的移動(dòng)端使用弓乙。
正是因?yàn)槿绱四┤冢琯oogle 也推出了ArrayMap,sparseArray 來替代hashmap。
以下是性能對(duì)比圖
但是對(duì)于一些要求響應(yīng)速度的場景勾习，比如 api響應(yīng),或者 算密集型場景，以及很多sdk項(xiàng)目中懈玻，hashmap還是很常見的巧婶。
那么接下來我們使用C語言 來手動(dòng)實(shí)現(xiàn)一個(gè)散列表。
使用C來實(shí)現(xiàn)有兩個(gè)原因：
1? ? ? C語言更貼近硬件涂乌，手動(dòng)分配內(nèi)存的過程艺栈，能更好的表示散列表的數(shù)據(jù)構(gòu)建過程
2? ? ? ?前段時(shí)間做的項(xiàng)目，正好需要一個(gè) 運(yùn)行在android NDK 上的緩存組件湾盒。
4? ?什么是特么的散列表
下面列出的是 hashmap.h?的內(nèi)容湿右。
類似于Java中的接口。 實(shí)現(xiàn)了下列功能罚勾，對(duì)外毅人，我們就認(rèn)為他是一個(gè)可使用的散列表。
5? ?哈希和散列
我們要明白 哈希和散列 其實(shí)就是一回事兒丈莺。? ?
通俗講就是講各種各樣，千奇百怪的東西分衫，通過一個(gè)算法场刑，成為特定的有規(guī)律的東西般此。這個(gè)算法就叫做hash/散列算法蚪战。
比如你現(xiàn)在要手里攥了一把蔥花牵现，要把他分散的放到一張大餅上去。 這個(gè)撒蔥花的過程就叫散列邀桑。
散列算法有各種各樣的實(shí)現(xiàn)瞎疼。? 能夠讓把蔥花撒的又快，又均勻的方法就是較優(yōu)的hash算法壁畸。
查看jdk源碼贼急，我們會(huì)發(fā)現(xiàn)，?
object的hash算法是取內(nèi)存地址的偏移量
string的hash算法是 所有的字符單個(gè)*31再相加捏萍。
int的hash算法是其數(shù)值本身太抓。
那我們的hash算法呢？
我們的hash算法分為兩部
第一步是 類似Java的String令杈，將所有字符*31相加走敌。得到一個(gè)唯一值。
第二步逗噩，根據(jù)當(dāng)前的容量大小掉丽，取余。
我得承認(rèn)這個(gè)算法看上去很蠢异雁、
但這是我經(jīng)過試驗(yàn)之后能想到最好的散列算法了捶障。如果有更好的想法，歡迎留言我纲刀。
6? hash沖撞
當(dāng)我們對(duì)這張散列表進(jìn)行? 增刪查操作時(shí)项炼，
第一步就是上面提到了撒蔥花操作，先計(jì)算出這個(gè)蔥花應(yīng)該在的位置示绊。然后在對(duì)這個(gè)蔥花進(jìn)行處理芥挣。
但是問題在于 再優(yōu)秀的散列算法也沒辦法保證? 不會(huì)有兩個(gè)蔥花放到同樣的一個(gè)位置。
那么一個(gè)合格的hashmap組件一定要處理hash碰撞的情況耻台。先來看看Java8是怎么做的
（為什么采用紅黑樹空免，而不是其他樹結(jié)構(gòu)，也是值得拉出來聊聊的盆耽。但這不是我們要聊的重點(diǎn)蹋砚，下次再說。）
我們的hash沖突處理情況稍微簡單一些摄杂。如果沖突就以鏈表進(jìn)行處理坝咐。這其實(shí)也是Java7之前的處理方式。
與此對(duì)應(yīng)的析恢，刪除也是同樣的道理墨坚，通過hash算法找到位置之后。如果存在的是一個(gè)鏈表映挂，則對(duì)其進(jìn)行遍歷查詢操作泽篮。
7? ? 使用示例
8? ?性能測試
12000條數(shù)據(jù)隨機(jī)查詢對(duì)比
接下來加上 我們手寫的hashmap組件 對(duì)比一下查詢速度
嗯盗尸，這個(gè)故事告訴我們一個(gè)道理。? 牛不牛逼和語言關(guān)系不大帽撑。 C語言用的不好泼各，還不如Java呢。
