Hash Table 구현

Linear Probing 방식의 Hash Table 구현하기

해쉬 테이블은 컴퓨터 과학에서 가장 중요하면서도 검색 / 삽입 / 삭제 작업에 효율적인 자료구조 중 하나로, 평균 O(1)의 시간복잡도로 Key-value 형태의 값을 저장하고 검색할 수 있습니다.

헤쉬 테이블에 데이터를 추가하거나 조회할 때는 Hash Function을 사용하며 해쉬 테이블에서 해시 함수는 입력된 키를 테이블의 크기에 적합한 인덱스 값으로 변환하는 것이 목적입니다. 따라서 인덱스 범위는 해시 테이블의 크기에 의존적입니다. 구현할 해시 테이블에서는 문자열 타입의 키를 입력 받으면 Hash Function에서는 파이썬의 내장 함수 ord()를 사용해 각 문자들을 모두 아스키 값으로 변환한 후에 tot 변수에 변환한 각 문자의 아스키 값들을 누적 덧셈하여 총합을 얻은 후 이 총합에서 해쉬 테이블이 가진 사이즈의 크기 만큼 나눈 나머지를 해쉬 테이블에 저장할 위치인 인덱스로 사용할 것입니다.

만약 해시 테이블에 데이터를 저장하던 도중 해쉬 테이블 인덱스에 이미 데이터가 존재할 경우, 즉 해시 충돌이 발생했을 경우 다음 주소를 정하는 방법 중 하나인 Open addressing 방식을 사용하여 충돌이 발생한 메모리 주소 다음 위치의 공간을 저장/검색하도록 하겠습니다.

데이터를 가져올 때는 키와 밸류 모두 숫자 인덱스로 되어 있을 경우 문자열 타입인 키로 데이터를 찾기가 힘들어 저장할 때 해쉬 테이블의 밸류는 튜플 타입으로 문자열 키와 밸류를 같이 넣었습니다.

Hash Table 구현 코드

class HashTable:
    # map 타입의 노드를 size 길이만큼 생성하고 초기 밸류값은 None을 할당합니다.
    def __init__(self, size: int):
        self.nodes = {i: None for i in range(size)}
        self.size = size

    # 문자열 타입의 키를 아스키코드로 변환한 후 size로 나눈 나머지 값을 반환합니다.
    def hash(self, key: str) -> int:
        # 키의 각 문자를 아스키 코드로 변환하여 tot에 더해 총합 추출
        tot = 0
        for word in key:
            tot += ord(word)
        # 총합을 size 크기만큼 나눈 나머지를 인덱스 변수에 할당
        index = tot % self.size
        # 인덱스 변수가 size보다 클 경우 헤시 테이블이 이미 꽉 찼다는 에러 발생
        if index >= self.size:
            raise ValueError("Hash Table Is Full")
        return index

    # 데이터 저장
    def put(self, key: str, value: int):
        # 해쉬 함수로 현재 노드의 인덱스 가져오기
        curr_node = self.hash(key)
        # 현재 노드의 밸류 값이 None일 경우
        if self.nodes[curr_node] is None:
            # 밸류값으로 문자열 key와 value를 튜플 타입으로 저장
            self.nodes[curr_node] = (key, value)
            return

        i = 1
        # 이전 노드가 이미 데이터로 채워져 있다면 현재 인덱스 오른쪽으로 한 칸 이동
        next_node = (curr_node + i) % self.size
        # 한 칸 이동한 노드에 데이터가 None이 아닐 경우(데이터가 존재할 경우) 반복문 실행
        while self.nodes[next_node] is not None:
            # 오른쪽으로 한 칸 이동
            next_node = (next_node + i) % self.size
            i += 1
            # 현재 인덱스 위치가 size보다 같거나 클 경우 에러 발생
            if i >= self.size:
                raise ValueError("Hash Table Is Full")
        # 밸류 데이터가 None인 노드를 찾을 경우 동일하게 문자열 타입의 키와 값을 튜플 타입으로 저장
        self.nodes[next_node] = (key, value)

    # 데이터 조회
    def get(self, key: str) -> int:
        # 해쉬 함수로 현재 노드 위치 인덱스 반환
        curr_node = self.hash(key)
        # 현재 노드가 None이 아니면서 밸류에 저장한 문자열 키가 key 인수와 동일하다면 value 반환
        if self.nodes[curr_node] is not None and self.nodes[curr_node][0] is key:
            return self.nodes[curr_node][1]

        i = 1
        # 오른쪽 노드로 이동한 인덱스를 next_node에 할당
        next_node = (curr_node + i) % self.size
        # 오른쪽으로 한 칸 이동한 노드에 데이터가 None이 아닐 경우(데이터 존재) 반복문 실행
        while self.nodes[next_node] is not None:
            # 만약 노드 밸류의 문자열 키와 key 인수가 동일하다면 value 반환
            if self.nodes[next_node][0] == key:
                return self.nodes[next_node][1]
            # 그렇지 않을 경우 다음 노드로 이동하며 순회
            next_node = (next_node + i) % self.size
            i += 1
            # 현재 인덱스가 사이즈보다 클 경우 데이터가 없으므로 None 반환
            if i > self.size:
                return None

TestCase

hash_table = HashTable(5)
test_case = ["강호동", "신짱구", "친구", "와우", "아나나"]
for idx, test in enumerate(test_case):
    hash_table.put(test, idx)

for test in test_case:
    print(hash_table.get(test), end=" ")

# 출력
# 0 1 2 3 4