溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
1、直接映射表
查找數據時，直接定位，時間復雜度為：O(1)；
局限性：浪費大量的內存空間；
2、哈希表
(1)、用一個哈希函數Hash()來隨機映射那些鍵；
抽象模型
(2)、哈希沖突時：
i、鏈地址法，時間復雜度最壞：O(n)；
簡單均勻哈希的時間復雜度：O(1+a)；a：裝載因子
哈希函數的選取：除留余數法；
ii、開放尋址法，沒有鏈表；
利用多次哈希函數，探測空的位置，直到找到一個可以存放元素的位置即可；探查序列很重要！！！
插入、查詢就根據探查序列比較簡單，刪除比較難做；
探測序列：a、線性探測：一個挨一個位置的探測，往下掃描；
探測序列：b、二次哈希：2個哈希函數的和掃描；
哈希表越滿，其探查效率越低；
3、哈希表溢出，動態哈希怎么實現？
i、首先申請一個原哈希表2倍大的空間；
ii、在將舊有元素移到新的哈希表空間中；
iii、在釋放原有空間；
平攤分析的思想：
一個插入的平均代價時間復雜度：O(1)；
n個元素的插入時間復雜度是：O(n)；
4、哈希函數的所有鍵映射同一個槽，此時查詢效率極為低下。
(1)、問題關鍵：選擇哈希函數，要隨機選擇，與輸入的哈希運算的鍵保存獨立，程序員本身也不能確定在實際運行時會用到哪一個哈希函數，無法預測隨機數的輸出；----->全域哈希
(2)、全域哈希解決的問題：所有鍵都相同，此時隨機選擇哈希函數將會使其映射到不同的槽中；
哈希函數集H中隨機地選擇函數h，均勻的分布在哈希表中；
(3)、全域哈希的構造：
i、槽的總數為m = 質數時成立，k = <k_0,k_1,.....,k_r>把任意的鍵分解為r+1位，可以把k看成k_0，k_1......k_r(k_i >= 0 && k_i <= m-1)，k用"m進制"來表示；k不斷除m，取余在除(進制轉換法)
ii、構造一個a = <a0,a1,a2....ar>，隨機地從(0,1,2,....m-1)中選取元素分配到a集合中；
哈希函數集：k x a，k中的每一項和a中的每一項相乘，再把乘積全部加起來，在對m取余，就得到分配的槽數；哈希函數集的大小：m^(r+1)；
(4)、全域哈希是用隨機函數的思想，但是有很小很小的概率還是會沖突的，解決方案：完全哈希；
5、完全哈希
使用二級結構，在每一級都會用全域哈希，第一級可能會有沖突，但是第二級就沒有了；
(1)、算法模型
(2)、算法分析：
時間復雜度：O(1)；
所需的存儲空間為：O(n)；
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
