一：概念
順序結(jié)構(gòu)以及平衡樹(shù)中，元素關(guān)鍵碼與其存儲(chǔ)位置之間沒(méi)有對(duì)應(yīng)的關(guān)系，因此在查找一個(gè)元素時(shí)，必須要經(jīng)過(guò)關(guān)鍵碼的多次比較。順序查找時(shí)間復(fù)雜度為O(N)，平衡樹(shù)中為樹(shù)的高度，即O(log_2 N)，搜索的效率取決于搜索過(guò)程中元素的比較次數(shù)。
理想的搜索方法：可以不經(jīng)過(guò)任何比較，一次直接從表中得到要搜索的元素。 如果構(gòu)造一種存儲(chǔ)結(jié)構(gòu)，通過(guò)某種函數(shù)使元素的存儲(chǔ)位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，那么在查找時(shí)通過(guò)該函數(shù)可以很快找到該元素。
當(dāng)向該結(jié)構(gòu)中：
插入元素
根據(jù)待插入元素的關(guān)鍵碼，以此函數(shù)計(jì)算出該元素的存儲(chǔ)位置并按此位置進(jìn)行存放。
搜索元素
對(duì)元素的關(guān)鍵碼進(jìn)行同樣的計(jì)算，把求得的函數(shù)值當(dāng)做元素的存儲(chǔ)位置，在結(jié)構(gòu)中按此位置取元素比較，若關(guān)鍵碼相等，則搜索成功。
該方式即為哈希(散列)方法，哈希方法中使用的轉(zhuǎn)換函數(shù)稱(chēng)為哈希(散列)函數(shù)，構(gòu)造出來(lái)的結(jié)構(gòu)稱(chēng)為哈希表(HashTable)(或者稱(chēng)散列表)
二： 沖突-概念
對(duì)于兩個(gè)數(shù)據(jù)元素的關(guān)鍵字K1!=K2，但有：Hash(K1) == Hash(K2)，即：不同關(guān)鍵碼通過(guò)相同哈希函數(shù)計(jì)算出相同的哈希地址，該種現(xiàn)象稱(chēng)為哈希沖突或哈希碰撞。
把具有不同關(guān)鍵碼而具有相同哈希地址的數(shù)據(jù)元素稱(chēng)為“同義詞”。
三：沖突-避免-設(shè)計(jì)哈希函數(shù)
引起哈希沖突的一個(gè)原因可能是：哈希函數(shù)設(shè)計(jì)不夠合理。 哈希函數(shù)設(shè)計(jì)原則：
1.哈希函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵碼，而如果散列表允許有m個(gè)地址時(shí)，其值域必須在0到m-1之間。
2.哈希函數(shù)計(jì)算出來(lái)的地址能均勻分布在整個(gè)空間中。
3.哈希函數(shù)應(yīng)該比較簡(jiǎn)單。
常見(jiàn)哈希函數(shù)有：

創(chuàng)新互聯(lián)建站-專(zhuān)業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性?xún)r(jià)比南靖網(wǎng)站開(kāi)發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式南靖網(wǎng)站制作公司更省心,省錢(qián),快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋南靖地區(qū)。費(fèi)用合理售后完善，10多年實(shí)體公司更值得信賴(lài)。

1. 直接定制法--(常用)
   取關(guān)鍵字的某個(gè)線性函數(shù)為散列地址：Hash（Key）= A*Key + B
   優(yōu)點(diǎn)：簡(jiǎn)單、均勻
   缺點(diǎn)：需要事先知道關(guān)鍵字的分布情況
   使用場(chǎng)景：適合查找比較小且連續(xù)的情況

2. 除留余數(shù)法--(常用)
   設(shè)散列表中允許的地址數(shù)為m，取一個(gè)不大于m，但最接近或者等于m的質(zhì)數(shù)p作為除數(shù)，按照哈希函數(shù)：Hash(key) = key% p(p<=m),將關(guān)鍵碼轉(zhuǎn)換成哈希地址。
