해시 테이블을 통한 데이터의 적재

해시 테이블 소개

• 해시 테이블은 데이터를 적재하는 효율적인 방법을 제공한다.
• 기본 원리: 데이터의 '키(Key)'를 특정 '해시 함수(Hash Function)'를 통해 변환, 이를 바탕으로 데이터가 저장될 위치를 결정한다.
• 해시 함수의 결과값인 '해시 값(Hash Value)'은 데이터가 저장될 배열의 인덱스로 사용된다.
• 해시 테이블은 빠른 검색, 삽입, 삭제 연산을 지원한다.

해시 테이블의 충돌

• 두 개 이상의 키가 동일한 해시 값을 가지는 경우, '충돌(Collision)'이 발생한다.
• 충돌 해결 기법:
  • 체이닝(Chaining): 해시 테이블의 각 인덱스에 링크드 리스트를 사용하여 충돌 발생 시 리스트에 데이터를 추가함으로써 충돌 해결.
  • 오픈 어드레싱(Open Addressing): 충돌이 발생했을 때, 다른 인덱스를 찾아 데이터를 저장하는 방식. 대표적인 방법으로는 선형 조사(Linear Probing), 제곱 조사(Quadratic Probing), 이중 해싱(Double Hashing)이 있다.

선형 조사(Linear Probing)

• 충돌 발생 시, 다음 인덱스로 이동하여 빈 공간을 찾는 방식.

제곱 조사(Quadratic Probing)

• 충돌 발생 시, 제곱수만큼 건너뛰어 빈 공간을 찾는 방식. 이는 데이터의 군집화 현상을 줄여준다.

이중 해싱(Double Hashing)

• 두 개의 해시 함수를 사용하며, 첫 번째 해시 함수로 위치를 결정하고 충돌이 발생하면 두 번째 해시 함수로 건너뛸 위치를 결정한다.

해시 테이블의 응용

• 해시 테이블은 빠른 검색을 필요로 하는 다양한 애플리케이션에서 널리 사용된다.
• 예: 데이터베이스 인덱싱, 캐싱 시스템, 메모리 관리 등.