8장이 끝날 때까지 데이터를 O(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)이다.
A=1, B=2, C=3 ... 이라는 비밀 코드를 만든다고 가정하자. 가령, BAD는 214로 변환된다.
위 과정에서, 문자를 가져와 숫자로 변환하는 이러한 과정일 해싱이라 부른다. 또한, 글자를 특정 숫자로 변환하는 데 사용한 코드를 해시 함수라 부른다.
해시 함수는 이 밖에도 많다. 문자를 숫자로 변환해 모든 숫자를 합치거나 곱해서 반환할 수도 있다. BAD의 예시에서 합치면 7이 될 것이고, 곱하면 8이 될 것이다.
해시 함수가 유효하려면 딱 한 가지 기준을 충족해야 한다. 해시 함수는 동일한 문자열을 해시 함수에 적용할 때마다 항상 동일한 숫자로 변환해야 한다. 그런 면에서 주어진 문자에 대해 반환하는 결과가 일관되지 않으면 그 해시 함수는 유효하지 않다. 적용할 때마다 다른 결과가 나올 것이기 때문이다.
곱셈 해시 함수를 쓰면 BAD는 항상 8이다. 단, DAB 역시 8이 될 수도 있다는 점을 유의해야 한다.
thesaurus라는 해시 테이블로 유의어 사전을 표현할 수 있다.
let thesaurus = new Map([["bad", "evil"]]);로 첫 번째 항목을 추가하면, 해시 테이블은 다음과 같다: Map(1) {'bad' => 'evil'}.
배열과 유사하게 해시 테이블은 내부적으로 데이터를 한 줄로 이뤄진 셀 묶음에 저장한다.컴퓨터는 키에 해시 함수를 적용한다. 곱셈 해시 함수를 적용하면 "bad"는 8로 해싱되므로 값을 셀 8에 넣는다.
thesaurus.set("cab", "taxi");로 다른 키/값 쌍을 추가한다.다시 컴퓨터는 키("cab")를 해싱해, 셀 6에 값("taxi")을 넣는다.