자바스크립트는 High Level Language로, Low Level 메모리를 관리할 수 없다.
따라서 해시테이블을 구현할 땐, 빈객체 / 배열을 사용한다.
John Smith(key)
의 전화번호인 521-1234(value)
를 저장한다고 하자.
입력된 John Smith(key)
를 Hash function
에 적용해서 02(Hash)
라는 값을 얻는다.
그러면 "521-1234"(value)
는 미리 확보한 공간(0~15번) 중
02(Hash)
에 저장하게 된다.
이후 Key 값으로 John Smith를 입력하면, Hash Function을 통해 02라는 위치값을 알게되고, 그 위치에 저장된 521-1234라는 Value값을 얻어낼 수 있다.
키(key)는 해시함수(hash function)를 통해 해시(hash)로 변경이 되며 해시는 값(value)과 매칭되어 저장소에 저장이 된다.
해시테이블에서 자료를 저장하기 위해서는 해시 함수(hash function)으로 키(key)를 해시로 변경해야 한다. 위의 사진처럼 해시함수가 input key를 7로 나눈 나머지를 변경해서 출력했을때, 키는 '76', 해시는 '6'이다.
그러면 미리 준비해놓은 0, 1, 2, 3, 4, 5, 6의 저장소 중에 맞는 해시 값을 찾아 해당 값을 저장한다.
해시 함수로 해시를 산출하는 과정에서 서로 다른 key가 같은 hash로 변결되는 문제가 발생할 수 있는데 이는 key와 value가 1:1로 매칭이 되어야 한다는 규칙을 위해한 것으로 이 문제를 해결하면서 저장 되어야 한다.
저장 단계의 시간 복잡도는 O(1)이다. 키는 고유하며 해시함수의 결과로 나온 해시와 값을 저장소에 넣으면 되기 때문이다. 이 때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
하지만 최악의 경우 O(n)이 될 수 있다. 해시 충돌로 인해 모든 저장소의 값들을 찾아봐야 하는 경우도 있기 때문이다.
저장되어 있는 값을 삭제할때는 저장소에서 해당 key와 매칭되는 값을 찾아서 삭제하면 된다.
( 저장소에는 hash와 값이 함께 저장되어 있으므로 함께 지우면 된다.)
삭제 단계의 시간 복잡도는 O(1)이다. 키는 고유하며 해시함수의 결과로 나온 해시에 매칭되는 값을 삭제하면 되기 때문이다. 이때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
하지만, 최약의 경우 O(n)이 될 수 있다. 해시 충돌로 인해 모든 저장소의 값들을 찾아봐야 하는 경우가 있다.
키로 값을 찾아내는 과정은 Deletion 과정과 비슷하다.
1) 키로 hash를 구한다.
2) hash로 값을 찾는다.
저장 단계의 시간 복잡도는 O(1)이다. 키는 고유하며 해시함수의 결과로 나온 해시에 매칭되는 값을 찾으면 되기 때문이다. 이 때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
최악의 경우로 O(n)이 될 수 있다.
해시테이블은 Insertion, Deletion, Search 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가지고 있기 때문에 자료구조의 효율성 측면에서 매우 우수하다고 볼 수 있다.
하지만, 해시를 이용한 자료구조 방식에 필욘적으로 다른 key 값이지만, 같은 Hash 값이 나올때가 있다. 이런 현상을 해시 충돌이라 한다.
해시 충돌을 해결하는 방법은 크게 2가지가 있다.
체이닝(Chaining)은 자료 저장 시, 저장소에서 충돌이 일어나면 해당 값을 기존 값과 연결시키는 기법이다.
위 사진에서 Sandra를 저장할 때 충돌이 일어났고, 기존에 있던 John에 연결시켰다. 이때 연결리스트(Linked List) 자려구조를 이용한다. 다음에 저장된 자료를 기존의 자료 다음에 위치시키는 것이다.
체이닝의 장단점
복잡도를 계산하기 전, 한 가지를 추가하자면 해시 테이블의 저장소의 길이를 'n', 키의 수를 'm'이라고 가정했을 때, 평균적으로 저장소에서 1개의 해시당 (m/n)개의 키가 들어있다. 이를 'α'라고 정의한다.
m/n = α (1개의 Hash당 평균적으로 α개의 키가 들어있다.)
개방주소법은 데이터의 해시가 변경되지 않았던 chaining과는 달리 비어있는 해시를 찾아 데이터를 저장하는 기법이다. 따라서 개방주소법에서의 해시테이블은 1개의 해시와 1개의 값이 매칭되어 있는 형태로 유지된다.
비어있는 해시를 찾는 과정은 동일해야 한다.(일정한 규칙을 따라 찾아가야 한다.)
Open Addressing 방법에는 3가지가 있다.
장점
1) 또다른 저장공간 없이 해시테이블 내에서 데이터 저장 및 처리가 가능하다.
2) 또 다른 저장공간에서의 추가적인 작업이 없다.
단점
1) 해시 함수의 성능에 전체 헤시테이블의 성능이 좌지우지된다.
2) 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해두어야 한다.
chaining에서 정의한 'α'를 Open Addresing에서도 정의하자면, 해시 테이블의 저장소의 길이를 'n', 키의 수를 'm'이라고 가정했을때, 'α'는 1보다 작거나 같다. 저장소 1개 버킷당 1개의 값만 가지기 때문이다.
Insertion & Deletion & Search :
삽입, 삭제, 검색 모두 대상이 되는 Hash를 찾아가는 과정에 따라 시간복잡도가 계산이 된다. 해시함수를 통해 얻은 Hash가 비어있지 않으면 다음 버킷을 찾아가야 한다. 이 찾아가는 횟수가 많아지면 많아질 수록 시간복잡도가 증가한다. 최상의 경우 O(1) ~ 최악의 경우 (O(n)).
따라서 Open Addressing에서는 비어있는 공간을 확보하는 것(= 저장소가 어느 정도 채워졌을 때 저장소의 사이즈를 늘려주는 것)이 필요하다.
최악의 경우 저장소를 모두 살펴보아야 하는 경우가 생길 수 있다.(O(n))
멱등 법칙이란? 연산을 여러 번 적용하더라도 결과가 달라지지 않는 성질
해시 테이블은 키를 가지고 빠르게 값에 접근하고 조작할 수 있는 장점이 있어서 많이 사용된다. 예를 들어 주소록 저장형태의 경우 이름 - 전화 번호의 매칭을 이용해 데이터를 처리한다.