-查找與排序技術(shù)

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ)計(jì)算機(jī)軟件技術(shù)基礎(chǔ)4 4 查找與排序技術(shù)查找與排序技術(shù)賴生建 博士博士沙河校區(qū)科研樓710#, 物理電子學(xué)院物理電子學(xué)院3.2 3.2 哈希表技術(shù)哈希表技術(shù)11/12/2021 12:55 AM23.2.1 Hash表的基本概念3.2.2 幾種常用的Hash表3.2.1 3.2.1 HashHash表的基本概念表的基本概念11/12/2021 12:55 AM31. 直接查找技術(shù) 設(shè)表的長(zhǎng)度為n。如果存在一個(gè)函數(shù)ii(k)，對(duì)于表中的任意一個(gè)元素的關(guān)鍵字k，滿足以下條件 (1) 1in； (2) 對(duì)于任意的元素關(guān)鍵字k1k2，恒存在i(k1)i(k2)。 則稱此表為直接查找表

2、。其中函數(shù)ii(k)稱為關(guān)鍵字k的映象函數(shù)。3.2.1 3.2.1 HashHash表的基本概念表的基本概念11/12/2021 12:55 AM4 (1) 直接查找表的填入要將關(guān)鍵字為k元素填入到直接查找表，只需做以下兩步： 1) 計(jì)算關(guān)鍵字k的映象函數(shù)ii(k)； 2) 將關(guān)鍵字k及有關(guān)元素信息填入到表的第i項(xiàng)。(2) 直接查找表的取出要在直接查找表中取出關(guān)鍵字k的元素，也只需做以下兩步 1) 計(jì)算關(guān)鍵字k的映象函數(shù)ii(k)； 2) 檢查表中第i項(xiàng)： 若第i項(xiàng)為空，則說明表中沒有關(guān)鍵字為k的元素；否則取出第i項(xiàng)中的元素即可。3.2.1 3.2.1 HashHash表的基本概念表的基本概念

3、11/12/2021 12:55 AM52. Hash表 例：將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長(zhǎng)度為n12的表中。映象函數(shù)為iINT(k/3)1。3.2.1 3.2.1 HashHash表的基本概念表的基本概念11/12/2021 12:55 AM6設(shè)表的長(zhǎng)度為n。如果存在一個(gè)函數(shù)ii(k)，對(duì)于表中的任意一個(gè)元素的關(guān)鍵字k，滿足1in，則稱此表為Hash表。其中函數(shù)ii(k)稱為關(guān)鍵字k的Hash碼。(1)構(gòu)造合適的Hash碼，以便盡量減少表中元素沖突的次數(shù)。即Hash碼的均勻性要比較好。(2)當(dāng)表中元素發(fā)生沖突時(shí)，要進(jìn)行適當(dāng)?shù)奶?/p>

4、理。3.2.1 3.2.1 HashHash表的基本概念表的基本概念11/12/2021 12:55 AM73. Hash碼的構(gòu)造(1) 使各關(guān)鍵字盡可能均勻地分布在Hash表中，即Hash碼的均勻性要好，以便減少?zèng)_突發(fā)生的機(jī)會(huì)。 (2) Hash碼的計(jì)算要盡量簡(jiǎn)單。由于哈希碼的設(shè)計(jì)很大程度上依賴于各關(guān)鍵字的特性，下面常用的構(gòu)造方法(1) 截段法 (2) 分段疊加法 (3) 除法 (4) 乘法3.2.1 3.2.1 HashHash表的基本概念表的基本概念11/12/2021 12:55 AM8(1) 截段法 選取與關(guān)鍵字對(duì)應(yīng)的數(shù)字串中的一段（一般選取低位）作為關(guān)鍵字的哈希碼。(2) 分段疊加

