CS) 해시 테이블(Hash table) - 기본 개념과 효율성

대부분의 프로그래밍 언어는 해시 테이블이라는 자료 구조를 포함하며,
해시 테이블에는 빠른 읽기라는 놀랍고 엄청난 능력이 있다.
해시테이블은 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다.
해시, 맵, 해시맵, 딕셔너리, 연관 배열(Associative Array)등의 이름을 갖는다.

해시 테이블은 쌍으로 이뤄진 값들의 리스트다.
첫 번째 항목을 키(key)라 부르고, 두 번째 항목을 값(value)라 부른다.
자바스크립트에서는 Map이 대표적인 해시 테이블이다.

const nMap = new Map();
// key 자리에는 문자열뿐만 아니라 다른 데이터 타입도 들어갈 수 있다.
nMap.set('key','value'); 

해시 테이블에서 키와 값은 서로 중요한 관계다.

해시 테이블은 다음과 같은 문법으로 키의 값을 룩업할 수 있다.

nMap.get('key');

위 코드는 'value'를 반환한다.
해시 테이블의 값 룩업은 딱 한 단계만 걸리므로 평균적으로 효율성이 O(1)이다.

---

해시 함수

예를 들어 다음처럼 단순하게 글자와 숫자를 짝지을 수 있는 표가 있다고 하자

A = 1
B = 2
C = 3
D = 4
...

위 코드에 따르면 ACD 는 134로 BCA는 231로 변환한다.

문자를 가져와 숫자로 변환하는 이러한 과정을 해싱이라 부른다.
또한 글자를 특정 숫자로 변환하는데 사용한 코드를 해시 함수라 부른다.

이 밖에도 해시 함수는 많다. 또 다른 해시 함수 예제는 각 문자에 해당하는 숫자를 가져와 모든 수를 합쳐 반환하는 것이다.
이렇게 하면 BAD는 2단계를 거쳐 숫자 7이된다.
1. BAD를 214로 변환한다.
2. 각 숫자를 합한다.

또 다른 해시 함수 예제는 문자에 해당하는 수를 곱해서 반환하는 것이다.
곱셈을 해서 숫자를 구하면 BAD는 숫자 8이된다.

해시 함수가 유효하려면 한 가지 기준을 충족해야 한다.
동일한 문자열을 해시 함수에 적용할 때마다 동일한 숫자로 변환해야한다.

위의 곱셈 해시 함수를 쓰면 DAB 역시 BAD처럼 8로 변환되는데 이는 실제로 문제가 발생한다. 하지만 지금 단계에서는 동일한 문자열을 해시 함수로 적용하여 숫자로 변환한다는 사실만 인지하면 된다.
해시 함수의 개념을 알면 해시 테이블이 실제로 어떻게 동작하는지 알 수 있다.

해시 테이블

지금 당신이 어플리케이션을 제작하고 있다고 하자.
당신은 유의어 사전을 어플리케이션으로 대체하기 위해 해시 테이블을 사용한다.
해시 테이블은 키와 값 쌍으로 이루어진 항목들의 리스트이니 좋은 선택지가 될 것이다.

다음과 같이 해시테이블로 유의서 사전을 표시할 수 있다.

const dict = new map()

배열과 유사하게 해시 테이블은 내부적으로 데이터를 한 줄로 이뤄진 셀 묶음에 저장하며 각 셀마다 주소가 있다.

첫 번째 항목을 해시 테이블에 추가해 보자.

dict.set("bad","evil");

코드로 표현하면 해시 테이블은 이제 다음과 같다

{"bad" => "evil"}

해시 테이블이 데이터를 어떻게 저장하는지 알아보자.

먼저 컴퓨터는 키에 해시 함수를 적용한다. 앞서 설명했던 '곱셈' 해시 함수를 사용할 것이다. 따라서 다음과 같이 계산된다.
BAD = 2 * 1 * 4 = 8
키bad는 8로 해싱되므로 컴퓨터는 값evil을 다음과 같이 색칠된 셀 8에 넣는다.

▢▢▢▢▢▢▢■▢▢▢▢▢▢▢

이제 다른 키/값 쌍을 추가해 보자.

dict.set("cab","taxi");

컴퓨터는 키를 해싱한다.
CAB = 3 * 1 * 2 = 6

▢▢▢▢▢■▢■▢▢▢▢▢▢
6번째 셀에 값 taxi를 저장한다.

코드로 표현하면 해시 테이블은 현재 다음과 같다

{ "bad" => "evil", "cab" => "taxi" }

해시 테이블 룩업

