久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

標題: hash [打印本頁]

作者: 51黑tt 時間: 2016-3-5 23:41
標題: hash
HashMap、Map等是很多公司面試、筆試的時候�？嫉念}目，也是實際開發中經常用到的數據結構，必須好好掌握。因此我從《J2EE開發全程實錄》中摘取了下面的片段，希望對同學們有幫助。學習時請對照著《數據結構》這門課中“散列”相關的章節復習。

在實際問題中，按照給定的值進行數據查詢是經常遇到的，比如，在電話號碼簿中查詢某個人的電話號碼；在圖書館中按照ISBN 編號查找某本書的位置；在地圖中按照坐標查找某個地點的地名等等。為此，人們創造了一種能夠根據記錄的關鍵碼 ( 也就是用以標識數據在記錄中的存放位置的數據項 ) 方便的檢索到對應的記錄信息的數據結構，這就是字典 ( Dictionary ) 。

2.2.1字典的定義

我們都使用過字典，如英漢字典、成語字典，圖書的檢索目錄、電話簿等也可以看作廣義上的字典。在計算機科學中，把字典也當成一種數據結構。

我們把字典定義為“鍵- 值對” (Key-Value Pair) 的集合。根據不同的問題，我們為名字和值賦予不同的含義，比如，在英漢字典中，英文單詞是名字，此單詞的中文解釋條目是值；在電話簿中，人名是名字，此人名對應的電話號碼是值。

字典最基本的操作包括：find( 查找 ) 、 add( 插入 ) 、 remove( 刪除 ) ，分別用來從字典中檢索數據、插入數據和刪除數據。在實際存儲中，我們將“鍵 - 值對”存儲于記錄中，通過鍵 ( 也就是“鍵 - 值對”中的名字 ) 來標識該“鍵 - 值對”�！版I - 值對”的存放位置和其鍵之間的對應關系用一個二元組表示： ( 鍵 , 值的位置 ) 。

從字典中查找“鍵- 值對”的最簡單方法就是使用數組存儲，然后在查找的時候遍歷此數組，當遍歷到和被查找的“鍵 - 值對”的名字相同項的時候，這個“鍵 - 值對”就被找到了。這種最樸實的方式肯定是不能滿足實際要求的，因此人們發明了一種檢索效率非常高的組織字典數據的方法，即哈希表結構。

2.2.2哈希表與哈希方法

哈希方法在“鍵- 值對”的存儲位置與它的鍵之間建立一個確定的對應函數關系 hash() ，使得每一個鍵與結構中的一個唯一的存儲位置相對應：

存儲位置=hash( 鍵 )

在搜索時，首先對鍵進行hash 運算，把求得的值當做“鍵 - 值對”的存儲位置，在結構中按照此位置取“鍵 - 值對”進行比較，若鍵相等，則表示搜索成功。在存儲“鍵 - 值對”的時候，依照相同的 hash 函數計算存儲位置，并按此位置存放，這種方法就叫做哈希方法，也叫做散列方法。在哈希方法中使用的轉換函數 hash 被稱作哈希函數 ( 或者散列函數 ) 。按照此中算法構造出來的表叫做哈希表 ( 或者散列表 ) 。

哈希函數建立了從“鍵- 值對”到哈希表地址集合的一個映射，有了哈希函數，我們就可以根據鍵來確定“鍵 - 值對”在哈希表中的位置的地址。使用這種方法由于不必進行多次鍵的比較，所以其搜索速度非常快，很多系統都使用這種方法進行數據的組織和檢索。

舉一個例子，有一組“鍵值對”：<5, ” tom ” >、 <8, ” Jane ” >、 <12, ” Bit ” >、 <17, ” Lily ” >、 <20, ” sunny ” >，我們按照如下哈希函數對鍵進行計算 :hash(x)=x%17+3 ，得出如下結果： hash(5)=8 、 hash(8)=11 、 hash(12)=15 、 hash(17)=3 、 hash(20)=6 。我們把 <5, ” tom ” >、 <8, ” Jane ” >、 <12, ” Bit ” >、 <17, ” Lily ” >、 <20, ” sunny ” >分別放到地址為 8 、 11 、 15 、 3 、 6 的位置上。當要檢索 17 對應的值的時候，只要首先計算 17 的哈希值為 3 ，然后到地址為 3 的地方去取數據就可以找到 17 對應的數據是“ Lily ”了，可見檢索速度是非�？斓�。

