해시테이블(hash table) 자료구조

해시 테이블을 사용하는 이유

• 삽입, 추가, 검색 속도가 매우 빠르다!
• 연속적인 흐름이 있는 데이터라면 배열을 사용하면 된다.

자바스크립트에서는 객체나 맵에 해당한다. (객체보다는 맵이 더 가깝다.)

해시 테이블은 기본적으로 key, value 쌍을 저장한다.

• 특정 key 에 해당하는 value 를 찾을 때 사용된다.

하지만 컴퓨터는 string 타입으로 된 key 를 이해하지 못하기 때문에 이 string 을 숫자로 바꿔줘야 한다.

• 이 과정을 hash 라고 한다.
• 이 과정은 hash 함수로 이뤄진다.
• 특정 길이의 배열이 있고 이 배열의 인덱스에 key, value 쌍을 넣는다.
• 그러기 위해서는 일단 빈 배열이 마련되어 있어야 하고 key 를 넣으면 배열의 어느 인덱스에 저장할지 결정이 되어야 한다. 이때 이 인덱스는 특정 key 를 넣었을 때 항상 같은 값을 반환하도록 정해져야 한다. 매번 다른 값이 나와서는 안된다.
• 항상 같은 값이 나오게 하기 위해서는 예를 들어 'hello'라는 단어를 key 로 사용할 때, hello 의 각 알파벳을 특정 숫자와 매칭을 시킬 수 있도록 한다. (utf-8 번호로 변환하는 방법이 있다.) 그렇게 하면 각 알파벳은 중복되지 않는 숫자로 1:1 매칭을 시킬 수 있다. 그 다음 각 알파벳에 해당하는 숫자를 다 더해서 total 값을 만든다. (여기까지가 해시 과정)
• 그런데 total 값으로 결국 인덱스를 정해야 하는데 이 배열의 전체 길이를 벗어나게 되면 안 되기 때문에, 이 total 값을 모듈로 연산해서 나머지를 이용하는 방법을 취한다. (예를 들어 배열의 길이가 10 이라면 10 으로 나눠서 그 나머지를 인덱스로 활용한다. 그럼 일정한 길이 범위 안의 인덱스를 구할 수 있다.)
• 그 구한 인덱스에 key, value 쌍을 저장하면 된다.

  그러므로, 결국 해시 테이블을 만드는 과정은, 특정한 key 와 value 쌍이 있고 key 를 집어넣으면 항상 value 를 반환하는 자료구조를 만들어야 하는 것이다. 이를 위해서 key 를 집어넣으면 해시 함수를 통해 해시 값을 만들고, 이 해시 값으로 인덱스를 생성해서 정해진 범위 안의 인덱스에 이 key-value 쌍을 저장한다.

여기까지만 보면 단순하지만, 해시 테이블을 만들 때 발생하는 문제점을 보완하는 것이 중요하다.

• 그 중에서 중요한 것은 충돌 문제다. 어떤 key 를 해시값 -> 인덱스로 변환을 했을 때 동일한 인덱스가 반환될 수 있다. 결국 동일한 인덱스에 중복된 key-value 쌍이 저장된다는 뜻이다.
• 이 문제를 해결하기 위해서 1. seperate chaining 2. linear probing 2가지 방법이 있다.
  • 1. seperate chaining: 동일한 인덱스에 중복된 key-value 값이 존재하도록 하는 방법이다. 이때 인덱스에 배열이 있고, 그 배열은 중첩된 배열이 된다. [[key1, value1], [key2, value2], ...] 와 같은 형태가 된다.
  • 2. linear probing: 동일한 인덱스에 중복된 key-value 를 허용하지 않는다. 인덱스를 생성하면 그 인덱스에 이미 key-value 가 추가되어있는지 확인하고, 만약 추가되어 있다면 그 인덱스의 앞뒤를 탐색해서 비어있는 인덱스에 값을 저장한다.
  • 일단 여기서는 1번 방법을 이용해서 충돌 문제를 해결한다.

set 메소드를 만든다.
- hash -> index 생성 -> 해당 인덱스가 비어있으면 빈 배열을 만들고, 빈 배열에 [key, value] 를 push 한다. 해당 인덱스가 비어있지 않으면 바로 [key, value] 를 push 한다.

get 메소드를 만든다.
- seperate chaining 으로 충돌을 해결한다는 과정 하에, 일단 인덱스로 배열을 찾으면 그 배열을 순회하면서 key 를 찾고 그 key 에 해당하는 value 를 찾는다.

해시 테이블의 삽입/삭제/검색의 시간복잡도는 O(1) 이다.

참고: 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스