5、法 關(guān)鍵字的編碼串分割成若干段， 然后把它們疊加后再進(jìn)行截?cái)唷?3) 除法 關(guān)鍵字編碼除以表的長(zhǎng)度，取余數(shù) imod(k，n)3.2.1 3.2.1 HashHash表的基本概念表的基本概念11/12/2021 12:55 AM9(4) 乘法 關(guān)鍵字編碼與一常數(shù)相乘，再除以表的長(zhǎng)度的余數(shù) imod(k*，n)一般取0.618033988747，或0.6125423371， 或0.6161616161。3.2.1 3.2.1 HashHash表的基本概念表的基本概念11/12/2021 12:55 AM10哈希查找，也稱為散列查找。它既是一種查找方法，又是一種存貯方法，稱為散列存貯。散列存貯的內(nèi)

6、存存放形式也稱為散列表（Hash表） Hash：指形式上雜亂無章，沒有規(guī)律的一組元素隊(duì)列。與前面所述的查找不同，Hash表技術(shù)可以直接確定被查元素在表中的位置，按理論分析真正不需要用到比較的一種查找方法。3.2.2 3.2.2 幾種常見幾種常見HashHash表表- -線性線性HashHash表表11/12/2021 12:55 AM111)線性Hash表的填入 將關(guān)鍵字k及有關(guān)信息填入線性Hash表的步驟如下： 1) 計(jì)算關(guān)鍵字k的Hash碼ii(k)。 2) 檢查表中第i項(xiàng)的內(nèi)容： 若第i項(xiàng)為空，則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng)；若第i項(xiàng)不空，則令imod(i1，n)，轉(zhuǎn)2)繼續(xù)檢查。 只要

7、Hash表尚未填滿，最終總可以找到一個(gè)空項(xiàng)，將關(guān)鍵字k及有關(guān)信息填入到Hash表中。3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表11/12/2021 12:55 AM122) 線性Hash表的取出 要在線性Hash表中取出關(guān)鍵字k元素，其步驟如下 1) 計(jì)算關(guān)鍵字k的Hash碼ii(k)。 2) 檢查表中第i項(xiàng)的內(nèi)容： 若第i項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；若第i項(xiàng)為空，則表示在Hash表中沒有該關(guān)鍵字的信息；若第i項(xiàng)不空，且登記的不是關(guān)鍵字k，則令 imod(i1，n) 轉(zhuǎn)2)繼續(xù)檢查。3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表11/12/20

8、21 12:55 AM13例 將關(guān)鍵字序列 (09，31，26，19，01，13，02，11，27，16，05，21)依次填入長(zhǎng)度為n12的線性Hash表中。設(shè)Hash碼為iINT(k/3)1。3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表11/12/2021 12:55 AM141)在線性Hash表填入的過程中，當(dāng)發(fā)生沖突時(shí)，首先考慮 的是下一項(xiàng)，因此，當(dāng)Hash碼的沖突較多時(shí)，在線性 Hash表中會(huì)存在“堆聚”現(xiàn)象，即許多關(guān)鍵字被連續(xù)登記在一起，從而會(huì)降低查找效率。2)在線性Hash表的填入過程中，處理沖突時(shí)會(huì)帶來新的沖突。3.2.2 3.2.2 幾種常見的幾種常見的Ha

9、shHash表表11/12/2021 12:55 AM15線性Hash表查找一個(gè)關(guān)鍵字的平均查找次數(shù)：哈希表的填滿率222E/m n實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告報(bào)告6-26-2哈希表類及應(yīng)用哈希表類及應(yīng)用編寫哈希表類及應(yīng)用。編寫哈希表類及應(yīng)用。( (P162) )實(shí)驗(yàn)報(bào)告要求：實(shí)驗(yàn)報(bào)告要求：1. 1.編寫哈希表類編寫哈希表類2.2.哈希表各操作方法實(shí)現(xiàn)哈希表各操作方法實(shí)現(xiàn)3. 3.舉例應(yīng)用哈希表舉例應(yīng)用哈希表作業(yè)報(bào)告模板在網(wǎng)絡(luò)學(xué)堂作業(yè)報(bào)告模板在網(wǎng)絡(luò)學(xué)堂( (物理電子學(xué)院物理電子學(xué)院-軟件技術(shù)軟件技術(shù)基礎(chǔ)基礎(chǔ)-課程教案課程教案) )下載，完成報(bào)告后上傳到網(wǎng)絡(luò)學(xué)堂對(duì)下載，完成報(bào)告后上傳到網(wǎng)絡(luò)學(xué)堂對(duì)應(yīng)的實(shí)驗(yàn)報(bào)告應(yīng)的

