해시 테이블 (HashSet, HashMap) 구현

개요

해시 테이블(hash table)이란, 키를 가지는 데이터의 집합에 대해서 요소의 추가나 검색을 효율적으로 실시하기 위한 데이터 구조의 일종입니다. 그 실체는 일정수의 요소를 격납할 수 있는 배열과, 데이터가 격납되는 배열의 위치를 ​​출력하는 해시 함수로 구성되어 있습니다. 이 기사에서는 간단한 해시 함수를 사용하여 HashSet과 HashMap을 구현하는 방법을 소개합니다.

구현 예

HashSet

class MyHashSet(object):
    def __init__(self):
        # データを格納する配列を用意する
        self.hashset = [None] * 10000

    # keyを10000で割った剰余を配列の添え字として返すハッシュ関数
    def hash(self, key):
        return key % 10000

    def add(self, key):
        if self.contains(key):
            return
        idx = self.hash(key)
        if self.hashset[idx] is None:
            # 同じ位置に別のデータが保存される可能性があるため、配列として格納しておく
            self.hashset[idx] = [key]
        else:
            # すでに同じ位置に別のキーが格納されている場合、末尾に追加する
            self.hashset[idx].append(key)

    def remove(self, key):
        if not self.contains(key):
            return        
        idx = self.hash(key)
        if self.hashset[idx] is not None:
            arr = self.hashset[idx]
            del arr[arr.index(key)]

    def contains(self, key):
        idx = self.hash(key)
        if self.hashset[idx] is None:
            return None
        else:
            arr = self.hashset[idx]
            return any(val == key for val in arr)

HashMap

class MyHashMap(object):
    def __init__(self):
        self.hashmap = [None] * 10000

    def hash(self, key):
        return key % 10000

    # key, valueをタプルとして保存する
    def put(self, key, value):
        idx = self.hash(key)
        if self.hashmap[idx] is None:
            self.hashmap[idx] = [(key, value)]
        else:
            arr = self.hashmap[idx]
            for i in range(len(arr)):
                pair = arr[i]
                if pair[0] == key:
                    del arr[i]
                    break
            arr.append((key, value))

    # keyに対応するvalueを返す。見つからなければ-1を返す
    def get(self, key):
        idx = self.hash(key)
        if self.hashmap[idx] is None:
            return -1
        else:
            arr = self.hashmap[idx]
            for pair in arr:
                if pair[0] == key:
                    return pair[1]
            return -1

    def remove(self, key):
        if not self.contains(key):
            return

        idx = self.hash(key)
        arr = self.hashmap[idx]
        for i in range(len(arr)):
            pair = arr[i]
            if pair[0] == key:
                del arr[i]
                break

    def contains(self, key):
        idx = self.hash(key)
        if self.hashmap[idx] is None:
            return None
        else:
            arr = self.hashmap[idx]
            for pair in arr:
                if pair[0] == key:
                    return True
            return False

보충

격납되는 요소의 수가 배열의 사이즈를 넘으면 충돌이 일어나기 때문에, 체인법이나 오픈 어드레스법 등에 의해 충돌을 회피할 필요가 있습니다. 체인법에서는 배열의 요소를 LinkedList로 관리하는 것으로 충돌을 회피합니다만, 본 기사에서는 간략화를 위해서 배열의 배열이라고 하는 형태로 해시 테이블을 구현하고 있습니다.

참고