❶ 有關數據結構哈希表的問題
Hash，一般翻譯做"散列"，也有直接音譯為"哈希"的，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列演算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。
簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
hashing定義了一種將字元組成的字元串轉換為固定長度(一般是更短長度)的數值或索引值的方法，稱為散列法，也叫哈希法。由於通過更短的哈希值比用原始值進行資料庫搜索更快，這種方法一般用來在資料庫中建立索引並進行搜索，同時還用在各種解密演算法中。
設所有可能出現的關鍵字集合記為u(簡稱全集)。實際發生(即實際存儲)的關鍵字集合記為k（|k|比|u|小得多）。|k|是集合k中元素的個數。
散列方法是使用函數hash將u映射到表t[0..m-1]的下標上（m=o(|u|)）。這樣以u中關鍵字為自變數，以h為函數的運算結果就是相應結點的存儲地址。從而達到在o(1)時間內就可完成查找。
其中：
① hash：u→{0，1，2，…，m-1} ，通常稱h為散列函數(hash function)。散列函數h的作用是壓縮待處理的下標范圍，使待處理的|u|個值減少到m個值，從而降低空間開銷。
② t為散列表(hash table)。
③ hash(ki)(ki∈u)是關鍵字為ki結點存儲地址(亦稱散列值或散列地址)。
④ 將結點按其關鍵字的散列地址存儲到散列表中的過程稱為散列(hashing).
比如：有一組數據包括用戶名字、電話、住址等，為了快速的檢索，我們可以利用名字作為關鍵碼，hash規則就是把名字中每一個字的拼音的第一個字母拿出來，把該字母在26個字母中的順序值取出來加在一塊作為改記錄的地址。比如張三，就是z+s＝26+19＝45。就是把張三存在地址為45處。
但是這樣存在一個問題，比如假如有個用戶名字叫做：周四，那麼計算它的地址時也是z+s＝45，這樣它與張三就有相同的地址，這就是沖突，也叫作碰撞！
沖突：兩個不同的關鍵字，由於散列函數值相同，因而被映射到同一表位置上。該現象稱為沖突(collision)或碰撞。發生沖突的兩個關鍵字稱為該散列函數的同義詞(synonym)。
沖突基本上不可避免的，除非數據很少，我們只能採取措施盡量避免沖突，或者尋找解決沖突的辦法。影響沖突的因素
沖突的頻繁程度除了與h相關外，還與表的填滿程度相關。
設m和n分別表示表長和表中填人的結點數，則將α=n/m定義為散列表的裝填因子(load factor)。α越大，表越滿，沖突的機會也越大。通常取α≤1。
散列函數的構造方法：
1、散列函數的選擇有兩條標准：簡單和均勻。
簡單指散列函數的計算簡單快速；
均勻指對於關鍵字集合中的任一關鍵字，散列函數能以等概率將其映射到表空間的任何一個位置上。也就是說，散列函數能將子集k隨機均勻地分布在表的地址集{0，1，…，m-1}上，以使沖突最小化。
2、常用散列函數
（1）直接定址法：比如在一個0～100歲的年齡統計表，我們就可以把年齡作為地址。
（2）平方取中法
具體方法：先通過求關鍵字的平方值擴大相近數的差別，然後根據表長度取中間的幾位數作為散列函數值。又因為一個乘積的中間幾位數和乘數的每一位都相關，所以由此產生的散列地址較為均勻。
（3）除留余數法
取關鍵字被某個不大於哈希表表長m的數p除後所得余數為哈希地址。該方法的關鍵是選取m。選取的m應使得散列函數值盡可能與關鍵字的各位相關。m最好為素數（4）隨機數法
選擇一個隨機函數，取關鍵字的隨機函數值為它的散列地址，即
h(key)=random(key)
其中random為偽隨機函數，但要保證函數值是在0到m-1之間。
處理沖突的方法：
1、開放定址法
hi=(h(key)+di) mod m i=1,2,...,k(k<=m-1)
其中m為表長，di為增量序列
如果di值可能為1,2,3,...m-1，稱線性探測再散列。
如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
稱二次探測再散列。
如果di取值可能為偽隨機數列。稱偽隨機探測再散列。開放地址法堆裝填因子的要求
開放定址法要求散列表的裝填因子α≤l，實用中取α為0.5到0.9之間的某個值為宜。
②二次探查法(quadratic probing)
二次探查法的探查序列是：
hi=(h(key)+i*i)％m 0≤i≤m-1 //即di=i2
即探查序列為d=h(key)，d+12，d+22，…，等。
該方法的缺陷是不易探查到整個散列空間。
③雙重散列法(double hashing)
該方法是開放定址法中最好的方法之一，它的探查序列是：
hi=(h(key)+i*h1(key))％m 0≤i≤m-1 //即di=i*h1(key)
即探查序列為：
d=h(key)，(d+h1(key))％m，(d+2h1(key))％m，…，等。
該方法使用了兩個散列函數h(key)和h1(key)，故也稱為雙散列函數探查法。
2、拉鏈法
拉鏈法解決沖突的方法
拉鏈法解決沖突的做法是：將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組t[0..m-1]。凡是散列地址為i的結點，均插入到以t為頭指針的單鏈表中。t中各分量的初值均應為空指針。在拉鏈法中，裝填因子α可以大於1，但一般均取α≤1。
3、建立一個公共溢出區
假設哈希函數的值域為[0,m-1],則設向量hashtable[0..m-1]為基本表，另外設立存儲空間向量overtable[0..v]用以存儲發生沖突的記錄。
性能分析
插入和刪除的時間均取決於查找，故下面只分析查找操作的時間性能。
雖然散列表在關鍵字和存儲位置之間建立了對應關系，理想情況是無須關鍵字的比較就可找到待查關鍵字。但是由於沖突的存在，散列表的查找過程仍是一個和關鍵字比較的過程，不過散列表的平均查找長度比順序查找、二分查找等完全依賴於關鍵字比較的查找要小得多。
（1）查找成功的asl
散列表上的查找優於順序查找和二分查找。
（2） 查找不成功的asl
對於不成功的查找，順序查找和二分查找所需進行的關鍵字比較次數僅取決於表長，而散列查找所需進行的關鍵字比較次數和待查結點有關。因此，在等概率情況下，也可將散列表在查找不成功時的平均查找長度，定義為查找不成功時對關鍵字需要執行的平均比較次數。
注意：
①由同一個散列函數、不同的解決沖突方法構造的散列表，其平均查找長度是不相同的。
②散列表的平均查找長度不是結點個數n的函數，而是裝填因子α的函數。因此在設計散列表時可選擇α以控制散列表的平均查找長度。
③ α的取值
α越小，產生沖突的機會就小，但α過小，空間的浪費就過多。只要α選擇合適，散列表上的平均查找長度就是一個常數，即散列表上查找的平均時間為o(1)。
④ 散列法與其他查找方法的區別
除散列法外，其他查找方法有共同特徵為：均是建立在比較關鍵字的基礎上。其中順序查找是對無序集合的查找，每次關鍵字的比較結果為"="或"!="兩種可能，其平均時間為o(n)；其餘的查找均是對有序集合的查找，每次關鍵字的比較有"="、"<"和">"三種可能，且每次比較後均能縮小下次的查找范圍，故查找速度更快，其平均時間為o(lgn)。而散列法是根據關鍵字直接求出地址的查找方法，其查找的期望時間為o(1)。
例子：例子：選取哈希函數h(k)=(3k)%11,用線性探測再散列法處理沖突。
試在0～10的散列地址空間中，對關鍵序列22,41,53,46,30,13,01,67構造哈希表，並求等概率情況下查找不成功的平均查找長度asl。
❷ 關鍵字序列構造哈希表，並計算查找成功的平均查找長度ASL。是數據結構哪部分的知識
* 若結構中存在關鍵字和K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系f為散列函數(Hash function)，按這個思想建立的表為散列表。 * 對不同的關鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現象稱沖突。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。綜上所述，根據散列函數H(key)和處理沖突的方法將一組關鍵字映象到一個有限的連續的地址集(區間)上，並以關鍵字在地址集中的「象」 作為記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。 * 若對於關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為均勻散列函數(Uniform Hash function)，這就是使關鍵字經過散列函數得到一個「隨機的地址」，從而減少沖突。
❸ 對以下關鍵字序列建立哈希表
因為元素個數等於12,要求的填充率為0.8,所以表容量等於12/0.8=15.哈希函數通常採用除留余數法即取模數法,則哈希函數為H = key mod p,p應該為小於15且大於12的素數,由此得知p為13.而如果發生沖突再哈希時應該對表容量取模,增量序列則為1 -1 4 -4 9 -9.,所以構造的哈希表應如下:
0:26 1:^ 2:55 3:16 4:29 5:24 6:45 7:58 8:^ 9:36 10:49 11:37 12:50 13:38 14:^
ASL=(1+3+1+2+4+1+2+3+1+1+2+2)/12=23/12=1.9
❹ 數據結構表,字序列構造哈希表,
解：
Hi=(H(key)+di)
Mod
m,
i=1,2,3...,k(k<=m-1)
m為哈希表長，di=1,2,3,4,...m-1，
這里m=19,線性探測再散列是增量序列di=1,2,3,...,m-1
19%13=6，01%13=1，23%13=10，14%13=1，55%13=3，20%13=7
未出現沖突
處理84時，84%13=6，但6單元已佔用，出現沖突，調用沖突處理函數H1=(H(84)+1)
Mod
19=7，但7單元又被佔用，再次調用沖突處理函數得H2=(H(84)+2)
Mod
19=8,未沖突。
以下就不一一列舉了，下面把我算得的答案貼一下，可能有誤，歡迎指正！
表格橫著不好對齊我就豎著放吧
地址單元
關鍵字
0
01
1
14
2
27
3
55
4
68
5
6
19
7
20
8
84
9
10
23
11
11
12
10
13
77
14
15
16
17
18
其實線性探測再散列比較特殊，就是查找當前沖突單元往下第一個空閑地址單元，不用算直接用眼睛掃一下就知道下一個應放哪
希望我的解答有助於你理解~
❺ 一組關鍵字序列為(27,17,9,19,16,43,53,8,63),用哈希函數H(key)=key MOD 8和鏈地
27 mod 8 = 3, 17 mod 8 = 1, 9 mod 8 = 1, 19 mod 8 = 3, 16 mod 8 = 0, 43 mod 8 = 3, 53 mod 8 = 5, 8 mod 8 = 0, 63 mod 8 = 7，於是鏈地址法解決沖突的哈希表為：
後面的沖突的關鍵字一般插入在鏈表的表頭
❻ 小益根據如下的huffman樹
A:10B:001C:11D:0001E:0110F:0111G:010H:0000
第二題：||12|100|25||16|17|18|8|40|7
012345678910
❼ 數據結構習題
將以上九數字存在十二個空間中，增充因子為:9/12=0.75,由於哈希表的均勻特性，可以選key為11這個的一個素數為關鍵碼值。也就是說將其中的鍵與11求余，余數放在對應的空間中，若是已經存在，則直接向後探測，放入到一個不存在的空間中即可。
int[] hashtable = new int[12];
int hashkey = 11;
//hashtable就是你要定義的哈表，我用C#表示一下
int[] keys = new int[]{100,90,120,60,78,35,42,21,15};
setHash(keys);
//存儲哈希表
bool result = searchHash(100);
//尋找hash表中是否存在100的鍵值
//查找的原理是，打到該鍵應該在哈希表存儲的位置，如果不在，則一直向後查找，直找到第一個空位置時即立即停止，因為若是存放時那麼這里有一個空位置肯定要存放在這里的，否則就以查找到後報出存在的結果！
///該函數可以實現存儲，將其中的數組按與11取余的情況存放在其中！如果該位置被佔用時即尋找下一位置，直到尋找到空位置存入即可！
publci void setHash(int[] key)
{
foreach(int keyitem in key)
{
int sint = keyitem %hashkey;
int i =0;
while(hashtable[sint+i] != null)
{
i++;
}
hashtable[sint+i] = keyitem;
}
///該函數可以對特定鍵值進行查詢，查詢到即返回真，否則返回假
public bool searchHash(int key)
{
bool search = false;
int sint = key%hashkey;
int i = sint;
while(hashtable[i] != null)
{
if(i>hashtable.length)
i = 0;
if(hashtable[i] == key)
{
search = true;
break;
}
i++;
}
return seach;
}
//////////長時間不寫C語言了，自己看著改一下吧！
❽ (4) 給出關鍵字序列,給一個已知求余演算法,構造哈希表,求平均查找長度的思路
若結構中存在關鍵字和K相等的記錄,則必定在f(K)的存儲位置上。由此,不需比較便可直接取得所查記錄。稱這個對應關系f為散列函數
❾ 用哈希函數得到哈希表，哈希表中存放的是關鍵字,還是關鍵字所在元素的地址
根據哈希表的構造原理以及查找方法可以知道，存儲的應該是地址，貌似沒有聽說有存放關鍵字這一說法，在構造哈希表的時候通過關鍵字的hashcode()方法計算出散列碼，然後存放。在查找的時候通過要查找關鍵字對應的散列碼進而查找到存放的內容。