[알고리즘] 해시 테이블 (Hash Table)

해시(Hash)

해시는 데이터를 해시 함수(Hash Function)를 통해 고정된 크기의 값으로 변환하는 과정입니다.

• 해시 값은 실제로는 2진수 값이지만, 개발자가 읽기 편하도록 일반적으로 16진수로 표현해서 보여준다.
• 해시 함수(Hash Function) : 입력 데이터를 처리하여 고정된 길이의 해시 값을 생성하는 알고리즘
• 해시 값(Hash Value) : 해시 함수에 의해 생성된 고정 길이의 숫자나 문자열. (Hash Code, Digest)
• 데이터를 저장하거나 검색할 때 고유한 식별자로 사용할 수 있다.
• 비가역성 : 해시값으로 원래 데이터를 복원할 수 없다.
• Hash Table, Hash Map, Hash Set과 같은 자료구조가 있다.
• DB에 저장할 비밀번호를 해시화 하여 사용(암호화), 데이터 무결성 검사 등에 사용된다.

 

해시 테이블(Hash Table)

해시 테이블은 키-값(Key-Value)의 한쌍을 저장하는 데이터 구조입니다.

해시 함수를 사용하여 Key를 해시 값으로 변환하고, 이 값을 기반으로 데이터를 저장하거나, 검색합니다.

https://en.wikipedia.org/wiki/Hash_table

• 평균적으로 데이터 검색, 삽입, 삭제의 시간복잡도는 O(1)이다.
  • 최악의 경우 O(n)이 될 수 있으며, 해시 함수와 충돌 해결 기법으로 최소화 할 수 있다.
  • 충돌이 일어나지 않는다면, Map보다 Hash Map(C++ : Unordered Map)이 더 빠르다.
• 버킷 (Bucket) : 동일한 해시 값으로 매핑된 데이터(Value)를 저장하는 공간
• 충돌 (Collision) : 서로 다른 키가 같은 해시 값을 생성하는 경우.
  • 체이닝, 개방 주소법을 사용하여 해결할 수 있다.
• 데이터를 배열의 특정 인덱스에 매핑하므로 대량의 데이터를 관리하는데 효율적이다.
• 여유 공간을 추가로 할당하므로 메모리를 많이 사용하게 된다.

 

충돌 해결 방법

• 체이닝 (Chaining)
  • 동일한 해시 값에 대해 LinkedList 또는 다른 자료구조를 사용해 데이터를 저장
  • 단순하게 구현할 수 있지만, 충돌이 많을 시 검색 성능 저하
• 개방 주소법 (Open Addressing)
  • 충돌 발생 시 다른 빈 버킷을 탐색해 데이터를 저장
  • 선형 프로빙 (Linear Probing) : 순차적으로 다음 빈 공간을 탐색
  • 이차 프로빙 (Quadratic Probing) : 탐색 범위를 제곱 값으로 증가시킴
  • 이중 해싱 (Double Hashing) : 다른 해시 함수를 사용해 탐색

 

선형 프로빙

• 같은 해시 h(k) 값이 나오면 빈 슬룻이 나올 때까지 해쉬테이블을 탐색한다.  "  h(k,i) = ( h'(k) + i ) mod m "
• 삽입 : h(k)값에 빈 슬룻이 나오면 Key를 삽입
• 탐색 : h(k)값의 위치에서 값을 찾을 때까지 하나씩 이동하면서 탐색
• 삭제 : 실제로 값을 지우는 경우 DELETED 표기
• 구현은 쉽지만, 값이 들어있는 slot의 수가 많으면 평균 검색 시간이 증가하며, 슬룻이 끝부분에 뭉치는 Primary Clustering 문제가 발생할 수 있다.

 

이차 프로빙

• h( k ) = h( k ) + i² 
• 충돌이 일어났을 때 탐색 범위를 제곱값으로 증가시켜 탐색한다.
• Primary Clustering 문제를 줄일 수 있지만, Secondary Clustering 문제가 발생할 수있다.
• Secondary Clustering : 처음 시작 값이 같으면 이전 key값과 동일한 위치만큼 이동하기 때문에 반복적으로 충돌이 일어나는 경우

 

이중 해싱

• h₁(k) = k mod 13
  h₂(k) = i + ( k mod 13 )
  h(k,i) = (h₁(k) + i * h₂(k)) mod 13
• 해시 함수를 두번 적용하여 저장위치를 찾는다.