6-1 해시 테이블 개요

1. 해시 테이블의 개념

   - 데이터를 한 번에 찾아줄 수 있는 개념

① 저장과 검색의 복잡도

   - 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조

   - 저장된 자료와 비교하여 자리를 찾지 않고 단 한번의 계산으로 자신의 자리 찾음

   - 평균 O(1) 

 

② 해싱

  - 해시 함수를 이용하여 레코드가 저장되어 있는 주소를 직접 구하여 검색

  - 키를 비교하지 않고 계산에 의해 검색하는 방법

  - 매우 빠른 응답을 요하는 응용에 유용 ex) 주민등록 시스템

 

③ 해시 테이블 - 키값과 value 데이터 가진 구조

  - 최소 원소를 찾는 것과 같은 작업은 지원하지 않음.

  - 한 개 이상 보관하는 버킷들의 집합

  - 한 개의 버킷에는 하나 이상의 레코드 수용 가능

  - 키값을 해시 함수에 넣어서 계산하면 해시 테이블의 주소 값이 나오는데 계산된 값은 해시 값 또는 해시 주소라고 함.

 

  - 데이터를 "해시(잘게 부수고 다시 뭉침)"해서 테이블 내의 주소로 바꾸면 상수 시간 안에 탐색 가능.

2. 해시 함수

① 해시 함수의 성질

   - 입력 원소가 해시 테이블에 골고루 저장되어야 함.

   - 계산이 간단해야 함.

   - 해시 테이블에 원소가 차있는 비율(적재율)은 해시 테이블의 성능에 매우 중요한 영향을 미침

   - 해시 테이블에 골고루 데이터가 존재해야 서로 다른 두 원소가 한 주소를 놓고 충돌할 확률이 작아짐  

② 해시 함수

  - 하나의 문자열을 보다 빨리 찾을 수 있도록 주소에 직접 접근할 수 있는 짧은 길이의 값이나 키로 변환하는 알고리즘을 수식으로 표현한 것

  - 주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 내는 수식

 

3. 해시 테이블의 충돌

① 충돌 : 해시 테이블의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것

    - 한 원소를 해싱하여 저장하려하는데 다른 원소가 이미 그 자리를 차지한 상황

② 해결 방법

    - 체이닝, 대방주소 방법