๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

ํ•ด์‹ฑ1

13-1๊ฐ•. ํ•ด์Š(Hashing) 1 SUHA(Simple Uniform Hashing Assumption) - ๊ฐ๊ฐ์˜ ํ‚ค๊ฐ€ ๋ชจ๋“  ์Šฌ๋กฏ๋“ค์— ๊ท ๋“ฑํ•œ ํ™•๋ฅ ๋กœ() ๋…๋ฆฝ์ ์œผ๋กœ(independently) ํ•ด์Š๋œ๋‹ค๋Š” ๊ฐ€์ • => ์‚ฌ์‹ค ํ˜„์‹ค์ ์ด์ง€ ์•Š๋‹ค. - ์„ฑ๋Šฅ๋ถ„์„์„ ์œ„ํ•ด์„œ ์ฃผ๋กœ ํ•˜๋Š” ๊ฐ€์ •์ผ ๋ฟ - hash ํ•จ์ˆ˜๋Š” deterministicํ•˜๋ฏ€๋กœ ํ˜„์‹ค์—์„œ๋Š” ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค - Load factor alpha = n/m: - n : ํ…Œ์ด๋ธ”์— ์ €์žฅ๋  ํ‚ค์˜ ๊ฐฏ์ˆ˜ - m : ํ•ด์‰ฌํ…Œ์ด๋ธ”์˜ ํฌ๊ธฐ, ์ฆ‰ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ๊นƒ์ˆ˜ - ๊ฐ ์Šฌ๋กฏ์— ์ €์žฅ๋œ ํ‚ค์˜ ํ‰๊ท  ๊ฐฏ์ˆ˜ - ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ T[j]์˜ ๊ธธ์ด๋ฅผ Nj๋ผ๊ณ  ํ•˜๋ฉด, E[Nj] = alpha - ๋งŒ์•ฝ n = O(m)์ด๋ฉด ํ‰๊ท ๊ฒ€์ƒ‰์‹œ๊ฐ„์€ O(1) 2020. 11. 24.

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”