【文章內容簡介】 r = H（ key） 建立哈希函數的原則 – 均勻性 H（ key） 的值均勻分布在哈希表中； – 簡單 以提高地址計算的速度 。 下一頁 上一頁 停止放映 [第 35頁 /81] 沖突及沖突處理 在哈希元素求解過程中 ， 不同關鍵字值對應到同一個存儲地址的現象稱為沖突 。 即關鍵字 K1 ? K2， 但哈希函數值 H（ K1）= H（ K2） 。 均勻的哈希函數可以減少沖突 ， 但不能避免沖突 。 發(fā)生沖突后 ， 必須解決；也即必須尋找下一個可用地址 。 處理沖突是建立哈希表過程中不可缺少的一部分 。 下一頁 上一頁 停止放映 [第 36頁 /81] 處理沖突 —— 開放地址法 當發(fā)生地址沖突后 ， 求解下一個地址用 Hi =( H（ key） +di） MOD m i=1,2,… ,k(k ? m1) 其中 : H(key)為哈希函數 ,m為哈希表長度 ,di為增量序列 。 增量序列的不同取法 ， 又構成不同的開放地址法 。 線性探測再散列 di=1,2,… ,m1 二次探測再散列 di=12 , 12, 22, 22, … ,+k2, k2(k ? m/2) 下一頁 上一頁 停止放映 [第 37頁 /81] 處理沖突 —— 鏈地址法 當發(fā)生地址沖突后 ,將所有函數值相同的記錄連成一個單鏈表 。 下一頁 上一頁 停止放映 [第 38頁 /81] 鏈地址法處理沖突 對給定數列 { 22,41,53,46,30,13,1,67 },建立哈希表 。 表長取 9,即 [0~8]。 哈希函數設定為 : H(key) = key MOD 8 。 1 2 3 4 5 6 7 41 1 ^ 46 13 ^ 30 ^ 22 ^ 53 ^ ^ ^ 67 H(22)=H(46)=H(30)=6 H(53)=H(13)=5 H(67)=3 H(41)=H(1)=1 下一頁 上一頁 停止放映 [第 39頁 /81] 哈希查找操作步驟 用給定的哈希函數構造哈希表 根據選擇的沖突處理方法解決地址沖突 在哈希表的基礎上執(zhí)行哈希查找 下一頁 上一頁 停止放映 [第 40頁 /81] 建立哈希表 建立哈希表操作步驟： step1 取數據元素的關鍵字 key， 計算其哈希函數值 （ 地址 ） 。 若該地址對應的存儲空間還沒有被占用 ， 則將該元素存入；否則執(zhí)行 step2解決沖突 。 step2 根據選擇的沖突處理方法 ， 計算關鍵字 key的下一個存儲地址 。 若下一個存儲地址仍被占用 ， 則繼續(xù)執(zhí)行 step2， 直到找到能用的存儲地址為止 。 下一頁 上一頁 停止放映 [第 41頁 /81] 舉例 對給定數列 { 22,41,53,46,30,13,1,67 },建立哈希表 。 表長取 9,即 [0~8]。 哈希函數設定為 : H(key) = key MOD 8 ,用線性探測解決沖突 Hi=(H(key)+di) MOD m ,di=1,2,… ,m1。 0 1 2 3 4 5 6 7 8 22 22 0 1 2 3 4 5 6 7 8 41 比較次數： 1 1 取 41，計算 H（ 41） =1，該地址空，可用； 取 22，計算 H（ 22） =6，該地址空，可用； 下一頁 上一頁 停止放映 [第 42頁 /81] 舉例（續(xù)一） 取 53，計算 H（ 53） = 5，該地址空，可用； 22 41 0 1 2 3 4 5 6 7 8 53 比較次數： 1 1 1 22 41 53 46 0 1 2 3 4 5 6 7 8 比較次數： 1 1 1 2 取 46，計算 H（ 46） = 6，該地址沖突，用線性探測法計算下一個可用地址 Hi=（ 6+1） MOD 8 = 7，該地址空，可用； 下一頁 上一頁 停止放映 [第 43頁 /81] 舉例（續(xù)二） 取 30，計算 H（ 30） = 6，該地址沖突，用線性探測法計算下一個可用地址 Hi=（ 6+1） MOD 8 = 7，該地址沖突，再用線性探測法計算下一個可用地址； Hi=0，地址空，可用； 22 41 0 1 2 3 4 5 6 7 8 53 比較次數： 3 1 1 1 2 46 30 22 41 53 46 0 1 2 3 4 5 6 7 8 比較次數： 3 1 6 1 1 2 30 13 取 13，計算 H（ 13） = 5，依法解決沖突，得出： 下一頁 上一頁 停止放映 [第 44頁 /81] 舉例（續(xù)三） 取 1，計算 H（ 1） = 1，該地址沖突，解決沖突可得： 22 41 0 1 2 3 4 5 6 7 8 53 46 30 13 比較次數： 3 1 6 3 1 1 2 1 22 41 53 46 30 13 1 67 比較次數： 3 1 6 3 2 1 1 2 0 1 2 3 4 5 6 7 8 取 67，計算 H（ 67） = 3，沖突，解決沖突，得出： 下一頁 上一頁 停止放映 [第 45頁 /81] 哈希查找 哈希查找的過程和建立哈希表的過程是一致的 。 設哈希表為 HST[0~M1]， 哈希函數取 H（ key） ，解決沖突的方法為 R（ x） ， 則哈希查找步驟為： Step1 對給定 k值 ， 計算哈希地址 Di=H（ k） ；若 HST[i]為空 ， 則查找失??；若 HST[i]=k， 則查找成功；否則 ， 執(zhí)行 step2（ 處理沖突 ） 。 Step2 重復計算處理沖突的下一個存儲地址 Dk=R （ Dk1 ） ， 直到 HST[Dk] 為空 ， 或HST[Dk}=k為止 。 若 HST[Dk]=K， 則查找成功 ，否則查找失敗 。 下一頁 上一頁 停止放映 [第 46頁 /81] 查找舉例 以上述哈希表為例 。 哈希函數為 H(key)=key MOD 8, 設有數列 {22,41,53,46,30,13,1,67},用線性探測法解決沖突 ,建立的哈希的表為 : 0 1 2 3 4 5 6 7 8 比較次數： 3 1 6 3 2 1 1 2 22 41 53 46 30 13 1 67 8 1 8 19 平均查找長度 ASL= (3+1+6+3+2+1+1+2)= 查找 key = 67 比較 兩次找到 ,查找成功 。 查找 key = 21 比較 8次找不到 ,查找失敗。 示例 下一頁 上一頁 停止放映 [第 47頁 /81] 排序基本概念 排序是計算機內經常進行的一種操作 ， 其目的是將一組同類型的記錄序列調整為按照元素關鍵字有序的記錄序列 。 例如將學生記錄按學號排序 ，將課程記錄按課程編碼排序 。 排序的形式化定義為：假設含 n個記錄的序列為 { R1, R2,… ， Rn }， 其相應的關鍵字序列為{ K1, K2,… ， Kn }。 這些關鍵字相互之間可以進行比較 ， 即在它們之間存在著這樣一個關系Kp1≤K p2≤ … ≤K pn， 按此固有關系將最初的記錄序列重新排列為 { Rp1, Rp2, … ， Rpn }的操作稱作排序 。 下一頁 上一頁 停止放映 [第 48頁 /81] 排序分為 內部排序 和 外部排序 。 若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為 內部排序 ； 反之，若參加排序的記錄數量很大，整個序列的排序過程不可能在內存中完成，則稱此類排序問題為 外部排序 。 本節(jié)只討論內部排序的若干方法 下一頁 上一頁 停止放映 [第 49頁 /81] 內部排序分類方法 ? 按方法實現特點可分為 插入排序、選擇排序、交換排序、歸并排序 等等； ? 按方法效率可分為簡單的排序法、先進的排序法等等。 簡單的排序法 包括插入排序、選擇排序、冒泡排序等，它們的時間復雜度為 O(n2)。而 先進的排序法 包括 快速排序、歸并排序等， 它們的 時間復雜度 大約 為 O(nlog2n)。 下一頁 上一頁 停止放映 [第 50頁 /81] 插入排序算法 ? 基本思想： 將 n個元素的數列分為已有序和無序兩個部分 。 {{a1}， {a2， a3， a4， … ,an}} {{a1(1)， a2(1)}， {a3(1)， a4(1) … ,an(1)}} … ... {{a1(n1)， a2(n1) ， … }, {an(n1)}} 有序 無序 ?每次處理就是將無序數列的第一個元素與有序數列的元素從后往前逐個進行比較 ,找出插入位置 ,將該元素插入到有序數列的合適位置中 。 下一頁 上一頁 停止放映 [第 51頁 /81] 插入排序算法步驟 ? Step1 從有序數列 {a1}和無序數列 {a2,a3,… ,an}開始進行排序 。 ? S