Hashing

Hashing(해싱)

Hashing(해싱)은 Key(키)값에서 레코드가 저장되어 있는 주소를 직접 계산한 후에 산출된 주소로 바로 접근이 가능하게 하는 방법이다. 또는 Key(키)값을 해시 함수라는 수식에 대입시켜 계산한 후 나온 결과를 주소로 사용해서 바로 Value(값)에 접근하게 할 수있는 방법이라고도 할 수 있다.

Hash Function(해시 함수)

주어진 Key(키) 값으로부터 레코드가 저장되어 있는 주소를 산출해 낼 수 있는 수식이다.

Hashing(해싱)이 사용되는 분야

1. 보안 분야 : 데이터의 위변조를 막기 위해 전자서명이나 보안 알고리즘에 사용한다.
2. 자료구조 분야 : 기억 공간에 저장된 정보를 보다 빠르게 검색하기 위해 절대주소나 상대주소가 아닌 해시 테이블을 생성하는 방식이다.

Hashing(해싱) 구현 기법

정적 해싱

• 고정된 크기의 배열을 이용한다.
• 현재 파일의 크기를 고려하여 해시 함수를 결정한다.
• 파일의 크기가 커짐에 따라 주기적으로 해싱 구조를 재구성해야 한다.
• 구현이 쉽고 간단하다.
• 버킷의 크기를 작게 잡을 경우 충돌의 우려가 있고, 크게 잡을 경우 메모리 또는 디스크 낭비의 우려가 있다.
• 데이터가 증가함에 따라 검색성능이 떨어진다.

동적 해싱

• 데이터 증감에 따라 배열의 크기를 동적으로 변화시키는 방법이다.
• 버킷을 포인터로 가리키는 버킷 주소(인덱스) 테이블을 생성,유지 시켜야한다.
• 로직이 복잡하다.
• 데이터가 증가해도 검색 성능이 유지된다.
• 메모리 또는 디스크의 낭비를 줄일 수 있다.
• 접근시간을 일정하게 유지할 수 있다.
• 버킷을 직접 검색하는게 아니라 버킷 주소(인덱스)를 통해 간접적으로 검색하는 것이기 때문에 추가적인 검색이 필요하다.
• 특정 Key(키)를 검색하고자 할 경우, 해시된 Key(키, 이진 비트열)를 기준으로 디렉터리를 검색하여 주소(인덱스)를 얻는다.

확장 해싱

• 동적 해싱 기법에서 가장 많이 사용하는 방법으로 트리의 깊이가 2인 특별한 경우이다.

• 사용할 수 있는 비트열을 모두 사용하지 않고 일부 비트열만을 사용하고 더 많은 버킷이 필요한 경우 비트열을 하나씩 추가한다.

• 해싱 구조의 재구성이 한 번에 하나의 버킷에서만 발생하므로 상대적으로 부하가 덜 하다.

• 부가적인 접근 구조를 저장하며, 해시 함수 적용 결과인 이진수 표현을 기반으로 한다.

• 대부분의 Key(키)의 검색은 2개의 블록 접근을 필요로 한다.

• 장점 :

  1. 파일의 크기가 크더라도 레코드를 접근하기 위해 디스크 접근이 두 번이 넘지 않는다.
  2. 버킷 주소(인덱스) 테이블의 크기가 작으므로 저장공간이 절약된다.

• 단점 :

  1. 데이터의 숫자가 적으면 디스크의 낭비가 발생할 수 있다.
  2. 추가적인 검색이 필요하다.

해싱의 장단점 요약

장점

• 상당히 빠른 검색속도를 지녔다.
• 데이터에 대한 입력이나 삭제가 용이하다.
• 검색시간이 데이터의 양과 무관하게 일정하게 유지된다.

단점

• 연속적인 데이터 검색에는 비효율적이다.
• 디스크 공간이 비효율적으로 사용된다.
• 디스크 공간을 늘리고 재구조화하게 되면 재 검색을 위한 상당시간이 소요된다.

참고한 사이트 :
https://dev-kani.tistory.com/2
http://www.jidum.com/jidums/view.do?jidumId=163
https://mattlee.tistory.com/62