[알고리즘] 해시 알고리즘

해시 테이블

해시 테이블은 key-value 쌍을 저장하는데, 해싱된 key를 인덱스로하여 값을 찾는 비선형 자료구조이다.
해시함수를 통해 key를 고정된 크기 내의 값으로 변환해 해당 값을 key로 지정하여 value를 저장한다.

자바스크립트의 해시 테이블

자바스크립트에서는 Object, Set, Map 객체를 해시 테이블로 사용할 수 있다.

Object와 Set, Map 차이점

Object에서는 문자열과 심볼만 Key로 사용할 수 있지만,
Set과 Map에서는 문자열, 숫자, 함수 등 다양한 타입을 Key로 사용할 수 있다.

Set과 Map은 해시 맵이라고 한다.

Set과 Map의 차이점

가장 큰 차이점은 Set은 Key 중복이 발생하지 않는다는 점이다.

해시 알고리즘

해시 알고리즘은 주어진 데이터를 정해진 크기 내의 값으로 변환 후 해당 값을 반환하는 알고리즘이다.
해싱된 key가 이전에 해싱되었던 key와 충돌할 수도 있는데, 이때 충돌을 대처하는 방식(open addressing)을 사용할 수 있으나 primary clustering 과 secondary clustering이 발생할 수 있다.

primary clustering: 데이터가 특정 위치에 밀집되어 있는 것을 말한다. (Linear Probing이 해당 문제에 취약)
secondary clustering: 여러 개의 슬롯이 동일한 초기 해시 값을 갖는 것을 말한다. (Quadratic Probing이 해당 문제에 취약)
잘 만들어진 해시 알고리즘을 통해 반환된 해시값은 충돌이 잘 발생하지 않는다.

코딩테스트에서 해시 알고리즘이라고 하면 키와 값을 가지고 답을 찾는 걸 말하는 거 같다.