We.TIL 21 : Set, Dictionary, Hash๐Ÿ™‰

๊น€๊ธฐ์šฑยท2020๋…„ 8์›” 11์ผ
0

We.TIL

๋ชฉ๋ก ๋ณด๊ธฐ
35/69

Set

What is Set?

Set๋Š” array๋‚˜ list ์ฒ˜๋Ÿผ ์ˆœ์—ด ์ž๋ฃŒ๊ตฌ์กฐ (collection) ์ž…๋‹ˆ๋‹ค.
ํ•˜์ง€๋งŒ set๋Š” ์ˆœ์„œ๋ผ๋Š” ๊ฐœ๋…์ด ์กด์žฌํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. Set์˜ ํŠน์ง•์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

  • ๋ฐ์ดํ„ฐ๋ฅผ ๋น„์ˆœ์ฐจ์ (unordered)์œผ๋กœ ์ €์žฅํ•  ์ˆ˜ ์žˆ๋Š” ์ˆœ์—ด ์ž๋ฃŒ๊ตฌ์กฐ (collection).
  • ์‚ฝ์ž…(insertion) ์ˆœ์„œ๋Œ€๋กœ ์ €์žฅ๋˜์ง€ ์•Š๋Š”๋‹ค.
    ์ฆ‰ ํŠน์ •ํ•œ ์ˆœ์„œ๋ฅผ ๊ธฐ๋Œ€ํ•  ์ˆ˜ ์—†๋Š” ์ž๋ฃŒ๊ตฌ์กฐ.
  • ์ˆ˜์ • ๊ฐ€๋Šฅํ•˜๋‹ค(mutable).
  • ๋™์ผํ•œ ๊ฐ’์„ ์—ฌ๋Ÿฌ๋ฒˆ ์‚ฝ์ž… ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค.
    ๋™์ผํ•œ ๊ฐ’์ด ์—ฌ๋Ÿฌ๋ฒˆ ์‚ฝ์ž… ๋˜๋ฉด ํ•˜๋‚˜์˜ ๊ฐ’๋งŒ ์ €์žฅ๋œ๋‹ค.
  • Fast Lookup์ด ํ•„์š”ํ• ๋•Œ ์ฃผ๋กœ ์“ฐ์ธ๋‹ค.

Array์™€ ๋‹ฌ๋ฆฌ set์€ ์š”์†Œ๋“ค์„ ์ˆœ์ฐจ์ ์œผ๋กœ ์ €์žฅํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. Set์—์„œ ์š”์†Œ๋“ค์ด ์ €์žฅ๋  ๋•Œ ์ˆœ์„œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

1) ์ €์žฅํ•  ์š”์†Œ์˜ ๊ฐ’์˜ hash ๊ฐ’์„ ๊ตฌํ•œ๋‹ค.
2) ํ•ด์‰ฌ๊ฐ’์— ํ•ด๋‹นํ•˜๋Š” ๊ณต๊ฐ„(bucket)์— ๊ฐ’์„ ์ €์žฅํ•œ๋‹ค.
์ด๋ ‡๊ฒŒ set๋Š” ์ €์žฅํ•˜๊ณ ์ž ํ•˜๋Š” ๊ฐ’์˜ ํ•ด์‰ฌ๊ฐ’์— ํ•ด๋‹นํ•˜๋Š” bucket์— ๊ฐ’์„ ์ €์žฅํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ˆœ์„œ๊ฐ€ ์—†๋‹ค. ์ˆœ์„œ๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์— indexing๋„ ์—†๋‹ค.
๊ทธ๋ฆฌ๊ณ  ํ•ด์‰ฌ๊ฐ’ ๊ธฐ๋ฐ˜์˜ bucket์— ์ €์žฅํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ค‘๋ณต๋œ ๊ฐ’์„ ์ €์žฅํ•  ์ˆ˜ ์—†๋Š”๊ฒƒ์ด๋‹ค.
ํ•ด์‰ฌ๊ฐ’์„ ๊ธฐ๋ฐ˜์œผ๋กœ ์ €์žฅํ•˜๊ธฐ ๋•Œ๋ฌธ์— look up ์ด ๊ต‰์žฅํžˆ ๋น ๋ฆ„.
Look up: ํŠน์ • ๊ฐ’์„ ํฌํ•จํ•˜๊ณ  ์žˆ๋Š”์ง€๋ฅผ ํ™•์ธ ํ•˜๋Š”๊ฒƒ ==> 5 in my_set
Set์˜ ์ด ๊ธธ์ด์™€ ์ƒ๊ด€์—†์ด ๋‹จ์ˆœํžˆ ํ•ด์‰ฌ๊ฐ’ ๊ณ„์‚ฐ ํ›„ ํ•ด๋‹น bucket์„ ํ™•์ธํ•˜๋ฉด ๋˜๋ฏ€๋กœ O(1)

