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