(191120) - 자료구조 Hash Table

hash table.jpg

Hash Table

해시테이블은 내부적으로 배열을 사용하여 데이터를 저장을 하기 때문에 특정한 값을 탐색하거나 추출할 때, 데이터의 삭제나 추가시에 시간복잡도가 평균적으로 O(1)이 나온다. 이는 해시 테이블이 데이터 고유의 index를 사용하여 바로 접근하기 때문이다.

(평균적으로 O(1) 이고 O(N)이 나올 수도 있는데 조금 있다가 설명)

 

 

구성

해시 테이블은 기본적으로 키(key), 해시 함수(hash function), 해시(hash), 값(value), 저장소(bucket) 으로 이루어져 있다.

 

키(key) : 해시 함수의 input이다. 다양한 길이의 값일 수 있다.

 

해시 함수(hash function) : 키를 해시로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키를 input으로 받아 일정한 길이를 가지고 있는 해시(hash)로 변환하여 준다 (배열의 index 값이라 생각할 수 있다!!)

-> 이때 서로 다른 키가 우연히 해시 함수에 의해 같은 해시로 변환될 수 있는데 이것을 해시 충돌(hash collision)이라고 한다!

-> 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요

 

해시(hash) : 키가 해시함수를 통해 변환된 결과물로 저장소(bucket) 등에 저장될 때 값과 매칭이 되어 저장된다.

(즉, 배열에서 배열의 index 역할을 하고 element에 값이 담긴다)

 

값(value) : 저장소에 최종적으로 담기는 값으로 키와 매칭되어 데이터의 추가,삭제,검색이 된다.

 

 

먼저 해시테이블에 키와 값이 들어오게 되면 키는 먼저 해시 함수에 들어가게 되고 적절한 알고리즘을 통해 해시로 변환된다.

이 해시와 키와 같이 들어온 값을 매칭하여 저장소에 저장을 하는 것이다.

(즉, 위 배열의 경우 키가 해시함수를 통해 배열의 크기 내에서 배열이 index 값(숫자로) 변환이 되고 배열의 해당 index에 값이 element로 담기는 것이다)

 

 

해시테이블 자료구조의 장단점

장점 : 키를 가지고 빠르게 value에 접근하고 조작할 수 있다.

단점

- 해시테이블의 경우 키만 가지고 만들어진 해시에 저장을 하기 때문에 상하관계나 순서가 필요한 배열에는 좋지 않다.

- 공간 효율성이 떨어진다.

- 해시 함수의 의존도가 높다. (평균 데이터의 시간복잡도는 O(1)이지만, 해시 함수 자체의 시간복잡도는 고려하지 않은 것을 말하는 것이고 해시 함수의 성능이 좋지 않으면 밑에서 나온 해시 충돌이 많이 일어날 수도 있어서)

 

Hash method

해시 테이블의 method로는 

- 키와 값이 들어왔을 때 그 두 값을 저장하는 함수

- 키가 주어졌을 때 매칭되는 값을 얻는 함수

- 키와 새로운 값이 주어지면, 원래 키와 연관된 값을 새로운 값으로 교체할 수 있어야함

- 키가 주어졌을 때, 그 키와 연관된 값을 제거하는 함수

 

Insert (저장)

키와 값이 insert 함수의 input으로 들어오면

1. 먼저 키 값을 해시 함수에 넣어 해당하는 해시를 얻어낸다. (이때 해시는 배열의 크기 내에서 숫자로 나옴)

2. 해당 해시를 index로 저장소인 배열에 값을 element로 저장한다.

 

-> 저장의 시간 복잡도는 평균적으로 O(1) (왜냐하면 배열에 index에 값을 바로 넣어주면되므로)

-> O(N)이 될 수도 있는데 해시 충돌이 일어나 저장소를 모두 찾아봐야할 수도 있으므로

 

Deletion (삭제)

1. 먼저 삭제하려는 키 값을 해시 함수에 넣어 해당하는 해시를 얻어낸다.

2. 저장소인 배열에서 해당 해시를 index로 하는 값을 제거 (undefined로 할당?)

 

-> 저장과 동일한 시간 복잡도

 

Search (탐색)

1. 먼저 탐색하려는 키 값을 해시 함수에 넣어 해당하는 해시를 얻어낸다.

2. 저장소인 배열에서 해당 해시를 index로 하는 값을 리턴

 

-> 저장과 동일한 시간 복잡도

 

 

 

 

Hash collision (해시 충돌)

해시테이블에서 많은 키를 input으로 넣을 수 있지만 해시함수를 통해 나오는 해시는 한정되어 있기 때문에 (또는 해시가 키 만큼 많다고 하더라도, 우연히 같은 해시로 나오는 경우도 있기 때문에) 서로 다른 키를 넣더라도 같은 해시가 나올 수 있다.

이런 경우를 해시 충돌이라고 한다.

 

 

 

해시충돌 해결법

- Separate Chaning 방식 (분리 연결법)

각각의 bucket을 연결리스트 자료구조로 구현한다. 키와 값을 해당 해시의 index에 저장할 때 연결리스트의 노드로 저장하고 다른 키가 같은 해시로 들어왔을 때 연결리스트처럼 기존에 있던 노드에 연결시키는 것이다.

 

장점

1. 한정된 저장소를 효율적으로 사용할 수 있다.

2. 해시 함수의 중요성이 상대적으로 적어짐 (해시함수가 성능이 떨어져서 같은 해시가 자주 나와도 처리가능)

3. 상대적으로 적은 메모리 사용 (배열이 작아도 가능)

 

단점

1. 특정 하나의 해시로 자료들이 쏠려서 저장되면 탐색의 효율이 낮아진다!!!!!!

-> 이 특징때문에 최악의 경우(하나의 hash에 전부 연결될 경우) 연결리스트를 탐색하는 경우를 생각하면 시간복잡도는 O(N)까지 가질 수 있다.

->  자료의 추가와 삭제의 경우도 시간복잡도는 연결리스트와 비슷하게 볼 수 있다.

 

2. 외부 저장 공간이 추가로 필요하다 (연결리스트)

 

- Open Addressing (개방 주소법)

개방주소법은 비어있는 해시를 찾아서 데이터를 저장하는 방법이다.

 

이때 비어있는 해시를 찾는 규칙에는 3가지 방법이 있다.

- 선형 탐색(Linear probing) : 다음 해시 또는 n개를 건너뒤어 비어있는 해시에 데이터를 저장

- 제곱 탐색(Quadratic probing) : 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장

- 이중 해시(Double hashing) : 다른 해시 함수를 한번 더 적용하여 그 해시에 데이터를 저장

(최악의 경우에는 비어있는 해시를 찾지 못하고 다시 탐색을 시작한 위치로 돌아올 수도 있음.....)

 

장점

1. 별도의 저장공간이 없이 처리 가능

 

단점

1. 해시 함수의 성능이 매우 중요!!!

2. 저장할 데이터가 늘어나면 저장소의 크기가 더 필요하다.

 

이때 자료의 추가,삭제,탐색의 시간복잡도는 해시함수를 통해 얻은 해시가 비어있지 않으면 해시가 비어있는 곳을 찾아가야하므로 best case는 O(1), 최악의 경우에는 O(N)까지 나올 수 있다.

 

따라서 저장소가 어느정도 채워졌을 경우에는 저장소의 크기를 늘려주는 것이 좋다. (75% 이상일때???)

(해시 테이블의 효율은 25%~ 75% 정도 해시가 차있을 때 좋다)