# ํ•ด์‹œ(Hash)



๋ฐ์ดํ„ฐ๋ฅผ ํšจ์œจ์ ์œผ๋กœ ๊ด€๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด, ์ž„์˜์˜ ๊ธธ์ด ๋ฐ์ดํ„ฐ๋ฅผ ๊ณ ์ •๋œ ๊ธธ์ด์˜ ๋ฐ์ดํ„ฐ๋กœ ๋งคํ•‘ํ•˜๋Š” ๊ฒƒ

ํ•ด์‹œ ํ•จ์ˆ˜๋ฅผ ๊ตฌํ˜„ํ•˜์—ฌ ๋ฐ์ดํ„ฐ ๊ฐ’์„ ํ•ด์‹œ ๊ฐ’์œผ๋กœ ๋งคํ•‘ํ•œ๋‹ค.


Lee โ†’ ํ•ด์‹ฑํ•จ์ˆ˜ โ†’ 5
Kim โ†’ ํ•ด์‹ฑํ•จ์ˆ˜ โ†’ 3
Park โ†’ ํ•ด์‹ฑํ•จ์ˆ˜ โ†’ 2
...
Chun โ†’ ํ•ด์‹ฑํ•จ์ˆ˜ โ†’ 5 // Lee์™€ ํ•ด์‹ฑ๊ฐ’ ์ถฉ๋Œ

๊ฒฐ๊ตญ ๋ฐ์ดํ„ฐ๊ฐ€ ๋งŽ์•„์ง€๋ฉด, ๋‹ค๋ฅธ ๋ฐ์ดํ„ฐ๊ฐ€ ๊ฐ™์€ ํ•ด์‹œ ๊ฐ’์œผ๋กœ ์ถฉ๋Œ๋‚˜๋Š” ํ˜„์ƒ์ด ๋ฐœ์ƒํ•จ 'collision' ํ˜„์ƒ

๊ทธ๋ž˜๋„ ํ•ด์‹œ ํ…Œ์ด๋ธ”์„ ์“ฐ๋Š” ์ด์œ ๋Š”?

์ ์€ ์ž์›์œผ๋กœ ๋งŽ์€ ๋ฐ์ดํ„ฐ๋ฅผ ํšจ์œจ์ ์œผ๋กœ ๊ด€๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด

ํ•˜๋“œ๋””์Šคํฌ๋‚˜, ํด๋ผ์šฐ๋“œ์— ์กด์žฌํ•˜๋Š” ๋ฌดํ•œํ•œ ๋ฐ์ดํ„ฐ๋“ค์„ ์œ ํ•œํ•œ ๊ฐœ์ˆ˜์˜ ํ•ด์‹œ๊ฐ’์œผ๋กœ ๋งคํ•‘ํ•˜๋ฉด ์ž‘์€ ๋ฉ”๋ชจ๋ฆฌ๋กœ๋„ ํ”„๋กœ์„ธ์Šค ๊ด€๋ฆฌ๊ฐ€ ๊ฐ€๋Šฅํ•ด์ง!

  • ์–ธ์ œ๋‚˜ ๋™์ผํ•œ ํ•ด์‹œ๊ฐ’ ๋ฆฌํ„ด, index๋ฅผ ์•Œ๋ฉด ๋น ๋ฅธ ๋ฐ์ดํ„ฐ ๊ฒ€์ƒ‰์ด ๊ฐ€๋Šฅํ•ด์ง
  • ํ•ด์‹œํ…Œ์ด๋ธ”์˜ ์‹œ๊ฐ„๋ณต์žก๋„ O(1) - (์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ๋Š” O(logN))

# ์ถฉ๋Œ ๋ฌธ์ œ ํ•ด๊ฒฐ

  1. ์ฒด์ด๋‹ : ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋กœ ๋…ธ๋“œ๋ฅผ ๊ณ„์† ์ถ”๊ฐ€ํ•ด๋‚˜๊ฐ€๋Š” ๋ฐฉ์‹ (์ œํ•œ ์—†์ด ๊ณ„์† ์—ฐ๊ฒฐ ๊ฐ€๋Šฅ, but ๋ฉ”๋ชจ๋ฆฌ ๋ฌธ์ œ)

  2. Open Addressing : ํ•ด์‹œ ํ•จ์ˆ˜๋กœ ์–ป์€ ์ฃผ์†Œ๊ฐ€ ์•„๋‹Œ ๋‹ค๋ฅธ ์ฃผ์†Œ์— ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•  ์ˆ˜ ์žˆ๋„๋ก ํ—ˆ์šฉ (ํ•ด๋‹น ํ‚ค ๊ฐ’์— ์ €์žฅ๋˜์–ด์žˆ์œผ๋ฉด ๋‹ค์Œ ์ฃผ์†Œ์— ์ €์žฅ)

  3. ์„ ํ˜• ํƒ์‚ฌ : ์ •ํ•ด์ง„ ๊ณ ์ • ํญ์œผ๋กœ ์˜ฎ๊ฒจ ํ•ด์‹œ๊ฐ’์˜ ์ค‘๋ณต์„ ํ”ผํ•จ

  4. ์ œ๊ณฑ ํƒ์‚ฌ : ์ •ํ•ด์ง„ ๊ณ ์ • ํญ์„ ์ œ๊ณฑ์ˆ˜๋กœ ์˜ฎ๊ฒจ ํ•ด์‹œ๊ฐ’์˜ ์ค‘๋ณต์„ ํ”ผํ•จ



# [์ฐธ๊ณ ์ž๋ฃŒ]

์ตœ์ข… ์ˆ˜์ • : 12/17/2022, 7:23:59 AM