해시 테이블이라는 특수한 자료 구조를 사용하면 데이터를 O(1)만에 룩업할 수 있다.
8.1 해시 테이블
대부분의 프로그래밍 언어는 해시 테이블이라는 자료 구조를 포함하며, '빠른 읽기'가 특징이다. 해시, 맵, 해시 맵, 딕셔너리, 연관 배열 등의 이름을 갖는다.
let menu = new Map([["french fries", 0.75], ["hamburger", 2.5], ["hot dog", 1.5], ["soda", 0.6]]);해시 테이블은 쌍으로 이뤄진 값들의 리스트다. 첫 번째 항목을 키 Key라고 부르고, 두 번째 항목을 값 Value이라고 부른다.
자바스크립트에서는 다음과 같은 문법으로 키의 값을 룩업할 수 있다: menu.get("french fries"). 이 코드는 0.75라는 값을 반환한다. 해시 테이블의 값 룩업은 딱 한 단계만 걸리므로 평균적으로 효율성이 O(1)이다.
8.2 해시 함수로 해싱
A=1, B=2, C=3 ... 이라는 비밀 코드를 만든다고 가정하자. 가령, BAD는 214로 변환된다.
위 과정에서, 문자를 가져와 숫자로 변환하는 과정을 해싱이라 부른다.
글자를 특정 숫자로 변환하는 데 사용한 코드를 해시 함수라 부른다.
해시 함수는 이밖에도 많다. 비밀 코드로 문자를 숫자로 변환해 모든 숫자를 합치거나 곱해서 반환할 수도 있다. BAD의 예시에서 합치면 7이 될 것이고, 곱하면 8이 될 것이다.
해시 함수가 유효하려면, 동일한 문자열을 해시 함수에 적용할 때마다 동일한 숫자로 변환돼야 한다.
그런 점에서 현재 시간이나 난수를 사용하는 해시 함수는 유효하지 않다. 적용할 때마다 다른 결과가 나올 것이기 때문이다.
곱셈 해시 함수를 스면 BAD는 항상 8이다. 단, DAB 역시 8이 될 수도 있다는 점을 유의해야 한다.
8.3 재미와 이익, 특히 이익을 남길 유의어 사전 만들기
thesaurus라는 해시 테이블로 유의어 사전을 표현할 수 있다.
let thesaurus = new Map([["bad", "evil"]]);로 첫 번째 항목을 추가하면, 해시 테이블은 다음과 같다: Map(1) {'bad' => 'evil'}.
배열과 유사하게 해시 테이블은 내부적으로 데이터를 한 줄로 이뤄진 셀 묶음에 저장한다.
컴퓨터는 키에 해시 함수를 적용한다. 곱셈 해시 함수를 적용하면 "bad"는 8로 해싱되므로 값을 셀 8에 넣는다.
thesaurus.set("cab", "taxi");로 다른 키/값 쌍을 추가한다.
다시 컴퓨터는 키("cab")를 해싱해, 셀 6에 값("taxi")을 넣는다.
thesaurus.set("ace", "star");로 하나 더 추가하면, 셀 15에 "star"가 들어간다.
현재 해시 테이블은 다음과 같다: Map(3) {'bad' => 'evil', 'cab' => 'taxi', 'ace' => 'star'}
8.4 해시 테이블 룩업
해시 테이블에서 항목을 룩업할 때는 키를 사용해 연관된 값을 찾는다.
가령, thesaurus.get("bad");라는 코드로 "bad"의 값을 룩업하려 한다.
컴퓨터는 룩업하고 있는 키("bad")를 해싱한 후, 결과에 해당하는 인덱스에 찾아가 저장된 값("evil")을 반환한다.
해시 테이블에서 각 값의 위치는 키로 결정된다.
즉, 키 자체로 값을 어디서 찾을 수 있는지 알 수 있다. 키를 해싱해서 이전에 값을 넣었던 곳을 찾을 수 있기 때문이다.
키를 해싱하는 과정은 상수 시간이 걸릴 것이므로, 해시 테이블의 값 룩업은 O(1) 이다.
배열에서 메뉴 항목의 값을 룩업하려면 항목을 찾을 때까지 각 셀을 순회해야 한다.
정렬되지 않은 배열이라면 최대 O(N)이고, 정렬된 배열이라면 최대 O(logN)이 걸린다.
해시 테이블이라면 메뉴 항목을 키로 해서 O(1)만에 할 수 있다.
8.4.1 단방향(one-directional) 룩업
해시 테이블에서 한 단계만에 값을 찾는 기능은 그 값의 키를 알 때만 가능하다.
키를 모른 채 값을 찾으려면 해시 테이블 내 모든 키/값 쌍을 검색해야 하고 이는 O(N)이다.
값을 이용해 키를 찾을 때 역시 O(1) 룩업은 불가능하다.
즉, 해시 테이블의 빠른 룩업은 키→값의 단방향으로만 동작한다.
각 키는 해시 테이블에 딱 하나만 존재할 수 있으나 값은 여러 인스턴스가 존재할 수 있다.
가령, 해시 테이블에 햄버거는 두 번 나열할 수 없다. 하지만 2.5달러짜리 메뉴는 여러 개 있을 수도 있다.
8.5 충돌 해결
만일 위의 유의어 사전 해시 테이블에 thesaurus.set("dab", "pat");로 키/값 쌍을 추가한다면, 충돌이 발생한다.
키인 "dab"의 해싱 값이 8인데, 이미 셀 8에 "evil"이 들어있기 때문이다.
이미 채워진 셀에 데이터를 추가하는 것을 충돌(collision) 이라 부른다.
충돌을 해결하는 고전적인 방법으로 분리 연결법이 있다.
충돌이 발생했을 때 셀에 하나의 값을 넣는 대신 배열로의 참조를 넣는 방법이다.
셀 8을 { ["bad", "evil"], ["dab", "pat"] }로 대체한다. 각 하위 배열의 인덱스 0은 단어, 인덱스 1은 동의어다.
thesaurus.get("dab");으로 룩업한다면, 컴퓨터는 "dab"을 해싱해서 셀 8을 룩업한다.
셀 8이 배열들의 배열을 포함하고 있음을 알게 되고, 각 하위 배열의 인덱스 0을 찾아보며 "dab"을 찾을 때 까지 차례대로 검색한다.
컴퓨터가 확인 중인 셀이 배열을 참조한다면, 다수의 값이 들어 있는 배열을 선형 검색해야 한다.
만약 모든 데이터가 해시 테이블의 한 셀에 들어간다면 배열보다 나을 게 없다.
따라서 최악의 경우 해시 테이블 룩업 성능은 사실상 O(N)이다.
그러므로 해시 테이블에 충돌이 거의 없도록 디자인해야 한다.
8.6 효율적인 해시 테이블 만들기
해시 테이블은 다음 세 요인에 따라 효율성이 정해진다.
- 해시 테이블에 얼마나 많은 데이터를 저장하는가
- 해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가
- 어떤 해시 함수를 사용하는가
적은 셀에 많은 데이터를 저장한다면 충돌이 많을테고 해시 테이블의 효율성이 떨어질 것이다.
해시 함수가 특정 범위의 셀만을 사용하는 경우에도 효율성이 떨어질 것이다.
좋은 해시 함수란 사용 가능한 모든 셀에 데이터를 분산시키는 함수다.
8.6.1 훌륭한 충돌 조정
이론상 충돌을 피하는 최선의 방법은 해시 테이블에 많은 셀을 두는 것이다. 하지만 데이터 5개를 저장하겠다고 셀 1000개를 사용하는 것은 메모리 낭비다.
좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피한다.
저장할 데이터와 저장 가능한 셀의 비율을 부하율이라고 하며, 이상적인 부하율은 0.7이다.
해시 테이블 내부는 대부분 사용자가 쓰고 있는 컴퓨터 언어가 관리한다. 프로그래밍 언어가 최고의 성능을 내도록 해시 테이블을 구현했다고 가정해도 무방하다.
8.7 해시 테이블로 데이터 조직
해시 테이블은 데이터를 쌍으로 저장하므로 데이터를 조직하는 많은 시나리오에 유용하다.
어떤 경우에는 조건부 로직을 간소화할 수도 있다.
const statusCodeMeaning = (number) => {
if (number === 200) {
return "OK";
} else if (number === 301) {
return "Moved Permanently";
} else if (number === 401) {
return "Unauthorized";
} else if (number === 404) {
return "Not Found";
} else if (number === 500) {
return "Internal Server Error";
}
};해시 테이블로 조건부 로직을 완벽하게 없앨 수 있다.
const STATUS_CODES = new Map([
[200, "OK"],
[301, "Moved Permanently"],
[401, "Unauthorized"],
[404, "Not Found"],
[500, "Internal Server Error"],
]);
const statusCodeMeaning = (number) => {
return STATUS_CODES.get(number);
};다양한 속성을 갖는 객체를 표현할 때도 흔히 쓰인다. 예를 들어 개를 다음처럼 표현할 수 있다.
const fido = new Map([
["Name", "Fido"],
["Breed", "Pug"],
["Age", 3],
["Gender", "Male"],
]);8.8 해시 테이블로 속도 올리기
해시 테이블은 쌍이 아닌 데이터라도 코드를 빠르게 만들 때 쓰일 수 있다.
배열 [61, 30, 91, 11, 54, 38, 72]에서 어떤 수를 찾으려면 N단계의 선형 검색을 수행해야 한다.
하지만 이 수 배열을 const hashTable = new Map([[61, true], [30, true], [91, true], [11, true], [54, true], [38, true], [72, true]]);이라는 해시 테이블로 변환한다면 수를 찾을 때 한 단계면 된다. hashTable.get(72).
만일 찾으려는 수가 해시 테이블 안에 있다면 true를 받는다. 만일 없는 값을 찾는다면 자바스크립트는 undefined를 반환한다.
여기서 해시 테이블은 쌍으로 된 데이터가 아니라 수 리스트를 처리할 뿐이다. 각 키에 대한 값으로 true를 사용했으나, 다른 어떤 임의의 참인(truthy) 값을 사용해도 결과는 같다.
8.8.1 배열 부분 집합
["a", "b", "c", "d", "e", "f"]와 ["b", "d", "f"] 배열이 있다고 치자. 두 번째 배열은 첫 번째 배열의 부분집합이다. ["b", "d", "f", "h"] 배열은 첫 번째 배열의 부분집합이 아니다.
두 배열을 비교해 한 쪽이 다른 쪽의 부분집합인지 알려주는 함수를 작성하고자 한다.
중첩 반복문을 통해 작성할 수 있다.
const isSubset = (array1, array2) => {
let largerArray;
let smallerArray;
if(array1.length > array2.length) {
largerArray = array1;
smallerArray = array2;
} else {
largerArray = array1;
smallerArray = array2;
}
for (let i = 0; i < smallerArray.length; i++) {
let foundMatch = false;
for(let j = 0; j < largerArray.length; j++) {
if(smallerArray[i] === largerArray[j]) {
foundMatch = true;
break;
}
}
if(foundMatch === false) { return false; }
}
return true;
}이 알고리즘은 첫 번째 배열의 항목마다 두 번째 배열을 순회한다. 따라서 O(N * M)이다.
해시테이블을 통해서도 작성할 수 있다.
const isSubset = (array1, array2) => {
let largerArray;
let smallerArray;
let hashTable = new Map();
if (array1.length > array2.length) {
largerArray = array1;
smallerArray = array2;
} else {
largerArray = array1;
smallerArray = array2;
}
for (const value of largerArray) {
hashTable.set(value, true);
}
for (const value of smallerArray) {
if (!hashTable.get(value)) {
return false;
}
}
return true;
};이 알고리즘은 두 배열을 각각 한 번씩만 순회한다. 따라서 O(N + M)이므로 O(N)이다.
O(N * M)에 비하면 엄청난 개선이다.
해시 테이블을 인덱스로 사용하는 이 기법은 배열을 여러 번 검색해야 하는 알고리즘에 자주 쓰인다. 알고리즘에서 배열의 값을 계속 검색해야 한다면 매 검색에만 N단계가 걸리기 때문이다.
8.9 마무리
해시 테이블은 효율적인 소프트웨어 개발에 필수다. O(1) 읽기와 삽입은 쉽게 따라잡을 수 없는 자료 구조다.
