[자료구조] Hash

Hash

Hash란?

해시 (Hash)란, 임의의 길이를 가진 어떤 값을 입력받았을 때 고정된 길이의 값으로 반환값을 출력하는 함수이다.
해시 함수는 키를 사용하지 않기 때문에 같은 입력 값에는 항상 같은 출력값을 가진다.
따라서 해시 함수를 사용할 때에는 오류나 변조를 탐지하기 위한 무결성 제공에 사용된다.

Hash Table

• 연관배열 구조를 활용하여 key에 결과값을 저장하는 자료구조
• Key, 해시함수, 해시, 값, 저장소로 이루어져 있다.
  - Key : 임의의 고유 값, 해시 함수의 Input값
  • 해시 함수 : Key를 일정한 길이를 가지는 출력값(해시값)으로 바꾸어주는 역할을 하는 함수 (그러나, 서로 다른 임의의 값(Key)가 같은 Hash값을 가지는 해시 충돌을 주의해야함)
  • 해시 : 해시 함수의 결과물, 저장소의 값과 매칭
  • 값 : 저장소에 최종적으로 저장되는 값

Hash의 특징

1. 임의의 입력값의 길이에 상관없이 항상 고정된 길이의 해시값을 출력한다.
2. 입력 값의 아주 일부만 변경되어도, 완전히 다른 해시값을 출력한다.
3. 출력값을 통하여 임의의 입력값을 예측할 수 없다.

해시 충돌 (Hash Collision), 장단점

해시 충돌이란, 임의의 무한한 값(해시 테이블에서의 key)을 해시값(해시 테이블에서의 HAsh, 유한값)으로 표현하기 때문에 서로 다른 임의의 값이 동일한 출력값을 갖게 됨을 의미한다.

1. Seperate Chaining

• Chaining : 자료 저장 시에 저장소(bucket)에서 충돌이 일어날 경우에 해당 값을 기존의 값과 연결 시키는 기법
• 연결 리스트 자료구조를 이용하여 다음에 저장된 자료를 기존에 저장된 자료 당므에 위치 시킨다.

장점
1. 한정된 저장소(bucket)을 효율적으로 사용 가능하다.
2. 상대적으로 적은 메모리를 사용한다.

단점
1. 한 Hash에 연속하여 여러 자료들이 연결된다면, 검색 효율이 낮아진다.
2. 외부 저장 공간을 사용한다.(외부 저장 공간 작업이 추가로 필요)

2. Open Addressing

• 비어있는 해시를 찾아 데이터를 저장하는 기법
• 따라서 해시 테이블은 1개의 해시와 1개의 값이 연결되어 있는 형태를 유지한다.

장점
1. 외부 저장 공간을 사용하지 않고, 해시 테이블 내에서 해결이 가능하다.

단점
1. 해시 함수의 성능에 따라, 해시 테이블의 성능이 결정된다.
2. 데이터의 길이가 늘어나면, 다른 저장소를 추가해야하는 문제가 발생한다.

참고
1. Hash, Hashing, Hash Table
2. 해시함수에 대한 개념 정리하기