해시 테이블

key-value 데이터

key를 사용해 value를 가져온다. key와 그 key에 해당하는 value를 합쳐서 key - value 쌍이라 하고 하나의 key에는 하나의 value만 있어야 한다.

key	value
101	‘철수’
202	‘영희’
303	‘민수’

이렇게 호수를 key로 사용하면 그에 해당하는 value를 가져올 수 있다.

임의 접근 테이블에서는 효율적으로 key - value쌍을 저장하고 가져올 수 있지만 낭비하는 공간이 많다. 위의 경우에서 0에서 303번 인덱스까지 생성해야 하지만 실제 사용하는 인덱스는 3개다.

해시 테이블

해시 함수는 특정 값을 원하는 범위의 자연수로 바꿔주는 함수다.

해시 테이블은 해시 함수와 배열을 함께 사용하는 자료구조다. key를 바로 인덱스로 사용하지 않고 해시 함수에 넣어서 리턴된 값을 사용한다.
먼저 고정된 크기의 배열을 만들고 해시 함수를 이용해서 key를 원하는 범위의 자연수로 바꾼다. 그리고 해시 함수 결과 값 인덱스에 key - value 쌍을 저장한다.

해시 함수의 리턴값 범위를 0에서 2까지로 해서 101을 넣었을 때 0이 나왔다면 배열의 0번 인덱스에 101과 ‘철수’가 들어간다.

index	value
0	101, ‘철수’
1	202, ‘영희’
2	303, ‘민수’

해시 함수

해시 함수는 똑같은 key를 넣었을 때는 항상 똑같은 결과가 나와야 하고 결과 해시값이 최대한 치우치지 않고 고르게 나와야 한다. 그리고 해시 테이블은 모든 연산을 할 때마다 해시 함수를 써야하기 때문에 속도가 빨라야 한다.

나눗셈 방법

def hash_function_remainder(key, array_size):
    return key % array_size

print(hash_function_remainder(40, 200))  # 40
print(hash_function_remainder(788, 200))  # 188

이렇게 나누기를 사용해서 만드는 방법이 있다. key를 0 ~ array_size - 1범위의 자연수로 바꿔준다.

곱셈 방법

def hash_function_multiplication(key, array_size, a):
    temp = a * key
    temp = temp - int(temp)
    
    return int(array_size * temp)

print(hash_function_multiplication(40, 200, 0.61426212))  # 114
print(hash_function_multiplication(120, 200, 0.61426212))  # 142

먼저 0 < a < 1 인 아무 a를 정한다. 그리고 a에 key를 곱하고 소수 부분만 남긴다. 남은 소수 부분에 배열의 크기를 곱하고 자연수 부분만 리턴한다.

파이썬 해시 함수

print(hash(123))

파이썬의 hash함수는 위에서의 해시 함수와 같이 특정 범위의 정수가 아니라 아무 정수로 바꿔주는 함수다. 같은 값을 넣으면 항상 같은 값을 리턴하고 서로 다른 값을 넣었을 땐 절대 같은 정수가 리턴되지 않는다. 정수가 아닌 다른 자료형을 넣어도 고유한 정수값으로 리턴해 주므로 해시 테이블에 저장할 수 있는 데이터 종류의 폭을 늘릴 수 있다. 다만 모든 자료형을 넣을 순 없고 불변 타입 자료형에만 사용할 수 있다.

chaining

해시 함수가 기존에 있는 값을 리턴하면 충돌이 일어난 것이다. chaining은 충돌을 해결하는 방법이다. 충돌이 일어났을 때 중복이된 인덱스에 그 값들을 엮어 연결하는 것이다.

더블리 링크드 리스트를 사용한 chaining

Node클래스에는 기존의 data를 key와 value로 대체한다.

LinkedList클래스에서 init메소드는 그대로 사용한다.
탐색 메소드는 기존의 특정 데이터를 가진 노드를 찾는 것에서 특정 key를 가진 노드를 찾도록 변경한다.
추가 메소드는 파라미터로 data변수 대신 key와 value를 받도록한다. 새로운 노드를 생성할 때 key와 value를 넘겨주도록 수정한다.
삭제 메소드는 기존의 삭제할 노드의 데이터를 리턴하던 부분을 없애고 나머지는 동일하다.
str메소드는 key - value형식에 적합하도록 출력 형식을 바꿔준다.