10、實(shí)驗(yàn)報(bào)告6 6的文件夾中，報(bào)告名稱的文件夾中，報(bào)告名稱: : 學(xué)號(hào)學(xué)號(hào)+ +姓名姓名_ _ 實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告報(bào)告6-2.doc6-2.doc3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -隨機(jī)隨機(jī)HashHash表表11/12/2021 12:55 AM171) 隨機(jī)Hash表的填入 將關(guān)鍵字k及有關(guān)信息填入隨機(jī)Hash表的步驟如下： 1) 計(jì)算關(guān)鍵字k的Hash碼i0i(k)。且令ii0。 2) 偽隨機(jī)數(shù)序列初始化，令j1（即將取隨機(jī)數(shù)指針指向偽隨機(jī)數(shù)序列中的第1個(gè)隨機(jī)數(shù)）。 3) 檢查表中第i項(xiàng)的內(nèi)容： 若第i項(xiàng)為空，則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng) 若第i項(xiàng)不空，則令im

11、od(i0RN(j)，n)，并令jj1（即將取隨機(jī)數(shù)指針指向下一個(gè)隨機(jī)數(shù)）， 轉(zhuǎn)3)繼續(xù)檢查。其中RN(j)表示偽隨機(jī)數(shù)序列RN中的第j個(gè)隨機(jī)數(shù)。3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -隨機(jī)隨機(jī)HashHash表表11/12/2021 12:55 AM18偽隨機(jī)數(shù)序列RN按下列方法產(chǎn)生：3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -隨機(jī)隨機(jī)HashHash表表11/12/2021 12:55 AM19例，將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長(zhǎng)度為n2416的隨機(jī)Hash表中。設(shè)Has

12、h碼為iINT(k/3)1。偽隨機(jī)數(shù)序列為：1，6，15，12，13，2，11，8，9，14，7，4，5，10，3，0。3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -隨機(jī)隨機(jī)HashHash表表11/12/2021 12:55 AM202) 隨機(jī)Hash表的取出要在隨機(jī)Hash表中取出關(guān)鍵字k的元素，其步驟如下： 1)計(jì)算關(guān)鍵字k的Hash碼i0i(k)。且令ii0。 2)偽隨機(jī)數(shù)序列初始化，令j1（即將取隨機(jī)數(shù)指針指向偽隨機(jī)數(shù)序列中的第1個(gè)隨機(jī)數(shù)）。 3)檢查表中第i項(xiàng)的內(nèi)容： 若第i項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可； 若第i項(xiàng)空，則表示在Hash表中沒有該關(guān)鍵字

13、信息； 3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -隨機(jī)隨機(jī)HashHash表表11/12/2021 12:55 AM21 若第i項(xiàng)不空，則令imod(i0RN(j)，n)，并令jj1（即將取隨機(jī)數(shù)指針指向下一個(gè)隨機(jī)數(shù)）， 轉(zhuǎn)3)繼續(xù)檢查。其中RN(j)表示偽隨機(jī)數(shù)序列RN中的第j個(gè)隨機(jī)數(shù)。隨機(jī)Hash表查找一個(gè)關(guān)鍵字的平均查找次數(shù)：哈希表的填滿率1ln(1)E /m n3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -溢出溢出HashHash表表11/12/2021 12:55 AM22溢出Hash表包括Hash表和溢出表兩部分。在Hash表的填

