哈希表數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)中的哈希表查找

來源：整理時(shí)間：2023-08-18 23:40:08 編輯：智能門戶手機(jī)版

本文目錄一覽

1，數(shù)據(jù)結(jié)構(gòu)中的哈希表查找
2，什么是哈希表
3，數(shù)據(jù)結(jié)構(gòu)哈希查找
4，誰能講解一點(diǎn)哈希表數(shù)據(jù)結(jié)構(gòu)的知識(shí)
5，哈希表是一種算法還是一種數(shù)據(jù)結(jié)構(gòu)呢
6，什么是哈希表啊

1，數(shù)據(jù)結(jié)構(gòu)中的哈希表查找

在表中要插入一個(gè)元素,如果要插入的位置有元素存在,就要查找下一個(gè)位置,直到找到可以插入元素的位置,計(jì)算表中每個(gè)位置的查找次數(shù)的和除以元素個(gè)數(shù)即可.

數(shù)據(jù)結(jié)構(gòu)中的哈希表查找

2，什么是哈希表

散列表，用代碼來表示：a:array[0..max]of longint; 可以很方便的進(jìn)行數(shù)據(jù)查找以及存儲(chǔ)，速度快，簡潔，但是占用空間較大

給你個(gè)地址你自己看吧很詳細(xì)的 http://baike.baidu.com/view/273836.htm

什么是哈希表

3，數(shù)據(jù)結(jié)構(gòu)哈希查找

如果用JAVA來實(shí)現(xiàn)的話就很方便了，JAVA提供了HashSet類。使用HashSet的例子。 import java.util.*; class HashSetDemo{ public static void main(String args[]){ // create a hash set HashSet hs = new HashSet(); // add elements to the hash set hs.add("B"); hs.add("A"); hs.add("D"); hs.add("E"); hs.add("C"); hs.add("F"); System.out.println(hs); } } 程序運(yùn)行結(jié)果如下： [D, A, F, C, B, E] 元素沒有以排序的順序存放，且具體的輸出可能變化。

數(shù)據(jù)結(jié)構(gòu)哈希查找

4，誰能講解一點(diǎn)哈希表數(shù)據(jù)結(jié)構(gòu)的知識(shí)

基本原理: 我們使用一個(gè)下標(biāo)范圍比較大的數(shù)組(可以把地址比做數(shù)組)來存儲(chǔ)元素(把要存儲(chǔ)的數(shù)據(jù)比做元素)。可以設(shè)計(jì)一個(gè)函數(shù)（哈希函數(shù)，也叫做散列函數(shù)），使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)）相對應(yīng)，于是用這個(gè)數(shù)組單元來存儲(chǔ)這個(gè)元素. 構(gòu)造函數(shù)的方法 a) 除余法：選擇一個(gè)適當(dāng)?shù)恼麛?shù) p ，令 h(k ) = k mod p 這里， p 如果選取的是比較大的素?cái)?shù)，效果比較好。而且此法非常容易實(shí)現(xiàn)，因此是最常用的方法。 b) 數(shù)字選擇法：如果關(guān)鍵字的位數(shù)比較多，超過長整型范圍而無法直接運(yùn)算，可以選擇其中數(shù)字分布比較均勻的若干位，所組成的新的值作為關(guān)鍵字或者直接作為函數(shù)值。沖突處理(線性重散列法) 線性重新散列技術(shù)易于實(shí)現(xiàn)且可以較好的達(dá)到目的。令數(shù)組元素個(gè)數(shù)為 S ，則當(dāng) h(k) 已經(jīng)存儲(chǔ)了元素的時(shí)候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲(chǔ)單元為止（或者從頭到尾掃描一圈仍未發(fā)現(xiàn)空單元，這就是哈希表已經(jīng)滿了，發(fā)生了錯(cuò)誤。當(dāng)然這是可以通過擴(kuò)大數(shù)組范圍避免的）。這里只介紹一部分,還有一些,請參考相關(guān)書籍.

5，哈希表是一種算法還是一種數(shù)據(jù)結(jié)構(gòu)呢

