# ํด์(Hash)
๋ฐ์ดํฐ๋ฅผ ํจ์จ์ ์ผ๋ก ๊ด๋ฆฌํ๊ธฐ ์ํด, ์์์ ๊ธธ์ด ๋ฐ์ดํฐ๋ฅผ ๊ณ ์ ๋ ๊ธธ์ด์ ๋ฐ์ดํฐ๋ก ๋งคํํ๋ ๊ฒ
ํด์ ํจ์๋ฅผ ๊ตฌํํ์ฌ ๋ฐ์ดํฐ ๊ฐ์ ํด์ ๊ฐ์ผ๋ก ๋งคํํ๋ค.
Lee โ ํด์ฑํจ์ โ 5
Kim โ ํด์ฑํจ์ โ 3
Park โ ํด์ฑํจ์ โ 2
...
Chun โ ํด์ฑํจ์ โ 5 // Lee์ ํด์ฑ๊ฐ ์ถฉ๋
๊ฒฐ๊ตญ ๋ฐ์ดํฐ๊ฐ ๋ง์์ง๋ฉด, ๋ค๋ฅธ ๋ฐ์ดํฐ๊ฐ ๊ฐ์ ํด์ ๊ฐ์ผ๋ก ์ถฉ๋๋๋ ํ์์ด ๋ฐ์ํจ 'collision' ํ์
๊ทธ๋๋ ํด์ ํ ์ด๋ธ์ ์ฐ๋ ์ด์ ๋?
์ ์ ์์์ผ๋ก ๋ง์ ๋ฐ์ดํฐ๋ฅผ ํจ์จ์ ์ผ๋ก ๊ด๋ฆฌํ๊ธฐ ์ํด
ํ๋๋์คํฌ๋, ํด๋ผ์ฐ๋์ ์กด์ฌํ๋ ๋ฌดํํ ๋ฐ์ดํฐ๋ค์ ์ ํํ ๊ฐ์์ ํด์๊ฐ์ผ๋ก ๋งคํํ๋ฉด ์์ ๋ฉ๋ชจ๋ฆฌ๋ก๋ ํ๋ก์ธ์ค ๊ด๋ฆฌ๊ฐ ๊ฐ๋ฅํด์ง!
- ์ธ์ ๋ ๋์ผํ ํด์๊ฐ ๋ฆฌํด, index๋ฅผ ์๋ฉด ๋น ๋ฅธ ๋ฐ์ดํฐ ๊ฒ์์ด ๊ฐ๋ฅํด์ง
- ํด์ํ ์ด๋ธ์ ์๊ฐ๋ณต์ก๋ O(1) - (์ด์งํ์ํธ๋ฆฌ๋ O(logN))
# ์ถฉ๋ ๋ฌธ์ ํด๊ฒฐ
์ฒด์ด๋ : ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ก ๋ ธ๋๋ฅผ ๊ณ์ ์ถ๊ฐํด๋๊ฐ๋ ๋ฐฉ์ (์ ํ ์์ด ๊ณ์ ์ฐ๊ฒฐ ๊ฐ๋ฅ, but ๋ฉ๋ชจ๋ฆฌ ๋ฌธ์ )
Open Addressing : ํด์ ํจ์๋ก ์ป์ ์ฃผ์๊ฐ ์๋ ๋ค๋ฅธ ์ฃผ์์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ ์ ์๋๋ก ํ์ฉ (ํด๋น ํค ๊ฐ์ ์ ์ฅ๋์ด์์ผ๋ฉด ๋ค์ ์ฃผ์์ ์ ์ฅ)
์ ํ ํ์ฌ : ์ ํด์ง ๊ณ ์ ํญ์ผ๋ก ์ฎ๊ฒจ ํด์๊ฐ์ ์ค๋ณต์ ํผํจ
์ ๊ณฑ ํ์ฌ : ์ ํด์ง ๊ณ ์ ํญ์ ์ ๊ณฑ์๋ก ์ฎ๊ฒจ ํด์๊ฐ์ ์ค๋ณต์ ํผํจ