Hash Table, Hashing

Hash Table은 key로부터 매핑된(key-value 형식) 자료구조로 Hahsing이라는 기술을 사용합니다.

 

Hash, Hashing

해시는 O(1)을 지향합니다. 데이터 개수 N과 무관하게 단번에 값을 찾아내겠다는 것입니다.

주어진 키를 사용해서 실제 레코드의 주소를 직접적으로 계산해내는 것을 해시라고 합니다.

해시 함수에 주어진 레코드의 키에 해시 함수를 가하면 그 레코드가 저장되어야 할 인덱스가 나옵니다. 당연히 이 계산은 매우 빨라야 합니다. 키에 해시 함수를 가하여 채운 도표가 해시 테이블입니다.

 

Hash function

주어진 데이터를 실제 정수 값으로 변환하는 함수입니다. 여기서 나오는 정수값은 테이블의 인덱스로 사용할 수 있는 정수(해시 코드)입니다. key-value 값으로 연결될 때, key 값은 hash function을 통해서 테이블의 index(해시 코드)를 받습니다. 그리고 index에 접근하여 value 값을 알 수 있습니다.

 

좋은 해시 함수는 2가지 기본 속성을 충족해야 합니다.

• 계산 속도가 매우 빨라야 합니다.
• 출력값의 중복(충돌)을 최소화해야 합니다.

Hash collision

서로 다른 데이터가 동일한 해시 값을 공유하는 경우입니다.

해시 알고리즘은 충돌 방지를 목적으로 만들어졌지만 때때로 서로 다른 데이터를 동일한 해시에 매핑할 수 있습니다. 데이터 관리 및 컴퓨터 보안에서 해시 충돌은 부정적으로 적용될 수 있기 때문에 충돌 회피는 중요한 주제입니다.

 

충돌을 해결하기 위한 일반적인 전략으로는 2가지가 있습니다.

• 개방형 주소 지정
• 별도의 연결

개방형 주소지정은 점유된 상태, 비어있는 상태, 삭데된 상태 중 하나의 상태에 할당합니다. 해시 충돌이 발생하면 비어 있는 것으로 표시된 대체 셀로 레코드가 이동됩니다. 이러한 제공되는 유형은 아래와 같습니다.

• linear probing
  : 테이블에서 순차적으로 다음 위치를 탐색, 클러스터링이라는 문제점이 발생 확률이 높습니다.
• double hashing
  : 제곱 함수를 사용하여 점점 더 멀리 떨어진 슬롯을 계산
• quadratic probing
  : 별도의 해시 함수를 사용하여 새로운 위치를 계산

별도의 연결은 둘 이상의 레코드를 해시 테이블의 셀에 연결할 수 있습니다. 해시 충돌을 방지하지만 너무 많은 목록을 추적하는 것이 어렵고 사용중인 도구가 무엇이든 매우 느려질 수 있습니다.