Hash Table Python

 

 

이 글의 참조본입니다. 해시 테이블을 파이썬으로 구현해본 것입니다.

Hash Table implementation in Python [Data Structures & Algorithms]

key-value형태로 dictionary를 사용해서 저장할 수 있습니다.

 

country_code = {'25': 'USA', '20': 'India', '10': 'Nepal'}

print (country_code['10'])  # Output: Nepal
print (country_code['20'])  # Output: India

 

Python list에서 tuples형태로 저장해서 사용할 수도 있습니다.

 

country_code = [('25', 'USA'), ('20', 'India'), ('10', 'Nepal')]

def search(item_list, key):
    for item in item_list:
        if item[0] == key:
            return item[1]

print(search(country_code, '20'))  # Output: India

 

 

 

 

Insert도 해볼 수 있습니다.

 

hash_table = [None] * 10
print (hash_table) 
# Output: 
# [None, None, None, None, None, None, None, None, None, None]

def hashing_func(key):
    return key % len(hash_table)

def insert(hash_table, key, value):
    hash_key = hashing_func(key)
    hash_table[hash_key] = value


insert(hash_table, 10, 'Nepal')
print(hash_table)
# Output:
# ['Nepal', None, None, None, None, None, None, None, None, None]

insert(hash_table, 25, 'USA')
print(hash_table)
# Output:
# ['Nepal', None, None, None, None, 'USA', None, None, None, None]

 

그런데 이러면 충돌이 날 수 있습니다.

 

그래서 아래와 같이 수정해서 합니다.

 

# Hash table만들기
hash_table = [[] for _ in range(10)]
print (hash_table)
# Output:
# [[], [], [], [], [], [], [], [], [], []]

# 삽입
def insert(hash_table, key, value):
    # Key값
    hash_key = key % len(hash_table)

    # 중복확인을 위한 애
    key_exists = False
    bucket = hash_table[hash_key]

    # bucket안에 여러개가 들어있으면 반복문으로 돌리면서 확인
    for i, kv in enumerate(bucket):
        # kv(Key, value)
        k, v = kv
        if key == k:
            # 중복을 확인했다면 if else중 if로 가기
            key_exists = True
            break
    # 중복되는 것이 있을 때 append하지 않음
    if key_exists:
        bucket[i] = ((key, value))
    # 중복되는 것이 없으면 append
    else:
        bucket.append((key, value))

insert(hash_table, 10000000, '민수')
insert(hash_table, 10000005, '철수')
insert(hash_table, 20000000, '민지')
# output :
# [[(10000000, '민수'), (20000000, '민지')], [], [], [], [], [(10000005, '철수')], [], [], [], []]
insert(hash_table, 20000000, '민지')
# output :
# [[(10000000, '민수'), (20000000, '민지')], [], [], [], [], [(10000005, '철수')], [], [], [], []]
print(hash_table)

 

 

참고

[1] - http://blog.chapagain.com.np/hash-table-implementation-in-python-data-structures-algorithms/