hash๋Š” ๋‹จ๋ฐฉํ–ฅ (one way) ์•”ํ˜ธํ™” ์ž…๋‹ˆ๋‹ค. ๋‹จ๋ฐฉํ–ฅ์ด๋ž€ ํ•œ๋ฒˆ ์•”ํ˜ธํ™” ํ•˜๋ฉด ๋ณตํ˜ธํ™”๊ฐ€ ์•ˆ๋œ๋‹ค๋Š” ๋œป์ž…๋‹ˆ๋‹ค. ์‹ค์ œ ๊ฐ’์˜ ๊ธธ์ด์™€ ์ƒ๊ด€์—†์ด hash ๊ฐ’์„ ์ผ์ •ํ•œ ๊ธธ์ด๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค. ๊ทธ๋Ÿผ์œผ๋กœ Hash๋Š” ์ฃผ๋กœ ์ž„์˜์˜ ๊ธธ์ด๋ฅผ ๊ฐ–๋Š” ์ž„์˜์˜ ๋ฐ์ดํ„ฐ์— ๋Œ€ํ•ด ๊ณ ์ •๋œ ๊ธธ์ด์˜ ๋ฐ์ดํ„ฐ๋กœ ๋งคํ•‘ํ• ๋•Œ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.

When To Use Set?

1) ์ค‘๋ณต๋œ ๊ฐ’์„ ๊ณจ๋ผ๋‚ด์•ผ ํ•  ๋•Œ
2) ๋น ๋ฅธ look up ์„ ํ•ด์•ผ ํ•  ๋•Œ
3) ๊ทธ๋Ÿฌ๋ฉด์„œ ์ˆœ์„œ๋Š” ์ƒ๊ด€ ์—†์„ ๋•Œ

Dictionary

What is Dictionary?

Dictionary (๋‹ค๋ฅธ ์–ธ์–ด์—์„œ๋Š” hashmap ์ด๋‚˜ hash table์ด๋ผ๊ณ  ํ•˜๊ธฐ๋„ ํ•จ)๋Š” Key-value ํ˜•ํƒœ์˜ ๊ฐ’์„ ์ €์žฅํ•  ์ˆ˜ ์žˆ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ ์ž…๋‹ˆ๋‹ค. ์ด๋ฆ„์€ "์ •์šฐ์„ฑ" ๋“ฑ ์‹ค์ œ ๋ฐ์ดํ„ฐ ๊ฐ’๊ณผ ๋ฐ์ดํ„ฐ๋ฅผ ์„ค๋ช…ํ•˜๋Š” key์˜ ๋Œ€์‘ ๊ด€๊ณ„๋ฅผ ํ‘œํ˜„ํ• ๋•Œ ์œ ์šฉํ•ฉ๋‹ˆ๋‹ค.
Dictionary์˜ ํŠน์„ฑ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

  • Set๊ณผ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ํŠน์ • ์ˆœ์„œ๋Œ€๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ๋ฆฌํ„ดํ•˜์ง€ ์•Š๋Š”๋‹ค.
  • Key์˜ ๊ฐ’์€ ์ค‘๋ณต๋  ์ˆ˜ ์—†๋‹ค. ๋งŒ์ผ ์ค‘๋ณต๋œ key ๊ฐ€ ์žˆ์œผ๋ฉด ๋จผ์ € ์žˆ๋˜ key์™€ value๋ฅผ ๋Œ€์ฒดํ•œ๋‹ค.
  • ์ˆ˜์ • ๊ฐ€๋Šฅํ•˜๋‹ค(mutable).
  • set์™€ ๋น„์Šทํ•˜๊ฒŒ key ๊ฐ’์˜ ํ•ด์‰ฌ๊ฐ’์„ ๊ตฌํ•œ ํ›„ ํ•ด์‰ฌ๊ฐ’์— ์†ํ•ด์žˆ๋Š” bucket์— ๊ฐ’์„ ์ €์žฅํ•œ๋‹ค.
  • ๊ทธ๋Ÿผ์œผ๋กœ set์™€ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ์ˆœ์„œ๊ฐ€ ์—†๊ณ  ์ค‘๋ณต๋œ key ๊ฐ’์€ ํ—ˆ์šฉ ๋˜์ง€ ์•Š๋Š”๋‹ค.

