哈希表（hash table）也叫散列表，是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，應(yīng)用場(chǎng)景及其豐富，許多緩存技術(shù)（比如memcached）的核心其實(shí)就是在內(nèi)存中維護(hù)一張大的哈希表，而HashMap的實(shí)現(xiàn)原理也常常出現(xiàn)在各類的面試題中，重要性可見一斑。本文會(huì)對(duì)java集合框架中的對(duì)應(yīng)實(shí)現(xiàn)HashMap的實(shí)現(xiàn)原理進(jìn)行講解，然后會(huì)對(duì)JDK7的HashMap源碼進(jìn)行分析。
什么是哈希表
在討論哈希表之前，我們先大概了解下其他數(shù)據(jù)結(jié)構(gòu)在新增，查找等基礎(chǔ)操作執(zhí)行性能
數(shù)組：采用一段連續(xù)的存儲(chǔ)單元來存儲(chǔ)數(shù)據(jù)。對(duì)于指定下標(biāo)的查找，時(shí)間復(fù)雜度為O(1)；通過給定值進(jìn)行查找，需要遍歷數(shù)組，逐一比對(duì)給定關(guān)鍵字和數(shù)組元素，時(shí)間復(fù)雜度為O(n)，當(dāng)然，對(duì)于有序數(shù)組，則可采用二分查找，插值查找，斐波那契查找等方式，可將查找復(fù)雜度提高為O(logn)；對(duì)于一般的插入刪除操作，涉及到數(shù)組元素的移動(dòng)，其平均復(fù)雜度也為O(n)
線性鏈表：對(duì)于鏈表的新增，刪除等操作（在找到指定操作位置后），僅需處理結(jié)點(diǎn)間的引用即可，時(shí)間復(fù)雜度為O(1)，而查找操作需要遍歷鏈表逐一進(jìn)行比對(duì)，復(fù)雜度為O(n)
二叉樹：對(duì)一棵相對(duì)平衡的有序二叉樹，對(duì)其進(jìn)行插入，查找，刪除等操作，平均復(fù)雜度均為O(logn)。
哈希表：相比上述幾種數(shù)據(jù)結(jié)構(gòu)，在哈希表中進(jìn)行添加，刪除，查找等操作，性能十分之高，不考慮哈希沖突的情況下，僅需一次定位即可完成，時(shí)間復(fù)雜度為O(1)，接下來我們就來看看哈希表是如何實(shí)現(xiàn)達(dá)到驚艷的常數(shù)階O(1)的。
我們知道，數(shù)據(jù)結(jié)構(gòu)的物理存儲(chǔ)結(jié)構(gòu)只有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（像棧，隊(duì)列，樹，圖等是從邏輯結(jié)構(gòu)去抽象的，映射到內(nèi)存中，也這兩種物理組織形式），而在上面我們提到過，在數(shù)組中根據(jù)下標(biāo)查找某個(gè)元素，一次定位就可以達(dá)到，哈希表利用了這種特性，哈希表的主干就是數(shù)組。
比如我們要新增或查找某個(gè)元素，我們通過把當(dāng)前元素的關(guān)鍵字 通過某個(gè)函數(shù)映射到數(shù)組中的某個(gè)位置，通過數(shù)組下標(biāo)一次定位就可完成操作。
存儲(chǔ)位置 = f(關(guān)鍵字)
其中，
