TIL(2일차)

해시테이블(Hash Table)

 

처음에는 내 맘대로 정의하는거 보다 정확한 사이트에서 가져오는게 맞을것 같아서 wikipida의 정의를 보았다.

 

In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type, that maps keys to values.  A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.

 

컴퓨터에서 해시 테이블은 연관배열 또는 딕셔너리를 구현한 자료구조라고 한다. 또 해시 테이블은 키 와 값을 매핑하는 추상 자료형이라고 한다. 해시 테이블은 원하는 값을 찾을 수 있는 버킷 또는 슬롯 의 배열로 해시 코드 이라고 하는 인덱스를 계산하기 위해 해시 함수를 사용한다. 조회하는 동안 키가 해시되고 결과 해시는 해당 값이 저장된 위치를 나타낸다.

 

 

---

 

해시테이블(Hash Table) 구조

 

 

 

 

해시 테이블은 고유한 input 값인 key값에 해시 함수를 걸쳐 value와 1:1 관계를 가지게 된다.

 

그리고 배열과 같은 공간에 index를 생성하고 값을 저장한다.

 

여기서 실제 값이 저장되는 장소를 버킷이라고 한다.

 

또한 키가 해시 함수(Hashing function)를 거쳐 해시로 변환되는 과정을 해싱(Hashing)이라고 하는데 Hashing function 에 대해 간단하게 설명하겠다.

 

 

---

 

해싱 함수(Hashing Function)

 

키 값을 버킷(bucket)의 주소에 대응시키는 방법을 Hashing Function 이라고 한다.

 

Hashing function 조건

- 주소 계산이 빨라야한다.

 

- 가급적 결과 값이 중복되어서는 안된다.

 

bucket과 hash table과 적재밀도 등을 고려해야한다.

 

여기서 적재 밀도(Loading density)가 뭔지 아리송 하다.

 

적재 밀도란

 

저장된 레코드의 수 /  공간의 총 용량 으로 현재 차 있는 비율이라고 보면된다.

 

레코드 수 / 버킷 수 * 버킷 용량 < 1 이 유지되고

 

효율적인 적재밀도는 약 70% 라고 한다. 

---

해시 테이블(Hash Table) 시간복잡도

 

행위	평균	최악
탐색	O(1)	O(N)
삽입	O(1)	O(N)
삭제	O(1)	O(N)

 

Hash Table은 탐색에 특화된 자료구조인데 평균 O(1)의 시간 복잡도를 갖는다.

 

배열에서 인덱스를 아는 상태에서 접근하는 것과 비슷하다고 생각하면 되는데 평균 O(1)이고

 

해시 충돌이 일어날수록 최악인 O(N)에 수렴하게 된다.

 

Red Black트리를 이용하면 O(log N)으로 줄일 수 있다고 하는데 이것은 나중에 따로 포스팅 하도록 하겠다.

 

아래에서는 해시 충돌에 대해 설명하겠다.

 

 

---

 

해싱 충돌(Hash Collision)

 

해시 충돌은 고유해야 하는 해시 값을 두 개의 입력값(key)이 공유 하는 상황을 의미한다.

 

 

 

 

해시 충돌은 우연하게 발생하게 되고 해시 알고리즘에 의해 발생하게 된다.

 

해시 충돌은 피할 수 없기 때에 충돌을 해결하는 매커니즘이 존재한다.

 

일반적으로 개방형 주소 지정(Open addressing) 과 분리연결법 (Separate Chaning)을 사용한다.

 

분리 연결법(Separate Chaning)

 

- 버킷에 겹친 데이터에 대해 추가 메모리를 사용하여 다음 데이터의 주소를 저장한다.

 

- 그림처럼 동일한 버킷에 겹친 데이터들을 따로 Linked List를 사용하여 관리한다.

 

장점 : 해시 테이블을 확장할 필요가 없어지고 간단하게 구현이 가능하고 삭제도 비교적 쉽다.

 

단점: 데이터의 수가 많아 지면 해당 버킷에 대해 chaining 되는 데이터가 많아지고 캐시 효율성이 감소한다.

 

 

개방 주소법(Open Addressing)

 

선형조사법 interval을+1 한 그림

 

 

개방 주소법이란 Chainig 방법과는 다르게 메모리를 추가로 사용하지 않고 비어있는 테이블의 공간을 활용하는 방법이다.

 

개방 주소법도 대표적으로 3개의 조사법(Probing)이 있다.

 

- 선형 조사법 (Linear Probing): 현재 주소에서 고정폭 만큼 이동해서 차례대로 검색해 비어 있는 주소에 데이터를 저장한다.

 

- 제곱 조사법 (Quadratic Probing) : 저장순서의 폭을 제곱해서 충돌이 발생하면 1만큼 이동하고 그 다음 계속 발생하면 n^2, (n+1 )^2와 같이 주소를 이동시키는 방법

 

- 이중 해싱 (Double Hashing): 해시된 값을 다시 한번 해싱해서 해시의 규칙성을 없애 버리는 방법으로 해싱을 또하기 때문에 연산이 많아지게 된다.

 

 

 

 

 

 

 

참고 자료 : https://en.wikipedia.org/wiki/Open_addressing

Open addressing - Wikipedia

https://en.wikipedia.org/wiki/Hash_table

Hash table - Wikipedia

 

https://velog.io/@edie_ko/hashtable-with-js

자료구조 | 해시 테이블 hash table