20172313 2018-2019-1 《程式設計與資料結構》課堂測試修改報告

課程：《程式設計與資料結構》

班級： 1723

姓名： 餘坤澎

學号：20172313

實驗教師：王志強

實驗日期：2018年10月19日

必修/選修： 必修

題目内容

測試原理

• 順序查找：原理較為簡單，通過周遊清單逐個比較進行查找。
• 折半查找：首先，假設表中元素是按升序排列，将表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄将表分成前、後兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重複以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
• 哈希查找（散列查找）：
  • 概念了解：什麼是哈希查找呢？在弄清楚什麼是哈希查找之前，我們要弄清楚哈希技術，哈希技術是在記錄的存儲位置和記錄的關鍵字之間建立一個确定的對應關系f，使得每個關鍵字key對應一個存儲位置f(key)。查找時，根據這個确定的對應關系找到給定值的映射f(key),若查找集合中存在這個記錄，則必定在f(key)的位置上。哈希技術既是一種存儲方法，也是一種查找方法。
  • 哈希函數大體有六種構造方法：

  1，直接定址法：

  函數公式：f(key)=a*key+b (a,b為常數)

  這種方法的優點是：簡單，均勻，不會産生沖突。但是需要事先知道關鍵字的分布情況，适合查找表較小并且連續的情況。

  2，數字分析法：

  比如我們的11位手機号碼“136XXXX7887”，其中前三位是接入号，一般對應不同營運公司的子品牌，如130是聯通如意通，136是移動神州行，153是電信等。中間四們是HLR識别号，表示使用者歸屬地。最後四們才是真正的使用者号。

  若我們現在要存儲某家公司員工登記表，如果用手機号碼作為關鍵字，那麼極有可能前7位都是相同的，是以我們選擇後面的四們作為哈希位址就是不錯的選擇。

  3，平方取中法：

  故名思義，比如關鍵字是1234，那麼它的平方就是1522756，再抽取中間的3位就是227作為哈希位址。

  4，折疊法：

  折疊法是将關鍵字從左到右分割成位數相等的幾個部分(最後一部分位數不夠可以短些)，然後将這幾部分疊加求和，并按哈希表表長，取後幾位作為哈希位址。

  比如我們的關鍵字是9876543210，哈希表表長三位，我們将它分為四組，987|654|321|0 ，然後将它們疊加求和987+654+321+0=1962，再求後3位即得到哈希位址為962，哈哈，是不是很有意思。

  5，除留餘數法：

  函數公式：f(key)=key mod p (p<=m)m為哈希表表長。

  這種方法是最常用的哈希函數構造方法。

  6，随機數法：

  函數公式：f(key)= random(key)。

  這裡random是随機函數，當關鍵字的長度不等是，采用這種方法比較合适。

  • 沖突的産生：兩個不同的的關鍵字可能對應同一個記憶體位址。 這樣，将導緻後方的關鍵字無法儲存。
  • 沖突的解決：

    • 開放定值法：這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希位址p=H（key）出現沖突時，以p為基礎，産生另一個哈希位址p1，如果p1仍然沖突，再以p為基礎，産生另一個哈希位址p2，…，直到找出一個不沖突的哈希位址pi ，将相應元素存入其中。這種方法有一個通用的再散列函數形式：

      Hi=（H（key）+di）% m i=1，2，…，n

      其中H（key）為哈希函數，m 為表長，di稱為增量序列。增量序列的取值方式不同，相應的再散列方式也不同。主要有以下三種：

線性探測再散列

dii=1，2，3，…，m-1

這種方法的特點是：沖突發生時，順序檢視表中下一單元，直到找出一個空單元或查遍全表。

二次探測再散列

di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )

這種方法的特點是：沖突發生時，在表的左右進行跳躍式探測，比較靈活。

僞随機探測再散列

di=僞随機數序列。

具體實作時，應建立一個僞随機數發生器，（如i=(i+p) % m），并給定一個随機數做起點。

例如，已知哈希表長度m=11，哈希函數為：H（key）= key % 11，則H（47）=3，H（26）=4，H（60）=5，假設下一個關鍵字為69，則H（69）=3，與47沖突。