3. 平方取中法--(了解) 折疊法--(了解)隨機(jī)數(shù)法--(了解)數(shù)學(xué)分析法--(了解)。
   四：沖突-避免-設(shè)計(jì)哈希函數(shù)

五： 沖突-解決
解決哈希沖突兩種常見(jiàn)的方法是：閉散列（線性探測(cè)法）和開(kāi)散列（拉鏈桶）
六：（1）沖突-解決-閉散列
閉散列：也叫開(kāi)放定址法，當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表未被裝滿，說(shuō)明在哈希表中必然還有空位置，那么可以把key存放到?jīng)_突位置中的“下一個(gè)” 空位置中去。那如何尋找下一個(gè)空位置呢？
線性探測(cè)：從發(fā)生沖突的位置開(kāi)始，依次向后探測(cè)，直到尋找到下一個(gè)空位置為止。
插入：
通過(guò)哈希函數(shù)獲取待插入元素在哈希表中的位置，如果該位置中沒(méi)有元素則直接插入新元素，如果該位置中有元素發(fā)生哈希沖突，使用線性探測(cè)找到下一個(gè)空位置，插入新元素。
采用閉散列處理哈希沖突時(shí)，不能隨便物理刪除哈希表中已有的元素，若直接刪除元素會(huì)影響其他元素的搜索。比如刪除元素4，如果直接刪除掉，44查找起來(lái)可能會(huì)受影響。因此線性探測(cè)采用標(biāo)記的偽刪除法來(lái)刪除一個(gè)元素。
但是：閉散列大的缺陷就是空間利用率比較低，這也是哈希的缺陷。

六：（2）沖突-解決-開(kāi)散列/哈希桶（重點(diǎn)）
開(kāi)散列法又叫鏈地址法(開(kāi)鏈法)，首先對(duì)關(guān)鍵碼集合用散列函數(shù)計(jì)算散列地址，具有相同地址的關(guān)鍵碼歸于同一子集合，每一個(gè)子集合稱(chēng)為一個(gè)桶，各個(gè)桶中的元素通過(guò)一個(gè)單鏈表鏈接起來(lái)，各鏈表的頭結(jié)點(diǎn)存儲(chǔ)在哈希表中。

從上圖可以看出，開(kāi)散列中每個(gè)桶中放的都是發(fā)生哈希沖突的元素。
開(kāi)散列，可以認(rèn)為是把一個(gè)在大集合中的搜索問(wèn)題轉(zhuǎn)化為在小集合中做搜索了。

七：性能分析
雖然哈希表一直在和沖突做斗爭(zhēng)，但在實(shí)際使用過(guò)程中，我們認(rèn)為哈希表的沖突率是不高的，沖突個(gè)數(shù)是可控的，也就是每個(gè)桶中的鏈表的長(zhǎng)度是一個(gè)常數(shù)，所以，通常意義下，我們認(rèn)為哈希表的插入/刪除/查找時(shí)間復(fù)雜度是O(1) 。
八：和 java 類(lèi)集的關(guān)系

1. HashMap 和 HashSet 即 java 中利用哈希表實(shí)現(xiàn)的 Map 和 Set
2. java 中使用的是哈希桶方式解決沖突的
3. java 會(huì)在沖突鏈表長(zhǎng)度大于一定閾值后，將鏈表轉(zhuǎn)變?yōu)樗阉鳂?shù)（紅黑樹(shù)）
4. java 中計(jì)算哈希值實(shí)際上是調(diào)用的類(lèi)的 hashCode 方法，進(jìn)行 key 的相等性比較是調(diào)用 key 的 equals 方法。所以如果要用自定義類(lèi)作為 HashMap 的 key 或者 HashSet 的值，必須覆寫(xiě) hashCode 和 equals 方 法，而且要做到 equals 相等的對(duì)象，hashCode 一定是一致的。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站欄目：Java中的HashTable哈希表是什么？-創(chuàng)新互聯(lián)
本文網(wǎng)址：http://jinyejixie.com/article44/psjee.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、網(wǎng)站策劃、ChatGPT、響應(yīng)式網(wǎng)站、電子商務(wù)、云服務(wù)器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)