對于動(dòng)態(tài)查找表而言，1) 表長不確定；2)在設(shè)計(jì)查找表時(shí)，只知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵字。因此，一般情況需建立一個(gè)函數(shù)關(guān)系，以f(key)作為關(guān)鍵字為key的錄在表中的位置，通常稱這個(gè)函數(shù)f(key)為哈希函數(shù)。(注意：這個(gè)函數(shù)并不一定是數(shù)學(xué)函數(shù)) 哈希函數(shù)是一個(gè)映象，即：將關(guān)鍵字的集合映射到某個(gè)地址集合上，它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍即可。現(xiàn)實(shí)中哈希函數(shù)是需要構(gòu)造的，并且構(gòu)造的好才能使用的好。用途：加密，解決沖突問題。。。。用途很廣，比特精靈中就使用了哈希函數(shù)，你可以自己看看。具體可以學(xué)習(xí)一下數(shù)據(jù)結(jié)構(gòu)和算法的書。

哈希算法并不是一個(gè)特定的算法而是一類算法的統(tǒng)稱。哈希算法也叫散列算法,一般來說滿足這樣的關(guān)系:f(data)=key,輸入任意長度的data數(shù)據(jù),經(jīng)過哈希算法處理后輸出一個(gè)定長的數(shù)據(jù)key。同時(shí)這個(gè)過程是不可逆的,無法由key逆推出data。如果是一個(gè)data數(shù)據(jù)集,經(jīng)過哈希算法處理后得到key的數(shù)據(jù)集,然后將keys與原始數(shù)據(jù)進(jìn)行一一映射就得到了一個(gè)哈希表。一般來說哈希表m符合m[key]=data這種形式。哈希表的好處是當(dāng)原始數(shù)據(jù)較大時(shí),我們可以用哈希算法處理得到定長的哈希值key,那么這個(gè)key相對原始數(shù)據(jù)要小得多。我們就可以用這個(gè)較小的數(shù)據(jù)集來做索引,達(dá)到快速查找的目的。稍微想一下就可以發(fā)現(xiàn),既然輸入數(shù)據(jù)不定長,而輸出的哈希值卻是固定長度的,這意味著哈希值是一個(gè)有限集合,而輸入數(shù)據(jù)則可以是無窮多個(gè)。那么建立一對一關(guān)系明顯是不現(xiàn)實(shí)的。所以"碰撞"(不同的輸入數(shù)據(jù)對應(yīng)了相同的哈希值)是必然會(huì)發(fā)生的,所以一個(gè)成熟的哈希算法會(huì)有較好的抗沖突性。同時(shí)在實(shí)現(xiàn)哈希表的結(jié)構(gòu)時(shí)也要考慮到哈希沖突的問題。密碼上常用的md5,sha都是哈希算法,因?yàn)閗ey的長度(相對大家的密碼來說)較大所以碰撞空間較大,有比較好的抗碰撞性,所以常常用作密碼校驗(yàn)。麻煩采納，謝謝!

當(dāng)然是數(shù)據(jù)結(jié)構(gòu)

6，什么是哈希表啊

哈希表是用于查找的一種表，它是根據(jù)某一函數(shù)H(key)=key,來確定某一元素的存儲(chǔ)位置，構(gòu)造哈希表的方法，一般有：或是它的線性函數(shù)，來構(gòu)造；還有除留余數(shù)法等等；構(gòu)造這種表的過程叫哈希造表，或散列，得到的地址，稱為哈系地址或散列地址。

