CS Study 6주차 : Hashing / 해시 테이블(Hash Table)

Hashing

주어진 키 값을 이용하여 목표 레코드 주소를 직접적으로 계산하는 방법

• 키 값에 연산(해시 함수)을 적용하여 도출된 결과 값이 찾고자 하는 레코드가 있는 위치 주소가 된다.
• 해시 함수 : 어떤 k에 대한 테이블 주소를 계산하기 위한 방법으로, 주어진 키 값으로부터 레코드가 저장되어 있는
  주소를 산출해 낼 수 있는 수식

 

구성 요소

단점

오버플로우가 일어나면 별개의 버킷을 할당하여 처리할 수밖에 없다.
-> 결국 또 한번의 디스크 입출력을 필요하게 만들기 때문에 해싱 기법에서는 이 충돌로 인한 오버플로우를 어떻게 처리하느냐가 중요하다.

• 단순히 버킷 크기를 크게 한다면 오버플로는 감소하지만, 저장 공간 효율 또한 감소하고, 버킷 내 레코드 탐색 시간이 증가한다.

어떤 키값이 들어오더라도 균일하게 버킷에 레코드를 저장할 방법이 필요한데 현실적으로 불가능하다.

 

확장성 해싱(extendible hashing)

• 충돌에 대처하기 위해 제안된 기법이다.
• 오버플로우가 일어난 버킷 안의 엔트리들만 재조정하고, 동적으로 해시 테이블의 크기를 변화시키면서
  전체적인 성능을 높일 수 있다.
• 입력되는 레코드의 수에 따라 버킷의 수가 변한다.

장점

• 파일의 크기가 크더라도 레코드를 접근하기 위해 디스크 접근이 두 번을 넘기지 않는다.
• 버킷 주소 테이블의 크기가 작기 때문에 저장 공간이 절약된다.

단점

• 버킷 주소 테이블을 생성해야 하는 부담이 있다.
• 버킷을 버킷 주소를 통해 간접적으로 검색하므로 추가적인 검색이 필요하다.
• 데이터의 숫자가 적으면 오히려 디스크의 낭비일 수 있다.

 

해시 테이블(Hash Table)

• 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.
• 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.
• 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

위 사진을 예시로 하면 (Key, Value)가 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 하면

먼저 연산을 통해서 index 값을 계산하고 배열에 array[index] = "521-1234" 이런식으로 저장을 하게 된다.
이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 한번만 수행하면 되므로 매우 빠르게
데이터를 저장/삭제/조회할 수 있다.

 

 

 

---

참고 블로그

해싱
해시 테이블