What is Set?
Set๋ array๋ list ์ฒ๋ผ ์์ด ์๋ฃ๊ตฌ์กฐ (collection) ์
๋๋ค.
ํ์ง๋ง set๋ ์์๋ผ๋ ๊ฐ๋
์ด ์กด์ฌํ์ง ์์ต๋๋ค. Set์ ํน์ง์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
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) ๊ทธ๋ฌ๋ฉด์ ์์๋ ์๊ด ์์ ๋
What is Dictionary?
Dictionary (๋ค๋ฅธ ์ธ์ด์์๋ hashmap ์ด๋ hash table์ด๋ผ๊ณ ํ๊ธฐ๋ ํจ)๋ Key-value ํํ์ ๊ฐ์ ์ ์ฅํ ์ ์๋ ์๋ฃ๊ตฌ์กฐ ์
๋๋ค. ์ด๋ฆ์ "์ ์ฐ์ฑ" ๋ฑ ์ค์ ๋ฐ์ดํฐ ๊ฐ๊ณผ ๋ฐ์ดํฐ๋ฅผ ์ค๋ช
ํ๋ key์ ๋์ ๊ด๊ณ๋ฅผ ํํํ ๋ ์ ์ฉํฉ๋๋ค.
Dictionary์ ํน์ฑ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
When to Use Dictionary?
๋ง์น ๋ฐ์ดํฐ๋ฒ ์ด์ค ์ฒ๋ผ ํค์ ๊ฐ์ ๋ฌถ์ด์ ๋ฐ์ดํฐ๋ฅผ ํํํด์ผ ํ ๋ ์ ์ฉํ๋ค. ์ค์ ๋ก ๋ฐ์ดํฐ๋ฒ ์ด์ค ์์ ์ฝ์ด๋ค์ธ ๊ฐ์ dictionary๋ก ๋ณํํด์ ์ฌ์ฉ ์์ฃผ ํจ.
ํด์๋ ๋จ๋ฐฉํฅ (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 ์ฉ ์ฆ๊ฐ์์ผ์ฃผ๋ ๋ฐฉ๋ฒ์ด ์๋ค.