[자료구조] 해시테이블

자료구조에서는 데이터의 접근에서 두 가지의 접근 방법이 있습니다.

순차 접근	직접 접근
연결 리스트	배열
한쪽 끝에서 목표 혹은 다른 끝에 도달할 때 까지 탐색	인덱스를 이용한 탐색(인덱스를 알아야함)
선형 시간	상수시간

순차 접근은 탐색 시간이 오래 걸리는데 비해 데이터의 삽입, 삭제로 인한 불필요한 이동이 없는 반면에 

직접 접근은 탐색 시간이 빠르지만 데이터의 이동에 불편한 점이 있습니다. 

각각의 단점을 보완하기 위한 것이 해시 테이블 (hash table) 입니다. 

※해시 : 원소들이 무 순서로 섞여 있다

- 해시 테이블

 - 원소의 인덱스에 대한 지식 없이 직접 접근 가능

 - 인덱스를 계산하는 해시 함수 사용

- 레코드와 테이블

레코드 : 여러 개의 컴포넌트를 가진 복합적인 자료구조

테이블 : 동일 타입의 레코드 집합 (ex key를 가진 테이블 -> MAP, 해시테이블 -> 해시 함수를 가진 키 테이블)

해시 테이블에서 해시 함수로 계산된 키 x와 임의의 인덱스 y를 가진 데이터가 다른 임의의 데이터 키 w, 인덱스 y를 가졌을 때 인덱스가 겹치는 경우가 있는데 이를 충돌이라고 표현한다. 

- 충돌을 피하는 방법

1. 선형 조사

 : 충돌된 인덱스의 다음 인덱스부터 순차적으로 조사하는 방법 

   해당 원소가 해시 함수로 인해 나온 인덱스 말고 다른 장소에 저장될 수 있기 때문에 개방 주소법 이라고도 한다

   그러나 기본 집중 발생, 해시 함수가 균일한 인덱스를 계산하는데에 실패하면 충돌이 계속 일어난다. 

2. 재해싱

 : 테이블의 오버플로우 문제를 해결하는 방법 (포화 되기 전에 재해싱을 한다면 충돌 횟수가 감소)

   테이블을 더 큰 사이즈로 재구축한다. 

 

3. 제곱 조사

 : 선형 조사와 비슷하지만 인덱스를 제곱만큼 더해서 찾는다 

   그러나 서로 다른 키 값을 가진 데이터들이 동일한 조사 순서를 가지게 되는 2차 집중 문제가 있다

4. 폐쇄 주소법

 : 하나의 인덱스에 1개 이상의 레코드를 사용하는 방법, 주로 연결 리스트를 사용한다.