When to Use Dictionary?
๋งˆ์น˜ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์ฒ˜๋Ÿผ ํ‚ค์™€ ๊ฐ’์„ ๋ฌถ์–ด์„œ ๋ฐ์ดํ„ฐ๋ฅผ ํ‘œํ˜„ํ•ด์•ผ ํ• ๋•Œ ์œ ์šฉํ•˜๋‹ค. ์‹ค์ œ๋กœ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์—์„œ ์ฝ์–ด๋“ค์ธ ๊ฐ’์„ dictionary๋กœ ๋ณ€ํ™˜ํ•ด์„œ ์‚ฌ์šฉ ์ž์ฃผ ํ•จ.

Hash

ํ•ด์‹œ๋ž€ ๋‹จ๋ฐฉํ–ฅ (one way) ์•”ํ˜ธํ™” ์ž…๋‹ˆ๋‹ค. ์ž…๋ ฅ ๋ฐ์ดํ„ฐ๋ฅผ ๋ณ€ํ™˜ํ•˜์—ฌ ์›๋ณธ ๋ฐ์ดํ„ฐ๋กœ ๋ณตํ˜ธํ™”ํ•  ์ˆ˜ ์—†๋„๋ก ํ•˜๋Š” ๊ณผ์ • ์ž…๋‹ˆ๋‹ค. SHA(๋ณด์•ˆ ํ•ด์‹œ ์•Œ๊ณ ๋ฆฌ์ฆ˜)์„ ์˜ˆ๋กœ ๋“ค์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. SHA ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•˜์—ฌ ๋ฌธ์ž์—ด ๋ฐ์ดํ„ฐ๋ฅผ ์ž…๋ ฅ๋ฐ›์•„์„œ ํ•ด์‹œ๊ฐ’์„ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
์‹ค์ œ ์ฝ”๋“œ๋กœ ํ•ด์‹œ ๊ฐ’์„ ๊ตฌํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ๋‹ค์Œ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•˜๊ณ  ์‹คํ–‰ํ•ด๋ณด์„ธ์š”.

import hashlib

def sha1_hash(input_str):
    
    hash_obj = hashlib.sha1(input_str.encode())
    hash_value = hash_obj.hexdigest()
    return hash_value


wecode_hash_value = sha1_hash('wecode')
print(wecode_hash_value)
print(len(wecode_hash_value))

hash_value_1234 = sha1_hash('1234')
print(hash_value_1234)
print(len(hash_value_1234))

์ด์ฒ˜๋Ÿผ hash ๊ฐ’์€ ์ผ์ •ํ•œ ๊ธธ์ด๋ฅผ ๊ฐ€์ง€๊ณ , ์ฃผ๋กœ ์ž„์˜์˜ ๊ธธ์ด๋ฅผ ๊ฐ–๋Š” ์ž„์˜์˜ ๋ฐ์ดํ„ฐ์— ๋Œ€ํ•ด ๊ณ ์ •๋œ ๊ธธ์ด์˜ ๋ฐ์ดํ„ฐ๋กœ ๋งคํ•‘ํ• ๋•Œ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.

ํ•ด์‹œํ•จ์ˆ˜๋Š” ๊ฐ™์€ ๋ฌธ์ž์—ด์— ๋Œ€ํ•ด์„œ๋Š” ๊ฐ™์€ ์ธ๋ฑ์Šค๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ•ด์‹œํ•จ์ˆ˜๋กœ ๊ตฌํ•œ ๋ฒ„ํ‚ท์˜ ์ธ๋ฑ์Šค๋ฅผ ์ €์žฅ ํ›„์—๋„ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

ํ•ด์‹œํ…Œ์ด๋ธ”์€ ํ•ด์‹œํ•จ์ˆ˜์™€ ๋ฒ„ํ‚ท(bucket)์˜ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ ์œ„์˜ wecode ์˜ ํ•ด์‹œ๊ฐ’์ธ '283463014a3f8ab829fcf9087ff85d50da1d1bb6' ์™€ '1234'์˜ ํ•ด์‹œ๊ฐ’์ธ '7110eda4d09e062aa5e4a390b0a572ac0d2c0220'์„ ๋ฒ„ํ‚ท์˜ ์ฃผ์†Œ์ธ ์ธ๋ฑ์Šค๋ฅผ ๊ตฌํ•  ๋•Œ ์‚ฌ์šฉํ•˜๊ธฐ์—๋Š” ๋ฌด๋ฆฌ๊ฐ€ ์žˆ์–ด ๋ณด์ž…๋‹ˆ๋‹ค.

