< 해쉬 테이블 > 

검색속도가 매우 빠르나, 메모리를 굉장히 소모한다.

 

 

1. 해쉬 : 자료를 입력할 때부터 검색하기 쉬운 위치에 삽입하는 방법

( 검색 방법이 아니라, 자료가 저장되는 전체 저장소이다. )

 

2. 해쉬 테이블 : 자료가 저장되는 전체 저장소 ( 구현에 따라 배열/동적배열/연결리스트 )

 

3. 해쉬 함수 : 데이터가 새로 입력될 때, 이 데이터를 어떤 위치(ex. index)에 넣을지 결정하는 연산을 해주는 함수

 

4. 해싱의 궁극적인 문제점 : 위치가 겹치는 충돌이 발생할 수 있다.

 

ex) 해쉬 테이블이 배열이라고 할 때, key 값이 정수 int형이고, 해쉬 함수 내부 처리가 key % 10 (나머지연산) 이라고 하면

배열의 크기가 10 일때, key 값 중 1, 11, 21, 31 은 모두 같은 위치 index == 1 을 가리키게 된다.

 

 

5. 해싱 문제점의 해결법

 

① 다중 슬롯 

배열의 크기를 충분히 크게 잡는다. 충돌이 발생하면 관련 배열의 다음 슬롯으로 데이터를 저장한다. ▶ 2차원 배열 사용

또한 해시 함수도 다중 슬롯을 지원하도록 수정해야한다.

▷슬롯 크기를 초과하는 데이터가 입력될 때만 문제가 발생한다.

 

② 정교한 해쉬 함수

해쉬 함수의 내부 처리를 더욱 정교하게 하는 방식이다.

ex) return num%10 → return ( num%10 ) % 10

 

③ 선형 탐색

충돌이 생긴 경우, 데이터를 버리지 않고 다른 index에 대신 넣는 방법 (단, 해쉬 함수가 검색하여 찾을 수 있는 위치로)

cf. 산술적 연산을 사용한다 

 

④ 재해시

선형 탐색과 비슷하나, 산술적 연산이 아니라, 대체 칸을 찾는 해쉬 함수를 별도로 더 구현하는 방식이다.

 

⑤ 동적 슬롯

슬롯의 갯수를 가변적으로 관리하는 방법.

cf. 선형탐색과 재해시가 충돌을 회피하는 해결방법이라면, 동적 슬롯은 충돌에 적극적 대처하는 방식이다.

동적으로 처리되어야하므로 가변 배열 vector 또는 list를 사용하여 구현한다.

 

 

 

출처

http://soen.kr/lecture/ccpp/cpp2/20-1-3.htm

http://jtoday.tistory.com/73

 

 

 

 

 

 

 

'DS & Algorithm > 자료구조' 카테고리의 다른 글

시간복잡도 BigO 표기법 정리  (0) 2022.11.12