해쉬 테이블은 무엇인가요? 해쉬값이 충돌하면 어떻게 해결할수 있을까요?

• 해쉬 테이블은 해쉬 알고리즘을 사용하여 키와 데이터를 저장하는 자료구조를 일컫습니다. 이 자료구조는 데이터 탐색, 삽입, 삭제, 수정에 평균 O(1)의 시간 복잡도가 소요됩니다.
  • 이런한 자료구조는 자바에서는 hashTable과 hashMap이 있습니다.
    • 구체적으로 설명 드리겠습니다. 해쉬란 가변길이 문자열을 고정된 길이의 문자열로 변환 하는 것입니다. 그러한 변환 알고리즘 은 여러가지 있는데 대표적으로는 SHA256, SHA512 등이 있고, 각각의 숫자는 변환된 문자열의 고정된 길이를 의미 합니다.
    • 이렇게 해쉬값(digest)을 배열의 인덱스로 하고, 배열의 해당인덱스에 실제 키 및 데이터를 저장하는 것입니다. 나중에 데이터를 찾을 때는 탐색하는 데이터를 해쉬 알고리즘으로 해쉬값변홚후, 그 해쉬값을 인덱스로 했을때 빈값이 아니면 그 값을 반환하면 되겠죠?
  • 물론 이러한 자료구조에도 문제가 있습니다. 그 문제는 바로 해쉬값이 충돌할수도 있다는 것이죠. 특히 변환하는 문자열의 길이가 다양할 때는 다양한 데이터의 변환결과가 특정한 해쉬값을 공유할수 있습니다. 이러한 충돌이 많을 수록, 데이터의 탐색 및 삽입 시간을 떨어 뜨릴수 있고, 최악의 경우 O(n)이 될수도 있습니다.
  • 그래서 이 충돌을 예방하는 방법으로는 해쉬 알고리즘을 충돌이 최소화되게끔 설계하는 것이고
  • 충돌을 해결하는 방법은 분리연결법과 개방 주소법이 있습니다.
    • 분리 연결법은 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음데이터의 주소를 저장합니다.
      • 연결된 데이터는 링크드리스트의 모양을 가집니다.
    • 개방 주소법은 비어있는 해시 테이블의 공간을 활용하는 방법입니다.
      • 구체적으로 3가지 방식이 존재합니다.
      • Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
      • Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
      • Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

참고자료

https://mangkyu.tistory.com/102