Hash란?
해시(Hash)는 임의의 크기를 가진 데이터를 (키,값) 데이터로 매핑하는 것을 말합니다. 이때 매핑된 데이터를 해시값이라고 하며, 해시 함수(Hash Function)라는 알고리즘이 이용된다.
해시 자료구조는 이러한 해시 함수를 이용하여 데이터를 저장하고 검색하는 방식이다. 해시 함수를 이용하여 데이터의 키 값을 해시값으로 변환한 후, 해당 해시값을 인덱스로 하는 배열에 데이터를 저장한다. 이렇게 저장된 데이터는 매우 빠른 검색 속도를 가진다.
사용하는 이유
'그래서 이게 뭐가 대수지?'라고 생각할 수가 있다. Hash가 없던 시절을 생각해보자면 자주 사용하는 배열이라는 자료구조는 오직 정수로만 접근이 가능했다. 때문에 키값을 알더라도 값에 접근할 수가 없었다. 접근할 수 있는 방법은 배열을 0부터 순회하면서 내가 찾는 키값이 배열의 인덱스번호와 같은지 확인하는 방법 뿐이였다. 이렇게 된다면 검색속도가 느려진다는 단점이 있다.
반면에 해시는 모든 데이터타입으로 접근이 가능하기 때문에 key를 이용하여 데이터를 빠르게 찾을 수 있다.
해시 함수의 문제점
하지만 해시는 해시 함수의 충돌(Collision)이 발생할 수 있기 때문에 충돌을 처리하는 방법이 필요하다.
해시 함수 충돌이 일어나는 이유는 여러 가지가 있을 수 있다. 가장 일반적인 이유는 해시 함수의 출력 범위보다 입력 범위가 더 큰 경우다. 이 경우 서로 다른 입력이 동일한 해시 값으로 매핑될 가능성이 높아진다. 또한 해시 함수 자체의 구현 문제, 즉 해시 함수가 충분히 무작위적이지 않은 경우에도 충돌이 발생할 수 있다.
해시 충돌을 해결하기 위해 일반적으로 두 가지 방법이 사용된다.
Separate Chaining
-해시 테이블의 각 슬롯에 연결 리스트를 사용하여 해시 충돌을 처리한다.
-충돌이 발생하면 해당 슬롯에 이미 데이터가 존재하는 경우 연결 리스트에 데이터를 추가한다.
-검색 작업 시에는 해당 슬롯에 대해 연결 리스트를 순회하여 데이터를 찾는다.
Open Addressing
-해시 충돌이 발생한 경우, 다른 빈 슬롯을 찾아서 데이터를 저장한다.
-선형 조사, 이차 조사, 이중 해싱 등의 방법으로 빈 슬롯을 찾는다.
-검색 작업 시에는 해당 슬롯에서 시작하여 일정한 규칙에 따라 다음 슬롯을 탐색하여 데이터를 찾는다.
해시 자료구조는 검색, 삽입, 삭제 연산이 모두 평균적으로 O(1)의 시간 복잡도를 가지기 때문에 많은 분야에서 활용된다. 예를 들어, 해시 테이블(Hash Table)이라는 자료구조는 해시 기법을 이용하여 데이터를 저장하는 자료구조로, 검색, 삽입, 삭제 연산에 매우 높은 성능을 보입니다.
자바스크립트 배열과 해시 테이블
사실 자바스크립트의 배열은 일반적인 다른 언어에서의 배열과 다르다. 일반적인 배열은 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열된 자료 구조를 말한다. 즉, 배열의 요소는 하나의 타입으로 통일되어 있으며 서로 연속적으로 인접해 있다. 이러한 배열을 밀집 배열(dense array)이라 한다.
이처럼 배열의 요소는 동일한 크기를 갖으며 빈틈없이 연속적으로 이어져 있으므로 아래와 같이 인덱스를 통해 단 한번의 연산으로 임의의 요소에 접근(임의 접근(random access), 시간 복잡도 O(1))할 수 있다. 이는 매우 효율적이며 고속으로 동작한다.
자바스크립트의 배열은 지금까지 살펴본 일반적인 의미의 배열과 다르다. 즉, 배열의 요소를 위한 각각의 메모리 공간은 동일한 크기를 갖지 않아도 되며 연속적으로 이어져 있지 않을 수도 있다. 배열의 요소가 연속적으로 이어져 있지 않는 배열을 희소 배열(sparse array)이라 한다.
이처럼 자바스크립트의 배열은 엄밀히 말해 일반적 의미의 배열이 아니다. 자바스크립트의 배열은 일반적인 배열의 동작을 흉내낸 특수한 객체이다.
일반적인 배열은 인덱스로 배열 요소에 빠르게 접근할 수 있다. 하지만 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 효율적이지 않다.
자바스크립트 배열은 해시 테이블로 구현된 객체이므로 인덱스로 배열 요소에 접근하는 경우, 일반적인 배열보다 성능적인 면에서 느릴 수 밖에 없는 구조적인 단점을 갖는다. 하지만 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 일반적인 배열보다 빠른 성능을 기대할 수 있다.
