Javascript - Hash Table(데이터 구조)(3)

이번 포스트는 data constructure 중에 Hash Table이다.

hash 는 뜻이 해시(고기와 감자를 잘게 다져서 섞어 요리하여 따뜻하게 차려 낸 것)이라고 한다. 프로그래밍에서 hash table은 hash 함수를 거쳐서 함수에 들어오는 인자를 하나의 고유의 값으로 바꾸어 data를 table에 기록한것처럼 저장한다.

 

from 위키피아

 

 

Hash Table 특징

 - 장점

   1. hash table은 주로 배열을 사용하는데, hash table 크기는 배열을 벗어나지 않는다.

   2. 인자로 들어오는 값(key)는 해시 함수를 거쳐서 특정 index를 값을 부여받고 여기에 value를 저장한다. 즉, 항상 같은 값을 출력할 수 있다.

  *원하는 데이터 값을 빠르게 찾을 수 있다.

  *두 개 이상의 값에 하나의 키를 사용할 수 없다(즉. 키와 값을 한 쌍으로 저장할 수 있는 자료구조)

  *같은 키를 가지고 왔을 때, 나중에 저장된 값을 덮어씌워진다.(같은 키가 있을 때, error가 발생 안하도록 해야한다.)

   3. Hash table은 항상 같은 값을 출력하기 때문에 메모리에 이전의 값을 저장할 필요가 없어서 메모리 효율이 좋다. 또한, 이러한 특징 때문에 데이터를 손쉽게 찾을 수 있다. (Big - O 표기법으로 표시하면 O(1) 이다. 나중에 언급 하겠지만, O(1)이 가장 빠르다는 뜻이다.)

 

 - 단점

   * 해쉬 함수를 돌렸을 때, 같은 index 값을 부여 받을 수 있으며, 이럴 때 충돌이 일어난다.(이것을 해결 해주는 코드가 필요)

   * 충돌 해결 방법

       - separate chaining : 해시 충돌이 발생하면 연결리스트로 데이터들을 연결

       - open addressing : 해시 충돌이 발생하면 남는 버켓에 데이터를 삽입(제곱법이라고 하는데 더 많은 충돌을 일으킬 확률이 높다)

 

 Hash table 용어

 - Hashing : 인자를 받고 hash 함수를 통해 고유의 index 값을 받고, 저장, 필요한 값을 출력하는 과정을 의미한다.

 - storage : 저장하는 배열을 의미

 - bucket : 저장할 수 있는 공간을 의미(배열에서 index라고 생각하면 된다.)

 - tuple : 데이터를 담고 있는 공간이다. (쉽게 이해하기 위해 bucket이 행렬에서 열이라고 한다면, tuple은 행이라고 생각하면 된다.)

 

**코드 예제는 아직 codestates 과제를 마무리를 못 해서... 나중에 추가로 코딩 내용을 기록 예정 ㄷㄷ