해시 테이블, 해시 함수

해시 테이블

• 데이터를 Key, Value 조합으로 관리하는 비선형적 자료구조.
• 해시 함수를 사용하여 각 Key를 해시 값으로 변환하고, 해시 값을 인덱스로 사용하여 해시 테이블에 저장한다.
• 데이터가 저장되는 공간을 버킷(bucket)이라고 한다.
• 삽입/삭제/탐색 모두 상수 시간(O(1))으로 처리가 가능하다.
• 단, 서로 다른 Key가 같은 해시 값을 도출해내는 해시 충돌이 일어날 경우 탐색 시간이 증가할 수 있다.

 

해시 테이블의 구조

---

해시 함수

• 임의의 길이를 가진 데이터를 고정된 길이의 해시 값으로 변환(매핑)해주는 함수.
• 동일한 입력에 대해 항상 동일한 해시 값을 반환해야 한다.
• 대부분 해시 함수는 출력 범위가 입력 범위 보다 작으므로 다른 입력에 대해 동일한 해시 값을 반환하는 해시 충돌이 발생할 수 있다(비둘기집 원리).
• 해시 충돌은 해시 테이블의 성능에 직접적인 영향을 미치므로 최대한 줄여야 한다.
• 해시 함수는 기본적으로 역함수가 존재하지 않는다.
• 대표적인 비암호학적 해시 함수는 다음과 같다.

1. Division Method: 입력 키를 해시 테이블의 크기로 나눈 나머지를 해시 값으로 사용. 2. Multiplication Method: 입력 키를 0과 1 사이의 상수로 곱한 후 소수 부분을 추출하여 해시 값으로 사용. 3. Digit Folding Method: 입력 키를 여러 부분으로 나누어 합산한 값을 해시 값으로 사용(123 → 1 + 2 + 3).

---

체이닝

• 해시 충돌을 처리하는 방법.
• 버킷을 연결 리스트 형태로 만들어서 동일한 해시 값의 데이터들을 저장한다.
• 해시 충돌이 발생하여도 연결 리스트를 동적으로 조절할 수 있어 유연성이 높다.
• 연결 리스트의 길이가 길어질수록 탐색 속도도 증가하게 된다.

Chaining 기법

---

오픈 어드레싱

• 해시 충돌을 처리하는 방법
• 충돌이 발생하면 다른 비어있는 버킷을 찾아 데이터를 저장한다.
• 데이터를 삭제할때 추후 탐색을 위해서 삭제된 버킷이라는 표시를 따로 해주어야 한다.

1. 선형 탐사: 충돌이 발생하면 다음 위치를 선형적으로 탐색한다. 데이터가 밀집되는 클러스터링 문제가 발생할 수 있다. 2. 제곱 탐사: 충돌이 발생한 위치로부터 1^2, 2^2, 3^2... 등의 제곱수를 더하여 빈 공간을 탐색한다. 클러스터링 문제를 완화할 수 있지만 여전히 존재한다. 3. 이중 해싱: 탐사의 폭을 결정하는데 다른 해시 함수를 사용하는 방법이다. 버킷들 간의 균등한 분포를 유지하여 클러스터링 문제를 최대한 줄일 수 있다.

Open Addressing 기법