1、哈希的原理
哈希的出現時因為傳統數據結構如線性表（數組，鏈表等），樹中，關鍵字與其它的存放位置不存在對應的關系。因此在查找關鍵字的時候需要逐個比對，雖然出現了二分查找等各種提高效率的的查找算法。但是這些並不足夠，希望在查詢關鍵字的時候不經過任何比較，一次存取便能得到所查記錄。因此，我們必須在關鍵字和其對應的存儲位置間建立對應的關系f。這種對應的關系f被稱為哈希函數，按此思想建立的表為哈希表。關鍵在於哈希函數如何構造。
有如下幾種方法：
1）直接定址法
取關鍵字或者關鍵字的某個線性函數值為哈希地址。
2）數字分析法
3）平方取中法
取關鍵字平方後的中間幾位為哈希地址。
4）折疊法
將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不通），然後取這幾部分的疊加和（捨去進位）作為哈希地址。
5）取余數法
取關鍵字被某個不大於哈希表表長(HASH_TABLE_LENGTH)的數p除後所得的余數作為哈希地址。
H(key) = key % p (其中p小於或者等於哈希表表長HASH_TABLE_LENGTH）
6）隨機數法
取關鍵字的隨機函數值作為它的哈希地址。
那麼確定了哈希函數之後，就要解決哈希沖突的問題，常用的方法如下：
1）開放定址法
Hi = (H(key) + di) % M i = 1, 2, 3,..., k ( k <= M-1 )
其中：H(key)為哈希函數；M為哈希表表長；di為增量序列；di可能有下列三種取法：
a 線性探測再散列：di = 1, 2, 3, ..., M-1
b 二次探測再散列：di = (+,-)k^2，(k <= M/2)
c 隨機探測再散列：di為隨機數序列
2）再哈希法
3）鏈地址法
4）建立一個公共溢出區
2、java中的hashmap是如何實現的
HashMap實際上是一個“鏈表散列”的數據結構，即數組和鏈表的結合體。我們可以理解為“鏈表的數組”，如圖：
HashMap其實也是一個線性的數組實現的,所以可以理解為其存儲數據的容器就是一個線性數組。那麼一個線性的數組怎麼實現按鍵值對來存取數據呢？這裡HashMap有做一些處理。
1.首先HashMap裡面實現一個靜態內部類Entry，其重要的屬性有 key , value, next，從屬性key,value我們就能很明顯的看出來Entry就是HashMap鍵值對實現的一個基礎bean，我們上面說到HashMap的基礎就是一個線性數組，這個數組就是Entry[]，Map裡面的內容都保存在Entry[]裡面。
2、hashmap中hash沖突的解決（鏈地址法）：Entry類裡面有一個next屬性，作用是指向下一個Entry。每當同一個index有新的結點（A）插入時，A成為此索引的頭結點，然後A->NEXT=舊頭結點。
