Hash, Hash Map, Hash Table

OUOยท2022๋…„ 5์›” 30์ผ
0
post-thumbnail

๐Ÿ˜œ Hash Table ์ด๋ž€?

์—ฐ๊ด€๋ฐฐ์—ด ๊ตฌ์กฐ๋ฅผ ์ด์šฉํ•ด key์— value๋ฅผ ์ €์žฅํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ
= key-value๋กœ ์ด๋ฃจ์–ด์ง„ ์ž๋ฃŒ๊ตฌ์กฐ

๐Ÿ“์—ฐ๊ด€๋ฐฐ์—ด(associative array) ๊ตฌ์กฐ๋ž€?

key 1๊ฐœ์™€ value 1๊ฐœ๊ฐ€ 1:1๋กœ ์—ฐ๊ด€๋˜์–ด ์žˆ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ
= key๋ฅผ ์ด์šฉํ•ด value๋ฅผ ๋„์ถœ

๐Ÿ˜œ Hash Table์˜ ๊ตฌ์กฐ

hash table์€ Key ํ‚ค, Hash Function ํ•ด์‹œ ํ•จ์ˆ˜, Hash ํ•ด์‹œ, Value ๊ฐ’, Bucket(slot) ์ €์žฅ์†Œ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์Œ

key๋Š” hash function์„ ํ†ตํ•ด hash๋กœ ๋ณ€๊ฒฝ, hash๋Š” value์™€ ๋งค์นญ๋˜์–ด ์ €์žฅ์†Œ์— ์ €์žฅ

key
1. ๊ณ ์œ ํ•œ ๊ฐ’, hash function์˜ input
2. key๊ฐ’์„ ๊ทธ๋Œ€๋กœ ์ €์žฅ์†Œ์˜ index๋กœ ์‚ฌ์šฉํ•  ๊ฒฝ์šฐ key์˜ ๊ธธ์ด๋งŒํผ์˜ ์ •๋ณด๋ฅผ ์ €์žฅํ•ด์•ผ ํ•˜๋Š” ๊ณต๊ฐ„๋„ ๋งˆ๋ จํ•ด์•ผ ํ•˜๋ฏ€๋กœ ๊ณ ์ •๋œ ๊ธธ์ด์˜ hash๋กœ ๋ณ€๊ฒฝ

hash function
1. key๋ฅผ hash๋กœ ๋ฐ”๊ฟ”์ฃผ๋Š” ์—ญํ• 
2. ๋‹ค์–‘ํ•œ ๊ธธ์ด๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” key๋ฅผ ์ผ์ •ํ•œ ๊ธธ์ด๋ฅผ ๊ฐ€์ง€๋Š” hash๋กœ ๋ณ€๊ฒฝํ•˜์—ฌ ์ €์žฅ์†Œ๋ฅผ ํšจ์œจ์ ์œผ๋กœ ์šด์˜ํ•  ์ˆ˜ ์žˆ๋„๋ก ๋„์™€์คŒ
3. ์„œ๋กœ ๋‹ค๋ฅธ key -> ๊ฐ™์€ hash๊ฐ€ ๋˜๋Š” ๊ฒฝ์šฐ = ํ•ด์‰ฌ ์ถฉ๋Œ
(ํ•ด์‰ฌ ์ถฉ๋Œ์„ ์ผ์œผํ‚ค๋Š” ํ™•๋ฅ ์„ ์ตœ๋Œ€ํ•œ ์ค„์ด๋Š” ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“œ๋Š”๊ฒƒ์ด ์ค‘์š”ํ•จ)

value
1. ์ €์žฅ์†Œ(๋ฒ„ํ‚ท, ์Šฌ๋กฏ)์— ์ตœ์ข…์ ์œผ๋กœ ์ €์žฅ๋˜๋Š” ๊ฐ’
2. key์™€ ๋งค์นญ๋˜์–ด ์ €์žฅ, ์‚ญ์ œ, ๊ฒ€์ƒ‰, ์ ‘๊ทผ์ด ๊ฐ€๋Šฅ

hash
1. hash function์˜ ๊ฒฐ๊ณผ๋ฌผ, ์ €์žฅ์†Œ์—์„œ value์™€ ๋งค์นญ๋˜์–ด ์ €์žฅ๋จ

๐Ÿ“์ •๋ฆฌ

Hash = ์ธ๋ฑ์Šค, Hash Function = key->hash๋กœ ๋งŒ๋“ค์–ด์ฃผ๋Š” function, Hash Table = hash๋ฅผ ์ฃผ์†Œ๋กœ ์‚ผ์•„ ๋ฐ์ดํ„ฐ ์ €์žฅํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ

  1. ๋ฐ์ดํ„ฐ๋“ค์ด ํ•ด์‹œํ•จ์ˆ˜์— ์˜ํ•˜์—ฌ ๋ถ„๋ฅ˜๊ฐ€ ๋œ๋‹ค
  2. ๋ถ„๋ฅ˜๋œ ๋ฐ์ดํ„ฐ๋“ค์€ ํ•ด์‹œ ํ•จ์ˆ˜์— ์˜ํ•ด์„œ ํ•ด์‹œ ํ…Œ์ด๋ธ”์•ˆ์— ์˜ˆ์˜๊ฒŒ ๊ทœ์น™์— ์˜ํ•ด์„œ ๋“ค์–ด๊ฐ€๊ฒŒ ๋œ๋‹ค => ํ•ด์‹ฑ
profile
develoops!er

0๊ฐœ์˜ ๋Œ“๊ธ€