해시테이블에서 각 값의 위치는 키로 결정된다.
즉 키 자체를 해싱해 키와 연관된 값이 놓여야 하는 인덱스를 계산한다.
키가 값의 위치를 결정하므로 이 원리를 사용하면 룩업이 아주 쉬워진다.
어떤 키가 있고, 그 키의 값을 찾고 싶으면 키 자체로 값을 어디서 찾을 수 있는지 알 수 있다.
적절한 셀에 값을 넣기 위해 키를 해싱했던 것처럼 다시 한 번 키를 해싱해 이전에 값을 넣었던 곳을 찾을 수 있다.

dict.get("bad")

bad의 값을 찾기 위해 컴퓨터는 두 단계를 실행한다.

1. 룩업하고 있는 키를 해싱한다 BAD = 2 * 1 * 4 = 8
2. 결과가 8이므로 셸 8을 찾아가서 저장된 값을 반환한다. 여기서는 문자열 evil이 value로 저장되어 있다.

이제 왜 해시 테이블의 값 룩업이 전형적으로 O(1)인지 명확해졌다.
O(1)은 상수 시간이 걸리는 절차다.
컴퓨터는 키를 해싱해서 숫자로 바꾼 후 그 수의 인덱스로 바로 가서 저장된 값을 추출한다.

왜 해시 테이블이 배열보다 식당 메뉴를 더 빠르게 룩업할 수 있는지 이해할 수 있을 것이다.
배열에서 메뉴 항목의 값을 룩업하려면 항목을 찾을 대까지 각 셀을 순회하며 검색해야 했다.

정렬되지 않은 배열에서는 최대 O(N)이 걸리며 정렬된 배열에서는 최대 O(logN)이 걸린다. 하지만 해시 테이블을 사용하면 실제 메뉴 항목을 키로 사용해서 해시 테이블 룩업을 O(1)만에 할 수 있다.

---

단방향(one-directional) 룩업

해시 테이블에서 한 단계만에 값을 찾는 기능은 그 값의 키를 알 때만 가능하다는 점에 주목하자.
키를 모른 채 값을 찾으려면 해시 테이블 내 모든 키/값 쌍을 검색하는 수밖에 없고 이는 O(N)이다.

즉, 키를 사용해 값을 찾을때만 O(1) 룩업이 가능하다.
값을 이용해 연관된 키를 찾을 때는 빠른 룩업 기능을 사용할 수 없다.

이는 키가 값의 위치를 결정한다는 해시 테이블의 대전제 때문이다.
이 전제는 한 방향으로만, 키를 사용해 값을 찾는 식으로만 동작한다.
값으로는 키의 위치를 빠른 룩업으로 찾을 수 없으니 전부 훑는 것 외에는 키를 쉽게 찾을 방법이 없다.

그렇다면 키는 어디에 저장될까?

앞선 셸 그림은 값이 해시 테이블에 어떻게 저장되는지만 보여준다.
세부적으로는 언어에 따라 다르지만 어떤 언어는 값 바로 옆에 키를 저장한다.
이렇게 저장하면 다음 절에서 다룰 충돌에서 매우 유용하다.

어떤 경우든 해시 테이블의 단방향 속성이 갖는 또 다른 측면에도 주목할 가치가 있다.
각 키는 해시 테이블에 딱 하나만 존재할 수 있으나, 값은 여러 인스턴스가 존재할 수 있다.
BAD키는 하나만 존재하지만, evil이라는 값은 여러 개 있을 수 있다는 뜻이다.

대부분의 언어는 이미 존재하는 키에 키/값 쌍을 저장하려 하면 키는 그대로 두고 기존 값만 덮어쓴다.

해시 충돌 해결

해시는 근사하지만 문제도 있다.

위 예시를 이어 계속 진행하겠다.

유의어 사전에 다음 항목을 추가하면 무슨 일이 벌어질까?

dict.set("dab","angel");

먼저 컴퓨터는 키를 해싱한다. DAB = 4 * 1 * 2 = 8
그리고 angel을 해시 테이블의 8번째 셸에 추가하려 한다.
▢▢▢▢▢▢▢■▢▢▢▢▢▢▢

앗, 8번째 셸에는 이미 bad키로 할당된 evil이 존재한다.

이미 채워진 셸에 데이터를 추가하는 것을 충돌(collision)이라 부른다.

이 문제를 해결하는 방법은 여러가지 있지만, 그 중 고전적인 방법 하나가 분리 연결법이다.
충돌이 발생 했을 때 셸에 하나의 값을 넣는 대신 배열로의 참조를 넣는 방법이다.

예제에서 컴퓨터는 8번째 셸에 angel을 추가하려 했지만 evil이 들어있었다. 따라서 8번째 셸을 배열로 대체한다.

"taxi"		[["bad","evil"],["dab","angel"]]
6	7	8	9	10	11

이 배열에 포함된 하위 배열의 첫번째 값은 단어, 두 번째 단어는 그 단어의 동의어다.

이렇게 바꿨을 때 dab키의 해시 테이블 룩업의 동작은 다음과 같다.

