[기술면접] 해시테이블 파이썬 구현

해시테이블이란?

딕셔너리 자료형을 생각하면 된다. 딕셔너리 자료형은 key값을 통해 value값을 O(1)속도로 찾는다.

여기서 key값을 특정한 hash값으로 변경해준 뒤 이 hash값으로 value를 찾는데 이러한 hash값을 모아논 자료형이 해시테이블이다

즉 해시테이블은 세가지만 기억하자

• key
• hashkey (그림에서 buckets)
• value

 

해시테이블의 과정은 이렇다.

 

1. key값을 기준으로 hashkey를 계산한다.

2. hashkey를 기준으로 value를 찾는다.

 

 

아래는 파이썬으로 기본적인 hashtable을 구현해본 것이다.

class hashTable:
    def __init__(self, tableSize):
        self.tableSize = tableSize
        self.hashTable = [0] * tableSize

    def getHashKey(self, key):
        hashkey = 0
        for c in key:
            hashkey += ord(c) - ord('a')
        hashkey %= self.tableSize
        return hashkey

    def add(self, key, value):
        hashkey = self.getHashKey(key)
        self.hashTable[hashkey] = value

    def find(self, key):
        hashkey = self.getHashKey(key)
        return self.hashTable[hashkey]


myHashTable = hashTable(10)
myHashTable.add("abc",10)
myHashTable.add("def",20)
print("key 값 abc의 value는 ",myHashTable.find("abc"))
print("key 값 def의 value는 ",myHashTable.find("def"))

결과

key 값 abc의 value는  10
key 값 def의 value는  20

 

코드 설명하면

def getHashKey(self, key):
        hashkey = 0
        for c in key:
            hashkey += ord(c) - ord('a')
        hashkey %= self.tableSize
        return hashkey

key 값에서 hashkey를 계산하는 과정이다. 각 key문자의 알파벳 순서를 구한뒤 다 더해서 hashkey를 만든다.

 

def add(self, key, value):
    hashkey = self.getHashKey(key)
    self.hashTable[hashkey] = value

def find(self, key):
    hashkey = self.getHashKey(key)
    return self.hashTable[hashkey]

위에 getHashKey 함수를 이용해서 hashkey를 구한 뒤 hashtable에서 해당 hashkey를 기준으로 값을 추가, 찾기를 해준다.

 

 

 

 

 

 

해시 충돌

 

가령 위 방법으로 key값을 "abc" , "cba"로 value를 추가해준다 하자.

"abc"와 "cba"는 동일한 hashkey값인 3을 가진다. 동일한 해시테이블 위치를 공유하므로 해시충돌이 일어난다.

 

 

 

이를 해결하는 방법은 두가지가 있다.

 

 

1. 체이닝 기법

두개의 key값이 같은 hashkey를 가질경우 해당 hashkey 해시테이블에 링크드리스트로 [key, value] 쌍을 저장한다.

 

여기서 주목할점은 데이터를 저장할 때 [key, value] 로 저장하는것을 기억하자.

 

그렇게 해야 똑같은 hashkey라도 key값으로 다시 value를 구분할 수 있다.

 

 

 

아래는 링크드리스트 대신 list로 구현해놓은 파이썬 코드이다.

class hashTable:
    def __init__(self, tableSize):
        self.tableSize = tableSize
        self.hashTable = [[] for _ in range(tableSize)]

    def getHashKey(self, key):
        hashkey = 0
        for c in key:
            hashkey += ord(c) - ord('a')
        hashkey %= self.tableSize
        return hashkey

    def add(self, key, value):
        hashkey = self.getHashKey(key)
        self.hashTable[hashkey].append([key, value])
        print("hashkey ", hashkey, "위치에 key", key, "value ", value,"값이 저장되었습니다.")

    def find(self, key):
        hashkey = self.getHashKey(key)
        for list_key, list_value in self.hashTable[hashkey]:
            if key == list_key:
                return list_value
        print("찾기 실패")
        return None


myHashTable = hashTable(10)
myHashTable.add("abc",10)
myHashTable.add("cba",20)
print("key 값 abc의 value는 ",myHashTable.find("abc"))
print("key 값 cba의 value는 ",myHashTable.find("cba"))