탐색 연산

해시 테이블은 데이터의 순서 관계를 저장하지 않기 때문에 인덱스를 이용하는 접근 연산이 없다. 해시 테이블에서 탐색 연산은 주어진 key에 해당하는 value를 찾는 것이다. 먼저 해시 함수가 값을 계산해야 하고 O(1)만큼 걸린다. 그 값으로 배열 인덱스를 접근하는 데는 O(1)만큼 걸린다. 그 인덱스에서 링크드 리스트를 탐색할 때 최악의 경우는 모든 데이터 쌍이 한 링크드 리스트에 저장된 경우고 O(n)만큼 걸린다. 그래서 최종적으로 봤을 때 O(n)만큼 걸리는 것이다.

삽입 연산

해시 함수의 리턴값에 해당하는 인덱스로 접근했을 때 추가할 값의 key가 기존에 존재하는 key라면 새로운 value로 수정하고 아니라면 링크드 리스트 마지막에 추가한다.

해시 함수가 값을 계산하면 O(1)이 걸린다.
그 값으로 배열 인덱스를 접근 하는 데는 O(1)이 걸린다.
링크드 리스트를 탐색하는 것은 최악의 경우에 O(n)이 걸린다.
링크드 리스트에 저장하거나 수정하는 것은 O(1)이 걸린다.
그래서 총 O(n)이 걸린다.

삭제 연산

특정 key에 대한 key - value 쌍을 삭제한다.
해시 함수 계산은 O(1), 배열 인덱스 접근은 O(1)이 걸린다.
접근한 인덱스에서의 링크드 리스트 노드 탐색은 최악의 경우에 O(n)이 걸린다.
링크드 리스트 노드 삭제는 O(1)이 걸린다.
총 O(n)이 걸린다.

평균 시간 복잡도를 이용

모든 key - value데이터 쌍이 하나의 링크드 리스트에 저장되는 경우가 최악의 경우고 O(n)이 걸린다. 하지만 이 경우는 거의 일어나지 않는 일이므로 평균 시간 복잡도를 이용해서 분석한다.

링크드 리스트를 탐색하는데 O(n)이 걸리고 나머지는 O(1)이 걸린다. 여기서 n이 최악의 경우가 아니라 링크드 리스트들의 평균길이라고 생각하고 이것을 사용해 평균 시간 복잡도를 평가해보자. 일단 배열에 저장되어 있는 링크드 리스트들의 평균 길이를 구하려면 해시 테이블에 총 들어가 있는 key - value 쌍의 수가 n이고 해시 테이블이 사용하는 배열의 크기가 m이라면 n/m이라고 할 수 있다. 여기서 한가지 가정을 하는데 해시 테이블에 총 저장하는 key - value쌍의 수와 해시 테이블이 사용하는 배열의 크기가 비슷하거나 작다고 하면, 즉 해시 테이블을 만들 때 항상 어느 정도까지는 n = m을 유지시켜 준다고 약속하면 n/m은 1이라고 볼 수 있고 결과적으로 O(1)이라고 할 수 있다. 그래서 해시 테이블의 삽입, 삭제, 탐색 연산은 최악의 경우에 O(n)이 걸리지만 평균적으로는 O(1)이 걸린다고 할 수 있다.

open addressing

open addressing은 충돌이 일어났을 때 다른 비어있는 인덱스를 찾아 그곳에 데이터를 저장한다.

선형 탐사

비어있는 인덱스를 찾는 방법 중 선형 탐사(linear probing)를 사용할 수 있다. 선형 탐사는 충돌이 일어났을 때, 한 칸씩 다음 인덱스가 비었는지 확인하는 방법이다. 2번 인덱스에 데이터를 넣으려는데 이미 2번 인덱스에 데이터가 존재한다면 3번 인덱스를 확인하고 마찬가지로 데이터가 존재한다면 4번 인덱스를 확인하고 비었다면 채워넣는다.

제곱 탐사

