Hash Table : ํค(Key)์ ๋ฐ์ดํฐ(Value)๋ฅผ ์ ์ฅํ๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ์ด๋ค.
hash_table = list([0 for i in range(8)])
# ํ์ด์ฌ list comprehension ์ฌ์ฉ
def get_key(data):
return hash(data)
def hash_function(key):
return key % 8
def save_data(data, value):
hash_address = hash_function(get_key(data))
hash_table[hash_address] = value
def read_data(data):
hash_address = hash_function(get_key(data))
return hash_table[hash_address]
save_data('Dave', '0102030200')
save_data('Andy', '01033232200')
read_data('Dave')
print(hash_table)
[0, 0, 0, 0, 0, 0, '0102030200', '01033232200']
๋ฌธ์ ์
- ํ์ง๋ง ๋ง์ฝ ์๋ก ๋ค๋ฅธ key์์๋ ํด์ฌ ์ฃผ์๊ฐ ๋์ผํ๋ค๋ฉด ์ด๋ป๊ฒ ํด์ผ ํ ๊น?
- ๋ฐ๋ผ์ ์์ ๋ฐฉ๋ฒ์ผ๋ก ํด์ฌ ํ ์ด๋ธ์ ๊ตฌํํ๊ฒ ๋๋ฉด ์ด๋ฌํ ํด์ฌ ์ถฉ๋(Hash Collision) ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ์ง ๋ชปํ๋ค.
- ํด์ฌ ์ถฉ๋์ ํด๊ฒฐํ๊ธฐ ์ํด์๋
Chaining ๊ธฐ๋ฒ
orLinear Probing ๊ธฐ๋ฒ
์ ์ด์ฉํด์ผ ํ๋ค.
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(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] = [[index_key, value]]
def read_data(data):
index_key = get_key(data)
hash_address = hash_function(index_key)
if hash_table[hash_address] != 0: # ํด๋น hash address์ ๋ฐ์ดํฐ๊ฐ ์กด์ฌํ๋ ๊ฒฝ์ฐ
for index in range(len(hash_table[hash_address])): # ํด๋น hash address์ ์ฐ๊ฒฐ๋ ๋ชจ๋ key ์ํ
if hash_table[hash_address][index][0] == index_key:
return hash_table[hash_address][index][1]
return None # ์ํ ํ ์ผ์นํ๋ key๊ฐ ์์ผ๋ฉด None ๋ฐํ
else:
return None # ํด๋น hash address์ ๋ฐ์ดํฐ๊ฐ ์กด์ฌํ์ง ์๋ ๊ฒฝ์ฐ
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)): # ํ์ฌ hash address๋ถํฐ ํด์ฌ ํ
์ด๋ธ ๋๊น์ง ์ํ
if hash_table[index] == 0: # ์ฒ์ ๋์ค๋ ๋น ๊ณต๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅ
hash_table[index] = [index_key, value]
return
elif hash_table[index][0] == index_key: # ๊ฐ์ ํค์ด๋ฉด ๋ฐ์ดํฐ๋ฅผ ์
๋ฐ์ดํธ
hash_table[index][1] = value
return
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: # ํด๋น hash address์ ๋ฐ์ดํฐ๊ฐ ์กด์ฌํ๋ ๊ฒฝ์ฐ
for index in range(hash_address, len(hash_table)): # ํ์ฌ hash address๋ถํฐ ํด์ฌ ํ
์ด๋ธ ๋๊น์ง ์ํ
if hash_table[index] == 0: #๋น ์ฌ๋กฏ์ด ๋ํ๋๊ฒ ๋๋ฉด ์ ์ฅ๋ ์ ์ด ์๋ ๋ฐ์ดํฐ์
return None
elif hash_table[index][0] == index_key:
return hash_table[index][1]
else: # ํด๋น hash address์ ๋ฐ์ดํฐ๊ฐ ์กด์ฌํ์ง ์๋ ๊ฒฝ์ฐ
return None
ํด์ฌ ํ ์ด๋ธ์ ๊ฒฝ์ฐ, ์ผ๋ฐ์ ์ธ ๊ฒฝ์ฐ๋ฅผ ๊ธฐ๋ํ๊ณ ๋ง๋ค๊ธฐ ๋๋ฌธ์, ์๊ฐ ๋ณต์ก๋๋ ์ด๋ผ๊ณ ๋งํ ์ ์์