1. 問題
問題同《簡(jiǎn)單散列函數(shù)算法》，這個(gè)例子并不是特別恰當(dāng)，當(dāng)在于簡(jiǎn)單，數(shù)字小，方便驗(yàn)證，方便理解，特別是計(jì)算概率的部分。
設(shè)有10個(gè)非負(fù)整數(shù)，用不多于20個(gè)的儲(chǔ)存單元來(lái)存放，如何存放這10個(gè)數(shù)，使得搜索其中的某一個(gè)數(shù)時(shí)，在儲(chǔ)存單元中查找的次數(shù)最少？
問題類似于，有10個(gè)帶號(hào)碼的球，放到編號(hào)為{0, 1, 2, …, 19}共20個(gè)盒子中，每個(gè)盒子最多放一個(gè)，問如何放，使能夠用最少的次數(shù)打開盒子，知道任一個(gè)球所在的盒子編號(hào)？
2. 分析
《散列函數(shù)之單散列算法解決沖突問題》中，我們提到用單散列算法來(lái)解決沖突，比簡(jiǎn)單散列算法沖突的比率有所降低，但18%的沖突率，對(duì)于實(shí)際應(yīng)用來(lái)說(shuō)還是略偏高，《初等數(shù)論及其應(yīng)用》中，說(shuō)明是從另一個(gè)角度來(lái)說(shuō)明該沖突率高的原因。
設(shè) h0(k) ≡ k (mod m), k = 球號(hào)， m = 盒子數(shù)量
hj(k) ≡ h0(k) + j，0<= j < m, hj(k) 表示發(fā)生 j 次沖突后，球所放入的盒子編號(hào)
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無(wú)線安全]玩轉(zhuǎn)無(wú)線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來(lái)看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式