如果用線性探測再散列處理沖突，下一個哈希位址為H1=（3 + 1）% 11 = 4，仍然沖突，再找下一個哈希位址為H2=（3 + 2）% 11 = 5，還是沖突，繼續找下一個哈希位址為H3=（3 + 3）% 11 = 6，此時不再沖突，将69填入5号單元。

如果用二次探測再散列處理沖突，下一個哈希位址為H1=（3 + 12）% 11 = 4，仍然沖突，再找下一個哈希位址為H2=（3 - 12）% 11 = 2，此時不再沖突，将69填入2号單元。

如果用僞随機探測再散列處理沖突，且僞随機數序列為：2，5，9，……..，則下一個哈希位址為H1=（3 + 2）% 11 = 5，仍然沖突，再找下一個哈希位址為H2=（3 + 5）% 11 = 8，此時不再沖突，将69填入8号單元。

- 再哈希法：這種方法是同時構造多個不同的哈希函數：Hi=RH1（key） i=1，2，…，k

當哈希位址Hi=RH1（key）發生沖突時，再計算Hi=RH2（key）……，直到沖突不再産生。這種方法不易産生聚集，但增加了計算時間。

- 鍊位址法：這種方法的基本思想是将所有哈希位址為i的元素構成一個稱為同義詞鍊的單連結清單，并将單連結清單的頭指針存在哈希表的第i個單元中，因而查找、插入和删除主要在同義詞鍊中進行。鍊位址法适用于經常進行插入和删除的情況。

• 方法優點
  • 開放定值法：1.記錄更容易進行序列化（serialize）操作。 2.如果記錄總數可以預知，可以建立完美哈希函數，此時處理資料的效率是非常高的。
  • 鍊位址法： ①對于記錄總數頻繁可變的情況，處理的比較好（也就是避免了動态調整的開銷）。 ②由于記錄存儲在結點中，而結點是動态配置設定，不會造成記憶體的浪費，是以尤其适合那種記錄本身尺寸（size）很大的情況，因為此時指針的開銷可以忽略不計了。 ③删除記錄時，比較友善，直接通過指針操作即可 。
• 方法缺點：
  • 開放定值法：1.存儲記錄的數目不能超過桶數組的長度，如果超過就需要擴容，而擴容會導緻某次操作的時間成本飙升，這在實時或者互動式應用中可能會是一個嚴重的缺陷 2.使用探測序列，有可能其計算的時間成本過高，導緻哈希表的處理性能降低 3.由于記錄是存放在桶數組中的，而桶數組必然存在空槽，是以當記錄本身尺寸（size）很大并且記錄總數規模很大時，空槽占用的空間會導緻明顯的記憶體浪費 4.删除記錄時，比較麻煩。比如需要删除記錄a，記錄b是在a之後插入桶數組的，但是和記錄a有沖突，是通過探測序列再次跳轉找到的位址，是以如果直接删除a，a的位置變為空槽，而空槽是查詢記錄失敗的終止條件，這樣會導緻記錄b在a的位置重新插入資料前不可見，是以不能直接删除a，而是設定删除标記。這就需要額外的空間和操作。
  • 鍊位址法： 1.存儲的記錄是随機分布在記憶體中的，這樣在查詢記錄時，相比結構緊湊的資料類型（比如數組），哈希表的跳轉通路會帶來額外的時間開銷 2.如果所有的 key-value 對是可以提前預知，并之後不會發生變化時（即不允許插入和删除），可以人為建立一個不會産生沖突的完美哈希函數（perfect hash function），此時封閉散列的性能将遠高于開放散列 ③由于使用指針，記錄不容易進行序列化（serialize）操作

測試結果

• 畫出順序查找的順序表和成功平均查找長度。

  

• 畫出折半查找的順序表和成功平均查找長度。

  

• 用線性探查法實作散列查找。

  

• 用鍊位址法實作散列查找。

  

其他

  前幾周的内容相對來說比較簡單，是以學習的時候有些放松，這次測試也讓我明白自己不會的東西還有很多，是以不能懈怠，還要繼續努力才是，希望自己能在以後的學習生活中能繼續進步！