第二十六講哈希表及其查找(已修改)
2025-09-15 14:57 本頁(yè)面
【正文】 第七 章 查找 1． 握散列 相關(guān)知識(shí)。 學(xué)習(xí)要點(diǎn)包括 各種 散列函數(shù)的 使用及其 比較 。 2． 理解解決沖突的主要方法 。 ? 教學(xué)重點(diǎn)： 哈希表及哈希查找。 解決地址沖突的方法。 ? 教學(xué)難點(diǎn)： 解決地址沖突的方法。 ? 授課內(nèi)容 哈希表查找 (雜湊法 ) 哈希表與哈希方法 以上討論的查找方法，由于數(shù)據(jù)元素的存儲(chǔ)位置與關(guān)鍵碼之間不存在確定的關(guān)系，因此，查找時(shí)，需要進(jìn)行一系列對(duì)關(guān)鍵碼的查找比較，即“查找算法”是建立在比較的基礎(chǔ)上的，查找效率由比較一次縮小的查找范圍決定。理想的情況是依據(jù)關(guān)鍵碼直接得到 其對(duì)應(yīng)的數(shù)據(jù)元素位置，即要求關(guān)鍵碼與數(shù)據(jù)元素間存在一一對(duì)應(yīng)關(guān)系，通過(guò)這個(gè)關(guān)系，能很快地由關(guān)鍵碼得到對(duì)應(yīng)的數(shù)據(jù)元素位置。 【例 】 11 個(gè)元素的關(guān)鍵碼分別為 18， 27， 1， 20， 22， 6， 10， 13， 41， 15，25。選取關(guān)鍵碼與元素位置間的函數(shù)為 f(key)=key mod 11 1. 通過(guò)這個(gè)函數(shù)對(duì) 11 個(gè)元素建立查找表如下： 0 1 2 3 4 5 6 7 8 9 10 22 1 13 25 15 27 6 18 41 20 10 2. 查找時(shí)，對(duì)給定值 kx 依然通過(guò)這個(gè)函數(shù)計(jì)算出地址，再將 kx 與該地址單元中元素的關(guān)鍵碼比較，若相等，查找成功。 哈希表與哈希方法 ：選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵碼計(jì)算元素的存儲(chǔ)位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值 kx計(jì)算地址，將 kx與地址單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功，這就是 哈希方法 (雜湊法 )；哈希方法中使用的轉(zhuǎn)換函數(shù)稱為 哈希函數(shù) (雜湊函數(shù) )；按這個(gè)思想構(gòu)造的表稱為 哈希表 (雜湊表 )。 第二 十六 講 哈希表及其查找 第七 章 查找 對(duì)于 n 個(gè)數(shù)據(jù)元素的集合，總能找到關(guān)鍵碼與存放地址一 一對(duì)應(yīng)的函數(shù)。若最大關(guān)鍵為m，可以分配 m個(gè)數(shù)據(jù)元素存放單元，選取函數(shù) f(key)=key即可，但這樣會(huì)造成存儲(chǔ)空間的很大浪費(fèi)，甚至不可能分配這么大的存儲(chǔ)空間。通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過(guò)哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個(gè)哈希地址上，這種現(xiàn)象稱為 沖突 (Collision)，映射到同一哈希地址上的關(guān)鍵碼稱為 同義詞 ?？梢哉f(shuō)，沖突不可能避免，只能盡可能減少。所以，哈希方法需要解決以下兩個(gè)問題： 1. 構(gòu)造好的哈希函數(shù) （ 1）所選函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度。 （ 2）所選函 數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在哈希地址集中大致均勻分布，以減少空間 浪費(fèi)。 2. 制定解決沖突的方案。 構(gòu)造 哈希函數(shù) 的常用方法 一 . 直接定址法 Ha
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1