자료구조(해시테이블)

해시테이블

데이터 검색을 효율적으로 하기 위해 사용되는 구조이다.

내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색속도를 제공한다.

해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

 

뭔소린지 모르겠으니 예를 들어서 한번 보자

 

해시테이블은 키(key)와 값(value)이 한 쌍을 이루는 데이터를 저장한다고 하니

키값으로 이름, 값으로는 성별을 담아서 데이터를 넣어줘보자

먼저 배열의 크기가 5인 배열을 만들자

'철수:남자, 영희:여자, 맹구:남자, 짱구:남자, 유리:여자, 수지:여자'

이러한 데이터가 있다고 하자

 

철수 데이터를 추가해보자

해시를 이용해서 철수의 키에 해당하는 해시값을 계산하자

문자열 '철수'에 해당하는 해시값이 4637이라고 하자

이 해시값을 배열의 크기인 5로 나누어 나머지를 구하면 2이다 ( 4627 mod 5 = 2)

 

그러면 구한 수와 같은 배열의 2번 상자에 철수의 데이터를 저장하는 것이다.

 

그렇게 영희의 해시값은 5238, 맹구의 해시값은 7129 라면 아래처럼 채워질 것이다

(5238 mod 5 = 3, 7129 mod 5 = 4)

그런데 짱구의 해시값이 6277이면 6277 mod 5 = 2로

철수 데이터가 저장이 되어있습니다 이렇게 데이터 저장위치가 겹치는 것을 충돌이라고 한다.

 

충돌을 해결하는 방법에는 여러가지가 있는데 그 중 하나인 연쇄법(Separate Chaining)으로 해결을 해보자

연쇄법은 리스트 구조로 기존 데이터와 연결시키는 것이다

유리 해시값이 1112 이고 수지 해시값이 7859라면

 

이렇게 나타낼 수 있다

 

해시테이블에서 데이터를 검색해보자

짱구의 성별을 알고 싶을 때는 짱구의 해시값을 구해서 5로 mod 연산을 하면 2이기 때문에

2번 상자에 저장되어 있는 것을 알 수 있다.

하지만 2번 데이터의 선두에는 철수데이터가 있기 때문에 이때는 선형탐색을 실시해서 찾는다

 

이렇게 해시테이블에서 사용하는 배열의 크기가 작으면 충돌이 많아져 선형 탐색의 빈도가 높아지게 된다

하지만 그렇다고 크기가 너무 크면 데이터가 없는 상자가 많아지기 때문에 메모리가 낭비되므로

적절한 배열의 크기를 설정하는 것이 중요하다.

 

 

알고리즘 도감을 보면서 공부했다!