簡單說就是按照哈希函數(shù)關(guān)系建立的表具體內(nèi)容請參考數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)~ 下面引用一些別的地方 1 基本原理我們使用一個(gè)下標(biāo)范圍比較大的數(shù)組來存儲(chǔ)元素。可以設(shè)計(jì)一個(gè)函數(shù)（哈希函數(shù)），使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)）相對應(yīng)，于是用這個(gè)數(shù)組單元來存儲(chǔ)這個(gè)元素；也可以簡單的理解為，按照關(guān)鍵字為每一個(gè)元素"分類"，然后將這個(gè)元素存儲(chǔ)在相應(yīng)"類"所對應(yīng)的地方。但是，不能夠保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對應(yīng)的，因此極有可能出現(xiàn)對于不同的元素，卻計(jì)算出了相同的函數(shù)值，這樣就產(chǎn)生了"沖突"，換句話說，就是把不同的元素分在了相同的"類"之中。后面我們將看到一種解決"沖突"的簡便做法。總的來說，"直接定址"與"解決沖突"是哈希表的兩大特點(diǎn)。 2 函數(shù)構(gòu)造構(gòu)造函數(shù)的常用方法（下面為了敘述簡潔，設(shè) h(k) 表示關(guān)鍵字為 k 的元素所對應(yīng)的函數(shù)值）： a) 除余法：選擇一個(gè)適當(dāng)?shù)恼麛?shù) p ，令 h(k ) = k mod p 這里， p 如果選取的是比較大的素?cái)?shù)，效果比較好。而且此法非常容易實(shí)現(xiàn)，因此是最常用的方法。 b) 數(shù)字選擇法：如果關(guān)鍵字的位數(shù)比較多，超過長整型范圍而無法直接運(yùn)算，可以選擇其中數(shù)字分布比較均勻的若干位，所組成的新的值作為關(guān)鍵字或者直接作為函數(shù)值。 3 沖突處理線性重新散列技術(shù)易于實(shí)現(xiàn)且可以較好的達(dá)到目的。令數(shù)組元素個(gè)數(shù)為 S ，則當(dāng) h(k) 已經(jīng)存儲(chǔ)了元素的時(shí)候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲(chǔ)單元為止（或者從頭到尾掃描一圈仍未發(fā)現(xiàn)空單元，這就是哈希表已經(jīng)滿了，發(fā)生了錯(cuò)誤。當(dāng)然這是可以通過擴(kuò)大數(shù)組范圍避免的）。 4 支持運(yùn)算哈希表支持的運(yùn)算主要有：初始化(makenull)、哈希函數(shù)值的運(yùn)算(h(x))、插入元素(insert)、查找元素(member)。設(shè)插入的元素的關(guān)鍵字為 x ，A 為存儲(chǔ)的數(shù)組。初始化比較容易，例如 const empty=maxlongint; // 用非常大的整數(shù)代表這個(gè)位置沒有存儲(chǔ)元素 p=9997; // 表的大小 procedure makenull; var i:integer; begin for i:=0 to p-1 do A[i]:=empty; End; 哈希函數(shù)值的運(yùn)算根據(jù)函數(shù)的不同而變化，例如除余法的一個(gè)例子： function h(x:longint):Integer; begin h:= x mod p; end; 我們注意到，插入和查找首先都需要對這個(gè)元素定位，即如果這個(gè)元素若存在，它應(yīng)該存儲(chǔ)在什么位置，因此加入一個(gè)定位的函數(shù) locate function locate(x:longint):integer; var orig,i:integer; begin orig:=h(x); i:=0; while (ix)and(A[(orig+i)mod S]<>empty) do inc(i); //當(dāng)這個(gè)循環(huán)停下來時(shí)，要么找到一個(gè)空的存儲(chǔ)單元，要么找到這個(gè)元 //素存儲(chǔ)的單元，要么表已經(jīng)滿了 locate:=(orig+i) mod S; end; 插入元素 procedure insert(x:longint); var posi:integer; begin posi:=locate(x); //定位函數(shù)的返回值 if A[posi]=empty then A[posi]:=x else error; //error 即為發(fā)生了錯(cuò)誤，當(dāng)然這是可以避免的 end; 查找元素是否已經(jīng)在表中 procedure member(x:longint):boolean; var posi:integer; begin posi:=locate(x); if A[posi]=x then member:=true else member:=false; end; 這些就是建立在哈希表上的常用基本運(yùn)算。

根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突方法將一組關(guān)鍵字映象到一個(gè)有限的地址區(qū)間上，并以關(guān)鍵字在地址區(qū)間中的象作為記錄在表中的存儲(chǔ)位置，這種表稱為哈希表或散列，所得存儲(chǔ)位置稱為哈希地址或散列地址。