資料結構›Ch8 雜湊
第 21 題/共 37 題
◀ DS 21/37
21. Bloom Filter、Hash Function
#DS-08-021中Bloom FilterHash Function
題組題幹(本題:(a),共 2 小題)點擊展開

Given the following bloom filter.

[0][1][2][3][4][5][6][7][8][9][10][11][12][13][14]
110111110100010

[3%] Assume that the bloom filter has 3 hash functions f1(k)f_1(k), f2(k)f_2(k), and f3(k)f_3(k):

f1(k)=(3k) mod m,f2(k)=(2k+1) mod m,f3(k)=k2 mod m,f_1(k) = (3k) \bmod m,\quad f_2(k) = (2k+1) \bmod m,\quad f_3(k) = k^2 \bmod m,

where kk represents the key and mm is the size of bit array for the bloom filter. Which of the following statements is true?

📄 成大113
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch8 雜湊
本章題號 · 21–37 / 37