數(shù)據(jù)結(jié)構(gòu)散列hashing(已修改)
2025-05-29 00:10 本頁(yè)面
【正文】 20210203 散列 (Hashing) ? 在線性表、樹結(jié)構(gòu)中查找紀(jì)錄是通過與關(guān)鍵 字的 “ 比較 ” 完成的。 ? 順序查找，比較的結(jié)果為 “ =”或 “ ≠ ” ? 非順序查找，比較的結(jié)果為 “ ”， “ =”， “ ” ? 散列的思想： 根據(jù)紀(jì)錄的關(guān)鍵字直接找到記錄的存儲(chǔ)位置， 即為關(guān)鍵字和記錄的存儲(chǔ)位置建立一個(gè)對(duì)應(yīng) 關(guān)系 f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的 存儲(chǔ)位置相對(duì)應(yīng)。 對(duì)應(yīng)關(guān)系 f為散列函數(shù)，按該思想建立的表 為散列表。 20210203 根據(jù)設(shè)定的哈希函數(shù) H(key)和處理沖突的方法將一組關(guān)鍵字映像到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的 “ 像 ” 作為紀(jì)錄在表中的存儲(chǔ)位置，這種表便稱為哈希表，這一影像過程稱為哈希造表或散列，所得存儲(chǔ)位置稱哈希地址或散列地址。 哈希表的定義 20210203 ? 散列方法在表項(xiàng)的存儲(chǔ)位置與它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系 Hash( )，使每個(gè)關(guān)鍵字與結(jié)構(gòu)中一個(gè)唯一存儲(chǔ)位置相對(duì)應(yīng)： Address ＝ Hash ( ) ? 在查找時(shí)，首先對(duì)表項(xiàng)的關(guān)鍵字進(jìn)行函數(shù)計(jì)算，把函數(shù)值當(dāng)做表項(xiàng)的存儲(chǔ)位置，在結(jié)構(gòu)中按此位置取表項(xiàng)比較。若關(guān)鍵字相等，則查找成功。在存放表項(xiàng)時(shí)，依相同函數(shù)計(jì)算存儲(chǔ)位置，并按此位置存放。 20210203 構(gòu)造散列函數(shù)時(shí)的幾點(diǎn)要求： ? 散列函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān) 鍵碼，如果散列表允許有 m個(gè) 地址時(shí) ,其值域必 須在 0 到 m1 之間。 ? 散列函數(shù)計(jì)算出來的地址應(yīng)能均勻分布在整個(gè) 地址空間中：若 key是從關(guān)鍵字集合中隨機(jī)抽 取的一個(gè)關(guān)鍵字，散列函數(shù)應(yīng)能以同等概率取 0到 m1 中的每一個(gè)值。 ? 散列函數(shù)應(yīng)是簡(jiǎn)單的，能在較短的時(shí)間內(nèi)計(jì)算 出結(jié)果。 哈希函數(shù)的構(gòu)造方法 20210203 1. 直接定址法 此類函數(shù)直接取關(guān)鍵字或關(guān)鍵字的某個(gè) 線性函數(shù) 值作為散列地址： Hash ( key ) ＝ a * key + b { a, b為常數(shù) } ? 這類散列函數(shù)是一對(duì)一的映射，一般
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1