1樓：匿名使用者
舉個簡單的例子：
有一百個數字1－100，隨機產生20個，求20個不重複的數的和。
例如：1，1，1，1，1，1，1，1，1，1，2，2，3，6，3，2，3，2，3，2
則20個不重複的數的和＝1＋2＋3＋6＝12main()}}
上面的思想是，每次得到一個數字，讓它和連結串列裡的數字依依比較，如果連表裡面沒有，就把它直接加到連表裡。如果連表裡的東西多了的話，那麼就要比較很多次，很浪費時間。
如果用哈西表的話，就可以通過查詢表，一次就確定數字是否重複：
main()}}
2樓：匿名使用者
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→ ，通常稱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隨機均勻地分佈在表的地址集上，以使衝突最小化。
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。
資料結構問題，資料結構（java）
資料結構是計算機儲存 組織資料的方式。資料結構是指相互之間存在一種或多種特定關係的資料元素的集合。通常情況下，精心選擇的資料結構可以帶來更高的執行或者儲存效率。一 資料的邏輯結構 指反映資料元素之間的邏輯關係的資料結構，其中的邏輯關係是指資料元素之間的前後件關係，而與他們在計算機中的儲存位置無關。邏...
關於雜湊表，雜湊函式的兩個問題，有關雜湊表雜湊函式的題 應該很簡單，可惜我不會
59放在11號位置,搜尋次數是4次,有0 17共18個格子,mod是取餘操作,26mod17 9,則26放9號,25mod17 8,25放8號,72mod17 0,72放0號,38mod17 4,38放4號,8mod17 8,由於8號被25佔用,嘗試放在9號,9號又給26佔用,8最終放在10號,18...
資料結構問題void A linklistl 和void A linklist l 的區別是什麼
書中的寫法void initlist linklist l 是為了告訴讀者，這裡需要傳入一個指標而已 我記得上課的時候老師是這麼說的 函式宣告和實現時寫void initlist struct lnode l 呼叫這個函式時寫initlist linklist l 我就這麼理解的 哀傷 霜之哀傷 l...