[CS] 해시 테이블은 뭘까

해시테이블은 키와 값, 쌍으로 이루어진 표같은 형태를 가지고 있습니다.

이때, 해시함수의 역할은 키를 인자로 활용해 인덱스로 반환시키는 역할을 합니다.

결국 키는 해시함수를 통과하여 원하는 버킷에 접근 할 수 있습니다.

해시함수는 임의의 길이를 지닌 데이터를 고정된 길이의 데이터로 변화하는 단방향 함수를 의미합니다.

따라서 해시값에 담긴 값이 키로 변환 될 수는 없다는 것을 의미합니다.

예를들어 웹페이지를 만들 때 비밀번호를 만드는 과정을 연상하면 되는데요.

사용자가 비밀번호를 누르면 보안을 위해 순수하게 사용자가 입력한 번호값을 저장하는것이 아니라

임의의 글자가 뒤죽박죽인 글자로 저장하게 되죠.

하지만 이 임의의 글자를 비밀번호로 다시 변환시킬 수는 없습니다.

해시는 해시 알고리즘을 통해 연산을 하는데

해시 알고리즘이란 수신자가 입력할 값과 해시값에서 저장해 둔 값이 일치하는 알고리즘을 의미합니다.

그렇기 때문에 검색속도가 빠른게 장점이며 이것이 해시 자료구조형을 사용하는 이유가 됩니다.

하지만 메모리 공간 소모가 많다는 단점도 있습니다.

그런데 해시테이블의 키가 항상 다른 해시값을 가르키지만은 않습니다.

여러개의 키가 같은 해시값을 가리키면 이것을 해시 충돌이라 일컫습니다.

해시 충돌을 해결하는 방법이 몇가지 있는데요,

1. 체이닝

체이닝은 서로 다른키가 같은 위치로 해시 값을 가리켜도 해시 값에 연결리스트의 노드를 추가해 해시 충돌을 해결하는 방법이 있습니다.

2. 개방주소법

해시키가 같은 해시값을 가리킬때 자리가 없는 인덱스를 피해 다른 인덱스를 찾아보는 활동인데 이를 조사라고 표현합니다.

선형조사법 같은경우 인덱스를 순차적으로 찾게 되는데

이는 한 인덱스에 많이 접근하게 되는 데이터 군집화가 일어나서 성능이 느려질 수도 있습니다.

3. 이중해싱

2개의 해시함수를 사용해서 키가 같은해시값을 가리키더라도 보조함수의 해시값으로 이동시켜 해시 충돌을 막는 방법이 있습니다.

이러한 해싱자료구조는 자바스크립트에서도 살펴볼 수 있는데요.

Map, Set , Object, WeakMap, WeakSet 자료형이 있습니다.

GSC4