14、入過程中，將沖突的元素順序填入溢出表，而當(dāng)查找過程中發(fā)現(xiàn)沖突時(shí)，就在溢出表中進(jìn)行順序查找。溢出表是一個(gè)順序查找表。3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -溢出溢出HashHash表表11/12/2021 12:55 AM231) 溢出Hash表的填入 將關(guān)鍵字k及有關(guān)信息填入溢出Hash表的步驟如下 1) 計(jì)算關(guān)鍵字k的Hash碼ii(k)。 2) 檢查表中第i項(xiàng)的內(nèi)容： 若第i項(xiàng)為空，則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng) 若第i項(xiàng)不空，則將關(guān)鍵字k及有關(guān)信息依次填入 溢出表中的自由項(xiàng)。3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -溢出溢出Has

15、hHash表表11/12/2021 12:55 AM242) 溢出Hash表的取出 要在溢出Hash表中取出關(guān)鍵字k的元素，其步驟： 1) 計(jì)算關(guān)鍵字k的Hash碼ii(k)。 2) 檢查表中第i項(xiàng)的內(nèi)容： 若第i項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；若第i項(xiàng)為空，則表示在Hash表中沒有該關(guān)鍵字信息； 若第i項(xiàng)不空，且登記的不是關(guān)鍵字k，則轉(zhuǎn)入在 溢出表中進(jìn)行順序查找。3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -溢出溢出HashHash表表11/12/2021 12:55 AM25例將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21

16、)依次填入長(zhǎng)度為n12的溢出Hash表中。設(shè)Hash碼為iINT(k/3)1。3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -溢出溢出HashHash表表11/12/2021 12:55 AM26例將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長(zhǎng)度為n12的溢出Hash表中。設(shè)Hash碼為iINT(k/3)1。實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告報(bào)告6-36-3溢出哈溢出哈希表類及應(yīng)用希表類及應(yīng)用編寫溢出哈希表類及應(yīng)用。編寫溢出哈希表類及應(yīng)用。( (P170) )實(shí)驗(yàn)報(bào)告要求：實(shí)驗(yàn)報(bào)告要求：1. 1.編寫溢出哈希表類編寫溢出哈希表類2.2.溢出哈希

17、表各操作方法實(shí)現(xiàn)溢出哈希表各操作方法實(shí)現(xiàn)3. 3.舉例應(yīng)用溢出哈希表舉例應(yīng)用溢出哈希表作業(yè)報(bào)告模板在網(wǎng)絡(luò)學(xué)堂作業(yè)報(bào)告模板在網(wǎng)絡(luò)學(xué)堂( (物理電子學(xué)院物理電子學(xué)院-軟件技術(shù)軟件技術(shù)基礎(chǔ)基礎(chǔ)-課程教案課程教案) )下載，完成報(bào)告后上傳到網(wǎng)絡(luò)學(xué)堂對(duì)下載，完成報(bào)告后上傳到網(wǎng)絡(luò)學(xué)堂對(duì)應(yīng)的實(shí)驗(yàn)報(bào)告應(yīng)的實(shí)驗(yàn)報(bào)告6 6的文件夾中，報(bào)告名稱的文件夾中，報(bào)告名稱: : 學(xué)號(hào)學(xué)號(hào)+ +姓名姓名_ _ 實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告報(bào)告6-3.doc6-3.doc3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -拉鏈拉鏈HashHash表表11/12/2021 12:55 AM28拉鏈Hash表又分為外鏈Hash表與內(nèi)鏈Hash表。1) 外鏈Hash表的填入 將關(guān)鍵字k及有關(guān)信息填入外鏈Hash表的步驟如下 1) 計(jì)算關(guān)鍵字k的Hash碼ii(k)。 2) 取得一個(gè)新結(jié)點(diǎn)p，并將關(guān)鍵字k及有關(guān)信息填入結(jié)點(diǎn)p。 3) 將結(jié)點(diǎn)p鏈入以H(i)為頭指針的鏈表的鏈頭。3.2.2 3.2.2 幾種常見的幾種常見的HashHash表表- -拉鏈拉鏈HashHash表表11/12/2021 12:55 AM29例將關(guān)鍵字序列(09,