[algorithm] 해시테이블 자료구조 란?

 

 

해시테이블이란?

키와 값을 받아 키를 해싱 하고, index에 값을 저장하는 선형 자료 구조.

시간복잡도 면에서 삽입(add)은 O(1) 상수시간이 소요되며,  키를 알고 있다면 삭제, 탐색도 O(1)이 소요된다. 

• 해쉬테이블이 빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장합니다.
• 값이 저장되는 방법은 key,value 값을 해쉬 함수 연산을 통해 index값으로 계산하고 buckets에 해당인덱스에 저장한다.

해시는 언제 사용하면 좋을까 ?

예. 학생정보, 회원정보, 환자정보 등등 key value 쌍을 이루는 값들을 다뤄야할때

• 연결리스트를 사용한다면 학생정보를 탐색할때 O(n)시간복잡도가 걸린다.
• 배열을 사용한다면 인덱스를 모를 경우 탐색에 O(n)이 걸린다.
• 해시테이블을 사용하면 키값으로 추가,탐색,삭제가 O(1) 으로 가장 빠르다.

 

 

해시 함수란?

고유 인덱스 값을 설정하는 것이다. 특별히 구현방법이 정해진 것은 아니고 원하는 대로 구현해도 된다.

해시테이블에 사용되는 대표적인 해시 함수로는 3가지가 있다. 

1. Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
2. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3. Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
4. Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

 

해시 값이 충돌하는 경우는?

"john smith"를 해시함수 돌려 나온 값과 " sandra dee" 해시함수를 돌려 나온 값이 동일 하면 충돌이 발생한다.

 

충돌을 해결하기 위한 방법은?

[ 개방주소법(Open addressing) ]

추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시테이블의 공간을 활용하는 방법.

1. 선형탐사법

충돌이 발생하면 옆으로 (->) 한칸 이동한다. 이동한 곳에서 또 충돌이 발생하면 동일하게 한칸 이동한다. 이렇게 충돌이 해소될 때까지 이동한다. 이렇게 바로 인접한 인덱스에 데이터를 삽입하기 때문에 데이터가 밀집되는 클러스터링(Clustering)문제가 발생하고 이로인해 탐색과 삭제가 느려지게 된다. 

2. 제곱탐사법

충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.   역시나 클러스터링(Clustering) 문제가 발생할 수 있다. 

3. 이중해싱

선형탐사와 제곱탐사에서 발생하는 클러스터링 문제를 모두 피하기 위해 도입된 것이다.

충돌이 발생하면 기존 해시함수가 아닌 새로운 해시 함수로 기존과 다른 인덱스 값을 만들어 낸다.

[분리연결법]

누르면 출처

다른 방식과 다르게 다른 곳으로 이동하지 않고 버킷의 값을 연결리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다. 최악의 경우 하나의 버킷이 무한정 늘어날 수 있다는 단점이 있다. (152에 "John Smith"와 "Sandra Dee"가 연결리스트로 저장됨)

 

 

 

 

참고:  https://mangkyu.tistory.com/102   , https://school.programmers.co.kr/learn/courses/13213/lessons/91080, https://baeharam.netlify.app/posts/data%20structure/hash-table

 

잘못된 정보에 대한 피드백은 언제나 환영입니다  (´▽`ʃƪ)♡