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