딕서녀리와 해시는 유일한 값 (반복되지 않은) 을 저장하기 위한 자료 구조다
집합은 원소의 값이 유일한 값이라면
딕서녀리(또는 맵) 은 값을 키: 값 형태로 저장하고 키가 중복되지 않은 자료구조다
딕셔너리
딕셔너리는 맵이라고도 하고
집합은 값이 키, 키 형태지만
딕셔너리는 키,값 형태로 구성한다는 점이 다르다
자바스크립트의 Map 클래스는 딕셔너리를 구현한 자료구조다
해시 테이블
자바스크립트의 배열은 해시 테이블 구현된 객체이면서
희소 배열..? 이지만
조금 더 배열처럼 빠른 검색이 되도록 검색 속도를 최적화 하여 일반 객체보다 2배 빠른 검색이 가능하다고 한다
해싱은 자료구조에서 특정 값을 가장 신속하게 찾는 방법이다
딕셔너리에서는 값을 찾기 위해 전체 원소에 대해 루프를 실행한다
해시 함수는 어떤 키에 해당하는 값의 주소를
테이블에서 찾아주는 함수로 조회 속도가 매우 빠르고 간단하다
가장 흔한 형태의 해시 함수는 일명 루즈 루즈 해시 함수라고 하는데
키를 구성하는 문자의 아스키 값을 단순히 더한 것이다
'John' 이라는 키의 해시 함수는 74 + 111 + 104 + 110 으로
해시 값은 399 이다
그럼 399에 해당하는 테이블에 John 에 대한 값을 저장하는 것
이런 형태의 자료 구조는 배열을 사용해 나타낸다
해싱
getHashCode (key) {
let hash = 0
for (let i = 0;i < key.length; i++){
hash += key.charCodeAt(i) // 아스키 값
}
return hash % 37
}아스키 수치가 작은 영역이 있음을 감안해 hash를 임의의 숫자로 나눈 나머지를 최종값으로 반환한다고 하는데
무슨 말인지 모르겠다..
다 더해버리면 숫자가 너무 커져서 그런가..?
해시 테이블의 remove 는 원소의 값 자체를
삭제할 필요는 없다
배열 전체에 원소들이 고루 분포되어 있어
어떤 인덱스에는 값이 할당되지 않은 채
기본 값 undefined 가 들어있다
해시 테이블과 해시 집합 비교
위의 해시 테이블은 해시 맵과 동일한 자료 구조다
일부 프로그래밍 언어에서는 해시 집합 (hash set) 을 지원한다
새지 집합은 집합의 모습을 하고 있지만
원소의 삽입/삭제 접근 시 해시 함수를 이용한다
키-값 쌍이 아닌 값만 넣는다는 것이 다르다
비반복적인 값만 저장한다는 점에서
해시 집합이나 집합은 서로 같다고 볼 수 있다
해시 테이블 간 충돌 해결
키가 다르지만 해시 값이 똑같을 수도 있다
같은 키에 값을 새로 넣게되면 마지막에 넣은 값만 남게 되니 충돌을 해결해줘야 한다
해결 방법으로는 체이닝, 선형 탐사, 이중 해싱
세 가지의 방법이 있다
이중 해싱은 알아보지 않는다
체이닝
체이닝은 테이블의 인덱스별 연결 리스트를 생성해
그 안에 원소를 저장하는 기법이다
충돌을 해결하는 가장 단순한 방법이고
추가적인 메모리가 사용된다는 단점이 있다
선형 탐색법
선형 탐색법은 새 원소 추가 시 인덱스가 이미 점유 중일 경우 인덱스 + 1, +2 를 찾아보는 식으로 충돌을 회피한다
다른 프로그래밍 언어에서는 배열의 크기를 미리 정해야해서 인덱스가 벗어난 경우를 생각해야 하지만
자바스크립트에서는 원소 추가 시 자동으로 배열의 크기가 늘어나기 때문에 걱정할 필요가 없다
해시 함수 개선
루즈 루즈 해시 함수는 좋은 해시 함수가 아니다
너무 잦은 충돌을 야기하기 때문이다
좋은 해시 함수는 원소 삽입과 조회 속도가 빠르고
충돌 확률이 낮아야 한다
루즈 루즈 해시 함수를 개선한 djb2 해시 함수가 있다
const djb2Hash = (key) => {
let hash = 5381
for (let i = 0; i < key.length; i++) {
hash = hash * 33 + key.charCodeAt(i)
}
return hash % 1013
}hash 변수를 임의의 소수로 초기화 후 (자주 쓰이는 수가 5381)
hash 변수에 33(매직 넘버)을 곱하고
각 문자의 아스키 값과 더한다
마지막으로 hash 변수에 또 다른 임의의 소수로 나눈다(인스턴스가 가질 수 있는 크기보다 더 큰 수)
적어도 책이 작성될 때 까지는
전문가들이 즐겨쓰는 방법이었다고 한다