결과

hashkey  3 위치에 key abc value  10 값이 저장되었습니다.
hashkey  3 위치에 key cba value  20 값이 저장되었습니다.
key 값 abc의 value는  10
key 값 cba의 value는  20

 

 

 

 

코드 설명하자면

def add(self, key, value):
	hashkey = self.getHashKey(key)
	self.hashTable[hashkey].append([key, value])
	print("hashkey ", hashkey, "위치에 key", key, "value ", value,"값이 저장되었습니다.")

def find(self, key):
	hashkey = self.getHashKey(key)
	for list_key, list_value in self.hashTable[hashkey]:
	if key == list_key:
		return list_value
	print("찾기 실패")
	return None

 

아까 강조했던 hashkey에 자료를 저장할 때  [key, value] 쌍을 저장하는것을 볼 수 있다.

self.hashTable[hashkey].append([key, value])

이를 토대로 같은 hashkey를 가질경우 key값으로 다시 value를 찾는다.

hashkey = self.getHashKey(key)
	for list_key, list_value in self.hashTable[hashkey]:
	if key == list_key:
		return list_value

 

 

 

 

2. 선형 조사 기법(Linear Probing)

이 방법은 해시충돌이 일어날 경우 해시테이블에서 빈곳을 찾아 값을 넣어주는 방법이다.

위 방법과 마찬가지로 데이터를 정할때  [key, value] 쌍을 저장해야 값을 찾을 수 있다.

 

 

class hashTable:
    def __init__(self, tableSize):
        self.tableSize = tableSize
        self.hashTable = [[] for _ in range(tableSize)]

    def getHashKey(self, key):
        hashkey = 0
        for c in key:
            hashkey += ord(c) - ord('a')
        hashkey %= self.tableSize
        return hashkey

    def add(self, key, value):
        hashkey = self.getHashKey(key)
        if not self.hashTable[hashkey]:
            self.hashTable[hashkey] = [key, value]
            print("hashkey ", hashkey, "위치에 key", key, "value ", value,"값이 저장되었습니다.")
        else:
            nextHash = (hashkey+1) % self.tableSize
            while self.hashTable[nextHash]:
                nextHash = (nextHash+1) % self.tableSize
                if nextHash == hashkey: # 한바퀴 돌았으면 빈테이블이 없다는 뜻
                    print("빈 테이블을 찾는데 실패하였습니다.")
                    return
            self.hashTable[nextHash] = [key, value]
            print("hashkey ", nextHash, "위치에 key", key, "value ", value,"값이 저장되었습니다.")


    def find(self, key):
        hashkey = self.getHashKey(key)
        if self.hashTable[hashkey][0] == key:
            return self.hashTable[hashkey][1]
        else:
            nextHash = (hashkey+1) % self.tableSize
            while self.hashTable[nextHash][0] != key:
                nextHash = (nextHash+1) % self.tableSize
                if nextHash == hashkey: # 한바퀴 돌았으면 빈테이블이 없다는 뜻
                    print("찾기 실패")
                    return
            return self.hashTable[nextHash][1]



myHashTable = hashTable(10)
myHashTable.add("abc",10)
myHashTable.add("cba",20)
print("key 값 abc의 value는 ",myHashTable.find("abc"))
print("key 값 cba의 value는 ",myHashTable.find("cba"))

결과

hashkey  3 위치에 key abc value  10 값이 저장되었습니다.
hashkey  4 위치에 key cba value  20 값이 저장되었습니다.
key 값 abc의 value는  10
key 값 cba의 value는  20

코드가 늘어나고 뭔가 복잡해진거 같은데 아이디어는 간단하다.

 

• hashkey에 해당하는 테이블이 비어있으면 값을 저장
• 비어있지 않다면 hashkey+1 을 해주어 가며 빈곳을 찾은 뒤 저장

역시나 값을 저장 할 때  [key, value] 쌍을 저장해주는걸 잊지 말자

 

 

위 예제에서 "abc" 가 hashkey 3에 먼저 데이터를 저장했다.

"cba"의 경우에도 hashkey 3을 가지나 값이 차있으므로 그 다음인 hashkey 4에 값을 저장한다.