2.2.3沖突與沖突的解決

通常鍵的取值范圍比哈希表地址集合大很多，因此有可能經過同一哈希函數的計算，把不同的鍵映射到了同一個地址上面，這就叫沖突。比如，有一組“鍵- 值對”，其鍵分別為 12361 、 7251 、 3309 、 30976 ，采用的哈希函數是：

public static int hash(int key)

{

return key%73+13420;

}

則將會得到hash(12361)=hash(7251)=hash(3309)=hash(30976)=13444 ，即不同的鍵通過哈希函數對應到了同一個地址，我們稱這種哈希計算結果相同的不同鍵為同義詞。

如果“鍵- 值對”在加入哈希表的時候產生了沖突，就必須找另外一個地方來存放它，沖突太多會降低數據插入和搜索的效率，因此希望能找到一個不容易產生沖突的函數，即構造一個地址分布比較均勻的哈希函數。常用的哈希函數包括：直接定址法、數字分析法、除留余數法、乘留余數法、平方取中法、折疊法等。應該根據實際工作中關鍵碼的特點選用適當的方法。

雖然采用合適的哈希方法能夠降低沖突的概率，但是沖突仍然是不可避免的，處理沖突的最常用方法就是“桶”算法：假設哈希表有m 個地址，就將其改為 m 個“桶”，其桶號與哈希地址一一對應，每個桶都用來存放互為同義詞的鍵，也就是如果兩個不同的鍵用哈希函數計算得到了同一個哈希地址，就將它們放到同一個桶中，檢索的時候在桶內進行順序檢索。

2.2.4Java中的 Map 接口

字典數據結構如此重要，以至于實際開發中經常需要使用它們。JDK 中提供了相關的類供我們使用，從而避免了自己開發字典類的麻煩。

在以前版本的JDK 中，最常使用的字典類就是 Dictionary 抽象類及其實現類 Hashtable ，不過在新版本的JDK 中不推薦讀者使用 Dictionary 抽象類而是使用Map 接口，并且由于 Dictionary 的實現類 Hashtable 也實現了Map 接口，所以我們沒有理由不使用 Map 接口。

Map接口有很多實現類，比如 HashMap 、 TreeMap 、 Hashtable 、 SortedMap 等，在第三方開源包中也有提供了更多功能的實現類，比如Apache-Commons 項目中的 LRUMap 。最常用的就是 HashMap 和 Hashtable ，它們最大的區別就是 Hashtable 是線程安全的，而 HashMap 則不是線程安全的，在使用的時候必須進行同步。由于JDK 中的工具類 java.util . Collections 提供了一個 synchronizedMap 方法，可以將非線程安全的Map 接口變量采用裝飾者模式改造成線程安全的，因此使用 HashMap 的場合更多一些，后邊的論述也將以 HashMap 為主。

2.3HashMap

HashMap是 Map 接口的實現類中最常用的一個，熟練的掌握這個類的使用將會提高解決問題的速度。

HashMap的主要方法

int size() ：得到Map中“鍵-值對”的數量

boolean isEmpty() ：Map是否是空的，也就是是否不含有任何“鍵-值對”

boolean containsKey(Object key) ：Map中是否含有以key為鍵的“鍵-值對”

boolean containsValue(Object value) ：Map中是否含有以 value 為值的“鍵-值對”

Object get(Object key) ：從Map中得到以key為鍵的值，如果Map中不含有以key為鍵的“鍵-值對”則返回null

Object put(Object key, Object value) ：向Map中存儲以key為鍵、value為值的“鍵-值對”

Object remove(Object key) :從Map中移除以key為鍵的“鍵-值對”

void putAll(Map t) ：將另一個Map中的所有“鍵-值對”導入到此Map中

void clear() ：清除所有“鍵-值對”

Set keySet() ：得到所有的鍵

Collection values() ：得到所有的值

Set entrySet() ：得到所有的“鍵-值對”，Set中的類型是Map.Entry

歡迎光臨 (http://www.zg4o1577.cn/bbs/)