해쉬테이블은 key-value로 구성되며, 순서를 보장하지 않으며 랜덤한 값을 빠르게 접근하기 위해 사용된다.
또한, 중복된 key를 허용하지 않기 때문에, key에 대응하는 value는 유일하게 존재한다.
해쉬테이블의 좋은 예시는 사전이다.(실제로 파이썬에서는 해쉬테이블을 dictionary라는 자료구조로 사용한다.)
사전에서 cat이라는 단어를 찾을 때, a부터 시작하여 b, c까지의 모든 단어들을 순차적으로 찾아볼 필요없이
처음부터 c로 시작하는 부분을 찾아가 cat을 찾을 수 있다.
때문에 해쉬테이블의 시간복잡도는 O(1)이 된다.
여기서 c는 해쉬테이블의 key가 되고, cat은 해쉬테이블의 value가 된다.
해쉬테이블의 c의 인덱스에는 cat이라는 값이 존재한다는 뜻이다.
그러면 여기서 문득 의문이 든다.
인간은 어쨋든 c라는 알파벳이 a,b다음으로 오는 알파벳이라는 것을 알기 때문에
'3번째 페이지를 확인하면 되겠구나!'라고 생각할 수 있다.
하지만 숫자(그것도 0, 1) 밖에 모르는 컴퓨터에게 c라는 알파벳이 가리키는 인덱스가
어디인지 어떻게 알려줄까.
이 자료구조의 이름에서도 알 수 있듯 Hash(해쉬)를 이용해서 문자열도 숫자로 넘길 수 있다.
key로 들어온 값을 해쉬함수를 사용해 숫자로 만들어준 뒤 그것을 인덱스로 사용하는 것이다.
(해쉬 함수는 다양하게 있고 나중에 한 번 작성해보기)
해쉬테이블이 생성되면 기본적으로 일정 크기의 배열이 만들어진다.
예를 들어, 10개의 공간을 가지는 해쉬테이블이 생성되었다고 해보겠다.
그러면 인덱스는 0부터 9까지의 값을 가진다.
만약 c라는 알파벳을 해쉬함수를 통해 숫자로 바꿨을 때 97(아스키코드로 이 근처이긴 한데..)이 나온다면?
인덱스는 0부터 9까지이기 때문에 테이블에 넣을 수 없게 된다.
때문에 key값을 해쉬한 뒤에 테이블의 크기로 나눈 나머지를 인덱스로 사용한다.
(사실 이 과정이 해쉬 함수에 포함되어있다. 또한 이 외의 방법으로도 인덱스를 정할 수 있다.)
그럼 97 % 10 = 7 이므로, c라는 key값은 7번째 인덱스를 가리키며 7번째 인덱스에는 cat이라는 value가
저장되는 것이다.
정말 기초가 되는 자료구조이지만, 여태까지 정확한 작동원리를 모르기도 했고 제대로 알아보려고 작성을 시작했다.
추가할 내용이 많지만 일단 여기까지.. 앞으로 이 글에 차차 더해나가야겠다.