< 해쉬 테이블 >
검색속도가 매우 빠르나, 메모리를 굉장히 소모한다.
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 |
---|