數(shù)據(jù)結(jié)構(gòu)-二叉排序樹(編輯修改稿)
2025-09-05 15:47 本頁面
【文章內(nèi)容簡介】 24 37 RR型 13 24 13 24 37 A B 24 37 13 A B 53 RL型 90 24 37 13 90 24 37 13 90 53 A B C 2 24 53 13 90 37 C B A 28 RL型 98 RR型 24 53 13 90 37 B C A 28 2 37 53 24 90 28 B A C 13 37 53 24 90 28 A B 2 13 98 37 90 24 98 28 13 53 哈希表的基本思想 : “一次” 查找成功。 關(guān)鍵字集合 映射函數(shù) H 地址空間 H(key) ASL的 T(n)=O(1)。 通常設(shè)定一個一維數(shù)組空間存儲記錄集合，則H(key)指示數(shù)組中的下標(biāo)。 稱這個一維數(shù)組為 哈希 (Hash)表 或 散列表 。 稱映射函數(shù) H 為 哈希函數(shù) 。 H(key)為 哈希地址 什么是哈希表 哈希表 0 1 2 3 4 5 6 7 8 9 10 11 12 H 例：假定一個線性表為： A = (18， 75， 60， 43， 54， 90， 46) 假定選取的哈希函數(shù)為 hash3(key) = key % 13 若根據(jù)哈希函數(shù)把元素存儲到哈希表 H[13] 中，則存儲映象為： 18 75 60 43 54 90 46 哈希表的 查找 同插入元素一樣。如從表中查找關(guān)鍵字為 60的元素時，只要利用上面的函數(shù)計算出地址 H(60) = 60 % 13 = 8 查找不成功： 查找 61： H(61)= 61%13= 9 0 1 2 3 4 5 6 7 8 9 10 11 12 H 18 75 60 43 54 90 46 如果 key1 ≠ key2， 但 H(key1) = H(key2) 這種現(xiàn)象稱為“ 沖突 ”，稱 key1 和 key2 為 同義詞 。 在實際應(yīng)用中，應(yīng)盡量選擇均勻的哈希函數(shù)來減少沖突。 沖突不能避免時，選定一個解決沖突的方法。 (1)裝填因子 (load factor): ? = (負(fù)載因子 ) m為 hash表的長度， n為填入的記錄數(shù)。 mn?越大，沖突的可能性越大。 ?越小，沖突的可能性會減小，但空間的利用率變低。 為兼顧兩者， ?在 [， ]范圍內(nèi)為宜。 (2) 與采用的散列函數(shù)有關(guān)。 (3) 與解決沖突的方法有關(guān)。 方法選擇的好壞也將減少或增加發(fā)生沖突的可能性 。 發(fā)生沖突與下列三個因素有關(guān)： 哈希函數(shù)的構(gòu)造方法 構(gòu)造 哈希 函數(shù)的目標(biāo)： 哈希 地址盡可能均勻分布在表空間上 ——均勻性好； 哈希 地址計算盡量簡單。 考慮因素： 函數(shù)的復(fù)雜度； 關(guān)鍵字長度與表長的關(guān)系； 關(guān)鍵字分布情況； 元素的查找頻率。 例： 1949年后出生的人口調(diào)查表，關(guān)鍵字是年份 年份 1949 1950 1951 … 人數(shù) … … … … H(key) = key + (1948) 此法僅適合于： 地址集合的大小 = = 關(guān)鍵字集合的大小 一、直接地址法 取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址 即： H(key) = key 或： H(key) = a* key + b 其中， a， b為常數(shù)。 二、數(shù)字分析法 例如：有若干記錄，關(guān)鍵字為 8 位十進(jìn)制數(shù)，假設(shè)哈希表的表長為 100, 對關(guān)鍵字進(jìn)行分析，取隨機性較好的兩位十進(jìn)制數(shù)作為哈希地址。 假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2,
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1