제곱 탐사는 처음에 1의 제곱 뒤에 있는 인덱스를 확인한다. 1번 인덱스에 데이터를 넣으려는데 이미 1번 인덱스에 데이터가 존재한다면 1의 제곱 뒤인 2번 인덱스를 확인한다. 그 다음엔 2번 인덱스에서 2의 제곱 뒤인 6번 인덱스를 확인한다. 그 다음엔 6번 인덱스에서 3의 제곱 뒤인 15번 인덱스를 확인한다. 이런식으로 빈 인덱스를 찾아나간다.

탐색 연산

선형 탐사를 사용한다. 해시 함수가 리턴한 해당 인덱스로 접근했을 때 key가 일치하지 않다면 선형적으로 다음 인덱스들을 확인해 나간다. 만약 선형 탐사를 해나가다가 빈 인덱스를 만나게 되면 탐색하는 해당 key에 대한 데이터가 애초에 저장되지 않았다는 말이된다. 왜냐하면 어떤 인덱스에 데이터를 넣으려는데 이미 데이터가 존재한다면 빈 인덱스를 중복된 인덱스에서 부터 찾아나가다가 빈 인덱스를 발견하면 바로 집어넣기 때문에 탐색 연산을 중복된 인덱스에서 부터 해나갈 때 찾으려는 key가 배열내에 분명히 존재한다면 빈 인덱스를 만나기 전에 반드시 발견할 수 밖에 없다. 그러므로 빈 인덱스를 찾으면 연산을 종료한다.

삭제 연산

탐색 연산을해서 데이터를 찾게된다. 하지만 여기서 찾은 데이터를 그냥 삭제해버리면 문제가 생기는데

인덱스	key, value
1	101,’철수’
2	202, ‘영희’
3	303, ‘민수’
4

이렇게 데이터가 존재할 때 데이터를 추가하려고 해시 함수를 돌렸더니 2가 나왔다면 이미 해당 인덱스에는 데이터가 존재하니 비어있는 4번 인덱스에 데이터를 넣게 된다. 여기서 3번 인덱스를 그냥 삭제해 버리고 탐색 연산으로 방금 추가 했던 데이터로 접근을 하려하면 처음에 2번 인덱스로 갔다가 key가 일치하지 않으니 그 다음 인덱스로 넘어간다. 그런데 3번 인덱스는 비어 있으니 찾으려는 key가 없다고 판단하고 종료하게 된다. 하지만 찾으려는 key는 4번 인덱스에 분명히 존재하고 있는 문제가 생기기 때문에 삭제하고 싶은 인덱스를 그냥 비워버리지 않고 “DELETED”같은 약속된 표시를 해둔다. 그럼 이 표시를 보고 연산을 중지하지 않고 원하는 값을 찾아낼 수 있다.

시간 복잡도

삽입, 탐색, 삭제 모두 인덱스를 찾는 탐사를 해야하고 탐사 최악의 경우는 배열안의 모든 인덱스를 다 확인하는 경우고 O(n)이 걸린다. 그럼 삽입, 탐색, 삭제의 시간 복잡도는 O(n)이 된다. 하지만 이 경우는 해시 테이블이 사용하는 배열이 거의 꽉 찼을 경우고 실질적으로 그런 경우는 잘 일어나지 않는다. 그래서 평균 시간 복잡도를 확인해 본다.

해시 테이블 연산들을 분석할 때는 load factor를 사용한다. load factor를 a, 해시 테이블이 사용하는 배열의 크기를 m, 해시 테이블 안에 들어 있는 데이터 쌍 수를 n이라고 할 때 a = n/m 이다. 해시 테이블이 얼마나 차있는지를 나타내는 것이다. 배열의 크기보다 더 많은 key - value 쌍을 저장할 수 없으므로 a는 항상 1보다 작다고 가정한다. open addressing을 사용하는 해시 테이블에서 평균적으로 탐사 해야 하는 횟수(기대값)는 1/1 - a 보다 작다. 배열이 총 100칸일 때 90개의 key - value쌍을 저장하면 a = 0.9이다. 기대값에 a를 대입하면 10이다. a = 0.5라면 기대값은 2보다 작다. load factor가 0.9를 넘기지 않게 사용한다고 약속한다면 항상 10보다 적게 탐사할 수 있으므로 O(10)이 된다. 즉, 탐사는 최악의 경우 O(n)이 걸리고 평균적으로는 O(1)이 걸린다.