1. 컴퓨터는 키를 해싱한다. DAB = 4 * 1* 2 = 8
2. 셸 8을 룩업한다. 컴퓨터는 셸 8이 하나의 값이 아닌 배열들의 배열을 포함하고 있음을 알게 된다.
3. 각 하위 배열의 인덱스 0을 찾아보며 룩업하고 있는 단어인 dab를 찾을 때까지 배열을 차례대로 검색한다.(선형검색)
4. 일치하는 하위 배열의 인덱스 1에 있는 값을 반환한다.

컴퓨터가 확인 중인 셸이 배열을 참조할 경우 다수의 값이 들어 있는 배열을 선형 검색해야 하므로 검색에 단계가 더 걸린다.
따라서 최악의 경우 해시테이블 룩업 성능은 사실상 O(N)이 되버리는 것이다.

이렇기 때문에 해시 테이블에 충돌이 거의 없도록, O(N)시간이 아닌 O(1)시간 내에 일반적으로 룩업을 수행하도록 디자인해야 한다.

다행히 대부분의 프로그래밍 언어에서 해시 테이블을 구현하고 이를 대신 처리한다.

하지만 내부 동작 방식을 이해함으로써 해시 테이블이 어떻게 O(1)성능을 간신히 유지하는지 이해할 수 있다.

어떻게 해시 테이블을 설정해야 충돌이 가능한 한 적게 일어나는지 알아보자.

효율적인 해시 테이블 만들기

궁극적으로 해시 테이블은 다음 세 요인에 따라 효율성이 정해진다.

1. 해시 테이블에 얼마나 많은 데이터를 저장하는가
2. 해시 테이블에서 얼마나 많은 셸을 쓸 수 있는가
3. 어떤 해시 함수를 사용하는가

해시 함수가 효율성에 영향을 주는 이유

예를 들어 항상 1과 9 사이에 값만 반환하는 해시 함수를 쓰고 있다고 가정하자.
글자를 상응하는 숫자로 변환해서 하나의 숫자가 될 때까지 결괏값의 숫자들을 계속해서 합하는 해시 함수라고 하자.

PUT = 16 + 21 + 20 = 57

57은 숫자가 둘 이상이므로 해시 함수는 57을 5 + 7 = 12로 쪼갠다.
다시 12를 1 + 2 = 3으로 쪼갠다.

결국 PUT은 3으로 해싱된다.

위 해시 함수는 본질적으로 항상 1과 9 사이에 숫자를 반환하게끔 되어있다.

예제로 사용했던 해시 테이블을 보자.

▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢

위 해시 함수를 적용하면 10 이상부터 존재하는 셸을 컴퓨터는 절대 사용하지 않는다.
모든 데이터는 셸1에서 9사이로 채워진다.

따라서 좋은 해시 함수란 사용 가능한 모든 셸에 데이터를 분산시키는 함수다.
데이터를 넓게 퍼트릴수록 충돌이 적다.

훌륭한 충돌 조정 방법

충돌 횟수가 줄어들수록 테이블의 효율성이 높아진다고 배웠다.

이론상 충돌을 피하는 최선의 방법은 해시 테이블에 많은 셸을 두는 것이다.
해시 테이블에 항목을 5개만 저장하고 싶다고 하자.
해시 테이블에 셸이 1000개면 충돌이 일어날 가능성이 거의 없으니 아주 좋을 듯하다.
하지만 충돌을 피하는 것 외에도 메모리를 많이 잡아먹지 않도록 균형을 맞춰야 한다.

1000개의 셸로 이뤄진 해시 테이블에 단지 5개만 저장하는 이유로 사용된다면 이는 메모리 낭비다.

해시 테이블은 반드시 충돌 조정을 수행해야 한다.
좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피한다.

충돌 조정을 위해 컴퓨터 과학자는 다음과 같은 경험에 기반한 규칙을 세웠다.

해시 테이블에 저장된 데이터가 7개면 셸을 10개여야 한다

데이터와 셸 간 이러한 비율을 부하율(load factor)이라 부른다.
이 용어를 적용하면 해시 테이블의 이상적인 부하율은 0.7이다.

앞서 언급했듯이 해시 테이블 내부는 대부분 사용자가 쓰는 컴퓨터 언어가 관리한다.
컴퓨터 언어는 해시 테이블이 얼마나 커야 하는지, 어떤 해시 함수를 쓰는지, 언제 해시 테이블을 확장할지 결정한다.
프로그래밍 언어가 최고의 성능을 내도록 해시 테이블을 구현했다고 가정해도 무방하다.

해시가 어떻게 동작하는지 알았으니 O(1)의 뛰어난 룩업이 가능해졌다.
곧 이러한 지식에 기반해 코드 속도를 최적화하겠다.

하지만 먼저 간단한 데이터 구조 관점에서 해시 테이블을 쓰는 다양한 유스케이스를 살펴보자.