98
Hash算法，及HashMap使用
為什麼要Hash？
哈希表是基於數組實現的，哈希算法就是如何將鍵值（key）轉換成數組小標的方法，哈希化可以提供非常高的操作（插入、刪除、查詢）效率，因為對有序數組的查詢，即使是二分查找也隻能做到O(logN)，因為哈希可以直接將要查詢的key轉化為數組小標，所以可以達到O(1)的時間級。
Hash算法：將key做hash後的值叫hashcode，hashcode的值範圍可能很大，Hash算法是將一個較大範圍的hashcode轉換為定長的區間的數值。一個好的hash算法應該使hashcode均勻分布在區間內。 但是難免還是會有不同的key會產生相同的hashcode，此為哈希衝突。
例如，要對公司100個雇員的信息做哈希存儲，要求以姓名作為鍵值，“frank” 的hashcode是3135416，如果直接用3135416做小標，意味著要用一個非常大的數組，顯然非常浪費。mod是最簡單，往往也是最有效的hash算法，3135416%100=16，這樣就可以用array[16]來存儲“frank”的信息了。
如何解決哈希衝突？
- 開放定址法
線性探測，二次探測，再哈希。
例如“leo”的hashcode是733616，用模100哈希算法後，其值也是16，因為array[16]已經被占用了，產生了“衝突”，那麼順序查看16的下個位置17，看array[17]是否可用，如果可以則存儲leo，否則繼續探測下個位置18，直到有空位為止。在查詢時，若一個key的哈希值為16，不能就簡單的返回array[16]，因為哈希值為16的可能是frank 或者 leo，所以還要比對key值。 - 鏈地址法
Java 的 HashMap就是用LinkedList解決hash衝突的。
參考：https://en.wikipedia.org/wiki/Hash_function
使用Java HashMap時，注意以下幾點：
1. HashMap不是線程安全的
不要在並發環境中使用HashMap，這樣會造成不可預期的後果，據sun的說法，在擴容時，會引起鏈表的閉環，在get元素時，就會無限循環，後果是cpu100%。
如果Concurrent is a must，請用Map m = Collections.synchronizedMap(new HashMap(...))
2.如果數據大小是固定的，那麼最好給HashMap設定一個合理的容量值
因為HashMap的默認容量是Capacity(16) * LoadFactor(0.75) = 12，如果你的HashMap是用來裝載1萬條數據的，那麼HashMap會不斷的擴容（resize），而每次擴容都會對原有數據做重新排列，非常的time-consuming，所以應該在初始化HashMap的時候用New HashMap(15000)，負載因子（loadFactor）用默認的0.75就好了。
More about loadFactor：這個loadFactor有做什麼用得呢？ 是用來減少collision的，試想一下， 是不是越接近滿載的時候，產生衝突的可能性越大呢，就像公交車上有16個座位，此時上來5個人，幾乎不會出現搶位子的情況，因為很空。假如又上來10個人，那麼15個人對16個座位，可能有些人覺得前麵座位比較好，就會產生衝突並問候對方的父母。現在規定這個16座的公交車隻允許載客12人，也就是負載因子是0.75，後麵來的人用另一輛空車裝載，這樣就可以有效的解決衝突。
3.成為HashMap的key的條件
HashMap是用一個數組Entry[ ]來存儲相應的Entry<K, V>的，所以在put(K, V)操作時，首先檢查Key的hashCode，看該Entry在數組中是否已經存在，若不存在，加到數組中，否則，會再將K.equals()於現有已存在數組中得Entry的鏈表（linked list）中的K進行比較，若有相同的，將其替換， 若沒有，將該Entry置於鏈表的頭部。
在get( )操作是，是先查看HashCode，再比較equals，兩者皆匹配的時候，才會返回Value。
所以這是為什麼要作為HashMap的key要override hashCode 和 equals的原因。
參考：https://www.iteye.com/topic/754887
4. HashMap 和 HashTable, HashSet的比較
1.Hashtable是Dictionary的子類，HashMap是Map接口的一個實現類；
2.Hashtable 中的方法是同步的，而HashMap中的方法在缺省情況下是非同步的。3.HashMap 允許key和value為null，HashTable則不允許
4. HashTable直接用對象的hashCode，HashMap有自己的hash算法
5. HashSet不是Map是Set，其與ArrayList的區別是HashSet不允許重複元素，可通過HashMap.keySet()獲得HashMap中key的set
發現一個對hash深入研究的博文，以及用hash做Top K 問題的solution （有1000萬條（查詢串）記錄，找出裏麵top 10出現次數最多的查詢串的方法）
https://blog.csdn.net/v_july_v/article/details/6256463
最後更新：2017-04-02 06:52:03