๐ ์ด ํฌ์คํ ์์๋ Hash Tables์ ๋ํด ์ ๋ฆฌํ์์ต๋๋ค.
๐ฅ Hash Tables ์ด๋?
๐ฅ Hash Tables vs Arrays
๐ฅ Hash Collisions
โ๏ธ ์ฌ์ ์ด ์ํ๋ฒณ ์์ผ๋ก ๋์ด ์์ง ์๋ค๋ฉด, ๋ด๊ฐ ์ํ๋ ๋จ์ด์ ๋ป์ ์๊ธฐ ์ํด ์ฒ์๋ถํฐ ์์ฐจ์ ์ผ๋ก ํ์ธํด์ผ ํ๋ค. ํ๋ํ๋ ๋ชจ๋ ํ์ธํด์ผํ๋ ์ด ๊ณผ์ ์ ๋จ์ ํ์๊ณผ ๊ฐ๊ณ , ์๊ฐ ๋ณต์ก๋๋ O(N)์ด๋ค.
โ๏ธ ๋คํ์ค๋ฝ๊ฒ๋ ์ฌ์ ์ ์ํ๋ฒณ์์ผ๋ก ๋์ด์๊ธฐ ๋๋ฌธ์ ์ด์ง ํ์์ด ๊ฐ๋ฅํ๋ค. ์ด ๊ฒฝ์ฐ์ ์๊ฐ ๋ณต์ก๋๋ O(logN)์ด๋ค.
โ๏ธ ์ด๋ฒ์๋ ์ฌ์ ์ด ์๋๋ผ, ๋งํธ์์ ๊ณ์ฐ์์ ํ๊ณ ์๋ค๊ณ ์๊ฐํด๋ณด์. ๋ฌผํ๋ณ๋ก ๊ฐ๊ฒฉ์ด ์ ํ์๋ ์ฅ๋ถ๊ฐ ์์ ๋, ๋จ์ ํ์์ O(N)์ด๊ณ , ์ด์งํ์์ํ๋ฉด O(logN)์ ์๊ฐ๋ณต์ก๋๊ฐ ํ์ํ๋ค.
โ๏ธ 1์ด์ ํ๋ชฉ 10๊ฐ๋ฅผ ์ฝ์ ์ ์๋ค๊ณ ๊ฐ์ ํ๋ฉด, ํ๋งค์ค์ธ ๋ฌผ๊ฑด 1๊ฐ์ ๊ฐ์ ์์๋ด๋๋ฐ ์๋์ ๊ฐ์ ์๊ฐ์ด ํ์ํ๋ค.
โ๏ธ ๋ฐ๋ผ์ O(logN)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ ์ด์ง ํ์ ๋ํ ์ด๋ฌํ ์ํฉ์์๋ ํจ์จ์ ์ธ ๋ฐฉ์์ด ์๋๋ค. 10000๊ฐ์ ํ๋ชฉ์ ํ๋งค ์ค์ด๋ผ๋ฉด ๊ณ์ฐ์์ด 1๊ฐ์ ๋ฌผํ์ ๊ฐ๊ฒฉ๋ง์ ํ์ธํ๋๋ฐ์๋ ์ต๋ 2์ด์ ์๊ฐ์ ์์๋๊ธฐ ๋๋ฌธ์ด๋ค.
โ๏ธ ์ด์ ๋ ํจ์จ์ ์ธ ๋ฐฉ์์ ์๋ฃ๊ตฌ์กฐ๊ฐ ํ์ํ๋ค. ์ด๋ฅผ ๊ฐ๋ฅํ๊ฒํ๋ ๊ฒ์ด ํด์ฌ๋ค. ํด์ฌ๊ฐ ์ผ๋ง๋ ๋น ๋ฅธ์ง๋ ๋ค์์ ์ดํด๋ณด๊ฒ ๋ค.
โ๏ธ ํด์ฌ ํ ์ด๋ธ์ ํค(key)์ ๊ฐ์(value)๋ฅผ ์ ์ฅํ๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ๋ก ํค(key) ๊ฐ์ ๋ง์น index์ฒ๋ผ ์์ฉํ์ฌ ๊ฐ(value)์ ์ฝ์ ์ ์๊ธฐ ๋๋ฌธ์ ๋น ๋ฅด๋ค.
โ๏ธ ์ด๋ฏธ python์์๋ dictionary๋ผ๋ ๋ฐ์ดํฐ ํ์ ์ด ์ด๋ฅผ ์ง์ํ๊ณ ์๋ค. ์ฆ, python์์๋ ํด์ฌ ํ ์ด๋ธ์ ๋ณ๋ ๊ตฌํํ ํ์ ์์ด ๋์ ๋๋ฆฌ๋ฅผ ์ฌ์ฉํ ์ ์๊ณ , ๋์ ๋๋ฆฌ ๋ด๋ถ์ ์ผ๋ก ํด์ฌ ํ ์ด๋ธ์ ๊ตฌ์กฐ๋ฅผ ๊ฐ๊ณ ์๋ค.
โ๏ธ ํด์ฌ์ ๋ํ์ ์ธ ์ฅ์ ์ผ๋ก๋ ๋ฐ์ดํฐ๋ฅผ Create/Read ํ๋ ์๋๊ฐ ๋น ๋ฅด๊ณ , ์ด๋ฏธ Key๊ฐ ์กด์ฌํ๋์ง ์ค๋ณต์ ์ฒ๋ฆฌํ๊ธฐ๊ฐ ์ฝ๋ค.
โ๏ธ ๋จ์ ์ผ๋ก๋ ์ถฉ๋ถํ ์ ์ฅ ๊ณต๊ฐ์ ํ๋ณดํด๋์ด์ผํ๊ธฐ ๋๋ฌธ์ ๋น๊ต์ ์ ์ฅ ๊ณต๊ฐ์ด ๋ง์ด ํ์ํ๊ณ , ์ฌ๋ฌ Key์ ํด๋นํ๋ ์ฃผ์๊ฐ ๋์ผํ ๊ฒฝ์ฐ ์ถฉ๋์ ๋ง๊ธฐ ์ํ ๋ฐฉํธ์ด ํ์ํ๋ค. ์ด๋ ์ถํ ๋ค๋ค๋ณด๊ฒ ๋ค.
โ๏ธ ์ด์ ํด์ฌ ํ ์ด๋ธ์ ์ฃผ ์ฉ๋๋ CRUD๊ฐ ๋น๋ฒํ ๊ฒฝ์ฐ, ๊ฒ์์ด ์์ฃผ ์ผ์ด๋๋ ๊ฒฝ์ฐ, ์บ์ฌ๋ฅผ ๊ตฌํํ ๋ ํ์ฉ๋๋ค.
โ๏ธ ์๋ฅผ ๋ค์ด, ์ค๋งํธํฐ์ ์ฃผ์๋ก์ ํด์ฌ๋ก ๊ฐ๋ ๊ณผ ๋์ผํ๋ค. ์ฌ๋์ ์ฃผ์๋ก์์ ๊ฒ์ํ๋ฉด, ์ ํ๋ฒํธ, ์ฃผ์, email ๋ฑ์ ๋ชจ๋ ๋น ๋ฅด๊ฒ ํ์ธํ ์ ์๋ค.
โ๏ธ ๋ฟ๋ง์๋๋ผ ์์์ ์ ๋ฆฌํ Domain๊ณผ IP Address์ ๊ด๊ณ๋ ์ด๋ฌํ ํด์ฌ๋ก ์ด๋ค์ ธ์๋ค.
โ๏ธ hash : ์์์ ๊ฐ์ ๊ณ ์ ๊ธธ์ด๋ก ๋ณํํ๋ ๊ฒ
โ๏ธ hash table : ํค ๊ฐ์ ์ฐ์ฐ์ ์ํด ์ง์ ์ ๊ทผ์ด ๊ฐ๋ฅํ ๋ฐ์ดํฐ ๊ตฌ์กฐ
โ๏ธ hash function : Key์ ๋ํด ์ฐ์ ์ฐ์ฐ์ ์ ์ฉํด ํด์ฌ ๊ฐ์ผ๋ก ๋ณํํด์ฃผ๋ ํจ์
โ๏ธ hash value : Key๋ฅผ ํด์ฑ ํจ์์ ๋์ ํ์ฌ ๋ฐํ๋๋ ๊ฒ์ ํด์ฌ ๊ฐ์ด๋ผํ๊ณ , ์ด๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ํ ์ด๋ธ์์ ํด๋น Key์ ๋ํ ๋ฐ์ดํฐ ์์น๋ฅผ ํ์
โ๏ธ slot : ํ๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ ์ ์๋ ๊ณต๊ฐ
โ๏ธ ํด์ฌ๋ key๊ฐ์ ํตํด value๋ฅผ ๋ฐ๋ก ์ฝ์ด์ฌ ์ ์๊ธฐ ๋๋ฌธ์ ์ฅ๋ถ์ ํ๋ชฉ์ด ๋ฌดํ๋๋ก ๋์ด๋๋คํด๋ O(1)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
โ๏ธ ์ฌ์ค, O(1)์ด๋ผ๋ ์๊ฐ๋ณต์ก๋๋ Key๊ฐ์ ํด์ฌ ํจ์์ ๋ฃ์์ ๋, ์ถฉ๋์ด ๋ฐ์๋์ง ์์ ๋(๋ฐํ๋๋ ํด์ฌ ๊ฐ์ด ์ค๋ณต์ด ์์ ๋)์ ํด๋น๋๋ค. ์ด์ ๋ํด์๋ ์๋์ ๋ค์ ์๊ธฐํด๋ณด๋๋ก ํ์.
โ๏ธ 10์๋ฆฌ์ ๊ฐ๋จํ ํด์ฌ ํ ์ด๋ธ์ ๋ฐฐ์ด์ ์ฌ์ฉํ์ฌ ์๋์ฒ๋ผ ๋ง๋ค์ด ๋ณผ ์ ์๋ค.
# ๋น ํด์ฌ ํ ์ด๋ธ ๋ง๋ค๊ธฐ hash_table = list([0 for i in range(10)]) print(hash_table) # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
โ๏ธ ๊ฐ๋จ ํด์ฌ ํ ์ด๋ธ ๊ตฌํ์ด๊ธฐ ๋๋ฌธ์ division ๋ฐฉ์์ผ๋ก ํด์ฌ ํจ์๊ฐ ์๋์ฒ๋ผ ์กด์ฌํ๋ค๊ณ ๊ฐ์ ํด๋ณด์.
# ๊ฐ๋จ ํด์ฌ ํจ์ # Division ๋ฐฉ์ : ๋๋๊ธฐ๋ฅผ ํตํ ๋๋จธ์ง ๊ฐ์ ์ฌ์ฉํ๋ ๊ธฐ๋ฒ def hash_func(key): return key % 5 # ๐ ์ด๋ค key๊ฐ์ด ๋ค์ด์ค๋ฉด, ์ด๋ฅผ 5๋ก ๋๋ ๋๋จธ์ง๋ฅผ ๋ฐํํด์!
โ๏ธ ํด์ฌ ํ ์ด๋ธ์ ๊ฐ์ ์ ์ฅํ๋ ํจ์๋ ์๋ ์ฒ๋ผ ์์ฑํ ์ ์๋ค. key๊ฐ์ด string์ด๊ธฐ ๋๋ฌธ์ ord๋ก ์ซ์๋ก ๋ณํ ํ, index๊ฐ์ ๊ตฌํ๊ธฐ ์ํด ํด์ฌ ํจ์์ ๋ฃ๋๋ค.
def storage_data(data, value): # ๐ ํค์ ์ ์ฅํ ๋ฐ์ดํฐ๋ฅผ ๋ฐ์ key = ord(data[0]) # ๐ ํค๋ฅผ ํด์ฌํจ์์ ๋ฃ์ด ์ฐ์ฐํ๊ธฐ ์ํด ์ซ์๋ก ๋ณํ hash_address = hash_func(key) # ๐ ํด์ฌ ํจ์ ์๋ํ์ฌ ํด์ฌ๊ฐ(ํด์ฌ์ฃผ์) ์ป์ hash_table[hash_address] = value # ๐ ํด์ฌ ์ฃผ์๋ฅผ index๋กํ์ฌ ๋ฐ์ดํฐ๋ฅผ ํ ์ด๋ธ์ ์ ์ฅ storage_data('Jaewon', '010-1234-5678') storage_data('Haezin', '010-4444-9999') storage_data('Ginsu', '010-8989-1212') # ํด์ฌ ํ ์ด๋ธ ์ ์ฅ ํ ํด์ฌ ํ ์ด๋ธ ์ํ ํ์ธ print(hash_table) # [0, '010-8989-1212', '010-4444-9999', 0, '010-1234-5678', 0, 0, 0, 0, 0]
โ๏ธ ํด์ฌ ํ ์ด๋ธ์ ๊ฐ์ ์ ์ฅํ์ผ๋, ์ด๋ฅผ ์ฝ์ด์ฌ ์ ์๋ ํจ์๋ ์๋ ์ฒ๋ผ ๋ง๋ค ์ ์๋ค.
# ํด์ฌ ํ ์ด๋ธ์์ ํน์ ์ฃผ์์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ ธ์ค๋ ํจ์ def get_data(data): key = ord(data[0]) # ๐ ๋ฐ์ดํฐ์์ Key๋ฅผ ์ถ์ถ hash_address = hash_func(key) # ๐ key๋ฅผ ํด์ฌ ํจ์์ ๋ฃ์ด ํด์ฌ ์ฃผ์๋ฅผ ์ป์ return hash_table[hash_address] # ๐ ํด์ฌ ์ฃผ์๋ฅผ ํตํด ๋ฐฐ์ด์์ ๋ฐ์ดํฐ๋ฅผ ๋ฐํ print(get_data('Jaewon')) # 010-1234-5678 print(get_data('Haezin')) # 010-4444-9999 print(get_data('Ginsu')) # 010-8989-1212
โ๏ธ ์ฌ์ค ํด์ฌ ํ ์ด๋ธ์ ์๊ฐ๋ณต์ก๋๋ ํ๊ท ์ ์ผ๋ก ๊ฐ์ง๋ ํด์ฌ์ ์๊ฐ๋ณต์ก๋์ ์ต์ ์ ๊ฒฝ์ฐ์ ์๊ฐ ๋ณต์ก๋๊ฐ ์กด์ฌํ๋ค.
โ๏ธ ๊ฐ๋จ ํด์ฌ ํ ์ด๋ธ์ ์์๋ฅผ ํตํด ์ถฉ๋์ด ์ด๋ป๊ฒ ๋ฐ์ํ๋์ง ์ดํด๋ณด๋๋ก ํ๊ฒ ๋ค.
โ๏ธ ์๋ฅผ ๋ค์ด, key๊ฐ์ด 'Jeawon'๊ณผ 'Jisu'๊ฐ ์๋ค๋ฉด, ๋๋ค 'J'๋ฅผ ord ํจ์๋ก ์ฒ๋ฆฌํ๊ธฐ ๋๋ฌธ์ 74๋ฅผ ๋ฐํ๋ฐ๋๋ค. ์ด๋ฅผ ํด์ฌ ํจ์์ ๋ฃ์ด 5๋ก ๋๋ ๋ชซ์ ์๋ก ๋์ผํ๊ธฐ ๋๋ฌธ์ ๋ฎ์ด์์ด์ง๋ ์ถฉ๋ ๋ฌธ์ ๊ฐ ๋ฐ์ํ๋ค.
โ๏ธ ์ถฉ๋์ ํด๊ฒฐํ๊ธฐ ์ํ ๋ฐฉ๋ฒ์ผ๋ก Open Hashing๋ฐฉ์์ Chaining ๊ธฐ๋ฒ ๋๋ Close Hashing ๋ฐฉ์์ Linear Probing ๊ธฐ๋ฒ์ ์ฌ์ฉํ๋๋ฐ, ์ด๋ด ๊ฒฝ์ฐ, ํด๋นํ๋ key๊ฐ์ ์ฐพ๊ธฐ ์ํด ๋ค์ ๋ฐ๋ณต์ด ํ์ํ๊ธฐ ๋๋ฌธ์ O(N)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
โ๏ธ ๋ฐ๋ผ์ ํด์ฌ, ๋ฐฐ์ด, ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์๊ฐ๋ณต์ก๋๋ ์๋์ ๊ฐ๋ค.
โ๏ธ ํด์ฌ ์ถฉ๋์ ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ผ๋ก Close Hashing ๊ธฐ๋ฒ์ผ๋ก ๋ํ์ ์ธ ๊ธฐ์ ์ Chaining์ด๋ค.
โ๏ธ Chaining์ ํด์ฌ ํ ์ด๋ธ ๊ณต๊ฐ ์ธ์ ์๋ก์ด ๊ณต๊ฐ์ ๋ง๋ จํ์ฌ ์ถฉ๋์ด ๋ฐ์ ์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์๋ฃ ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํด ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๋ ๊ธฐ๋ฒ์ด๋ค.
โ๏ธ ๋ํ Chaining ๊ธฐ๋ฒ์ ๋ฐ์ดํฐ๋ฅผ ์๋ณํ ์ ์๋ key๊ฐ์ ํจ๊ป ์ ์ฅํ์ฌ ์ด๋ฅผ ์๋ณํ๋๋ฐ, ๋จ์ ์ผ๋ก๋ ๊ณต๊ฐ์ด ๋ง์ด ํ์ํ๋ค.
# ํด์ฌ ํ ์ด๋ธ hash_table = list([0 for i in range(8)]) # ํด์ฌ ํค ์์ฑ def get_key(data): return hash(data) # ํด์ฌ ํจ์ def hash_function(key): return key % 8 # ํด์ฌ ๋ฐ์ดํฐ ์ ์ฅ def save_data(data, value): index_key = get_key(data) # ๐ index_key๋ผ๋ ๋ณ๋์ ๋ณ์์ key๊ฐ์ ์ ์ฅ hash_address = hash_function(index_key) if hash_table[hash_address] != 0: # ๐ ์ด๋ฏธ ์กด์ฌํ๋์ง ํ์ธ for index in range(len(hash_table[hash_address])): if hash_table[hash_address][index][0] == index_key: hash_table[hash_address][index][1] = value return hash_table[hash_address].append([index_key, value]) else: # hash_table[hash_address] == 0 ๐ ์์ ๋ hash_table[hash_address] = [[index_key, value]] # ํด์ฌ ๋ฐ์ดํฐ ์กฐํ def read_data(data): index_key = get_key(data) hash_address = hash_function(index_key) if hash_table[hash_address] != 0: for index in range(len(hash_table[hash_address])): if hash_table[hash_address][index][0] == index_key: return hash_table[hash_address][index][1] return None else: return None # ํด์ฌ์ฃผ์ ์ค๋ณต ๋ฐ์ <- ํ ๋๋ง๋ค ๋ณํจ print(hash('Jaewon')%8) # 3 print(hash('Haezin')%8) # 2 print(hash('AaLa')%8) # 3 # ์ ์ฅ save_data('Jaewon', '01011112222') save_data('Haezin', '01088889999') save_data('AaLa', '01033331234') print(hash_table) # [0, 0, [[-3231082452735185358, '01088889999'], [630994963842225842, '01033331234']], [[-6162502635708335149, '01011112222']], 0, 0, 0, 0] # ์กฐํ print(read_data('Jaewon')) # 01011112222 print(read_data('Haezin')) # 01088889999
โ๏ธ Linear Probing ๊ธฐ๋ฒ์ Open Hashing์ ํ ๊ธฐ์ ๋ก ํด์ฌ ํ ์ด๋ธ ์ ์ฅ ๊ณต๊ฐ ์์์ ์ถฉ๋ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ํ์ ์ธ ๋ฐฉ์์ด๋ค.
โ๏ธ ๋ํ Linear Probing ๊ธฐ๋ฒ์ ์ถฉ๋ ๋ฐ์ ์, hash adress์ ๋ค์ adress๋ถํฐ ๋งจ ์ฒ์ ๋์ค๋ ๋น ๊ณต๊ฐ์ ์ ์ฅํ๋ ๋ฐฉ์์ด๊ธฐ ๋๋ฌธ์ ์ ์ฅ๊ณต๊ฐ ํ์ฉ๋๊ฐ ๋๋ค.
# ํด์ฌ ํ ์ด๋ธ hash_table = list([0 for i in range(8)]) # ํด์ฌ ํค ์์ฑ def get_key(data): return hash(data) # ํด์ฌ ํจ์ def hash_function(key): return key % 8 # ํด์ฌ ๋ฐ์ดํฐ ์ ์ฅ def save_data(data, value): index_key = get_key(data) hash_address = hash_function(index_key) if hash_table[hash_address] != 0: for index in range(hash_address, len(hash_table)): if hash_table[index] == 0: hash_table[index] = [index_key, value] return elif hash_table[index][0] == index_key: # ์ ๋ฐ์ดํธ hash_table[index][1] = value else: hash_table[hash_address] = [index_key, value] # ํด์ฌ ๋ฐ์ดํฐ ์กฐํ def read_data(data): index_key = get_key(data) hash_address = hash_function(index_key) if hash_table[hash_address] != 0: for index in range(hash_address, len(hash_table)): if hash_table[index] == 0: return None elif hash_table[index][0] == index_key: return hash_table[index][1] else: return None # ํด์ฌ์ฃผ์ ์ค๋ณต ๋ฐ์ <- ํ ๋๋ง๋ค ๋ณํจ print(hash('Jaewon')%8) # 0 print(hash('Haezin')%8) # 0 print(hash('AaLa')%8) # 7 # ์ ์ฅ save_data('Jaewon', '01011112222') save_data('Haezin', '01088889999') save_data('AaLa', '01033331234') print(hash_table) # [[3214169218863054112, '01011112222'], [-291548128366538008, '01088889999'], 0, 0, 0, 0, 0, [-143120377966334057, '01033331234']] # ์กฐํ print(read_data('Jaewon')) # 01011112222 print(read_data('Haezin')) # 01088889999