๋ฒ„ํ‚ท์˜ ํฌ๊ธฐ์— ๋”ฐ๋ฅธ ์ธ๋ฑ์Šค๋กœ ๋ณ€ํ™˜ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ์ž…๋ ฅ๋œ ๋ฌธ์ž์—ด์˜ ๊ฐ์ž๋ฆฌ์˜ ์ˆซ์ž๋ฅผ ๋”ํ•˜๋Š” ๋ฐฉ์‹์ธ Digit folding ๊ณผ ๋น„ํŠธ์—ฐ์‚ฐ์„ ํ™œ์šฉํ•œ ๋ฐฉ๋ฒ•๋“ฑ ๋‹ค์–‘ํ•œ ๋ฐฉ๋ฒ•์ด ์žˆ์ง€๋งŒ ์šฐ๋ฆฌ๋Š” ์ด๋ฏธ SHA1 ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ํ•ด์‹œ๊ฐ’์„ ๊ตฌํ•˜์˜€์œผ๋ฏ€๋กœ ๊ฐ„๋‹จํ•˜๊ฒŒ ๋ฒ„ํ‚ท์˜ ์‚ฌ์ด์ฆˆ๋กœ ๋‚˜๋ˆ„๋Š” ๋ฐฉ๋ฒ•์ธ ๋‚˜๋ˆ—์…ˆ๋ฒ•์„ ์ ์šฉํ•˜๋ฉด ๋ฒ„ํ‚ท์˜ ์ธ๋ฑ์Šค๋ฅผ ์ดˆ๊ณผํ•˜์ง€ ์•Š๋Š” ์ธ๋ฑ์Šค๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋‚˜๋ˆ—์…ˆ ๋ฒ• : ์ฃผ์–ด์ง„ ํ•ด์‰ฌ๊ฐ’์„ ํ…Œ์ด๋ธ”ํฌ๊ธฐ(๋ฒ„ํ‚ท์˜๊ฐœ์ˆ˜)๋งŒํผ ๋‚˜๋ˆ ์ค€ ํ›„ ๋‚˜์˜จ ๊ฐ’์„ ์ธ๋ฑ์Šค๋กœ ์ฃผ๋Š” ๋ฐฉ์‹ ์˜ˆ๋ฅผ๋“ค์–ด SHA1์˜ ํ•œ๊ณ„๋ฐ”์ดํŠธ์ธ 160์— ํ•ด์‰ฌ๊ฐ’ 4351์ด ์ฃผ์–ด์ง„๋‹ค๋ฉด ์ธ๋ฑ์Šค๋Š” 4351%160(๋‚˜๋จธ์ง€๊ฐ’)์ธ 31๋กœ ๋ถ€์—ฌ๋œ๋‹ค.

Linear probing(์„ ํ˜•ํƒ์‚ฌ) : ํ•ด์‰ฌ๊ฐ’ ์ถฉ๋Œ์„ ๋ฐฉ์ง€ํ•˜๋Š” ๋ฐฉ๋ฒ• ์ค‘ ํ•˜๋‚˜๋กœ ๋‚˜์˜จ ์ธ๋ฑ์Šค์— ์ด๋ฏธ ๋‹ค๋ฅธ ํ•ด์‹œ๊ฐ’์ด ๋“ค์–ด๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ ๊ณ ์ •์ ์œผ๋กœ ์ธ๋ฑ์Šค๋ฅผ 1์”ฉ ์ฆ๊ฐ€์‹œ์ผœ ๋นˆ ๋ฒ„ํ‚ท์— ๋„ฃ์–ด ์ฃผ๋Š” ๋ฐฉ์‹์ด๋‹ค.

๊ฐ„๋‹จํ•œ ์‹์œผ๋กœ๋Š”
(hash+count)%(self.bucket)
count += 1 ๋“ฑ์œผ๋กœ
1 ์”ฉ ์ฆ๊ฐ€์‹œ์ผœ์ฃผ๋Š” ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค.

profile
์–ด๋ ค์šด ๊ฒƒ์€ ์—†๋‹ค, ๋‹ค๋งŒ ์•„์ง ์ต์ˆ™์น˜์•Š์„๋ฟ์ด๋‹ค.

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