[자료구조] Hash

Aug 18, 2023
[자료구조] Hash
💡
데이터를 입력받아 완전히 다른 모습의 데이터로 바꾸는 것
  • 해시테이블
해시 테이블은 데이터의 해시값을 테이블 내 주소로 이용하는 탐색 알고리즘, 이진 탐색보다 훨씬 빠름
  • 암호화
해싱은 원본 데이터를 다른 모습으로 바꿔놓는다. 해싱은 같은 데이터에 대해 같은 결과를 출력하지만, 다른 데이터에 대해서는 다른 결과를 출력한다.
해시는 데이터의 지문 역할을 할 수 있다. 이런 특징으로 디지털 서명이나 블록체인에 많이 사용됨 ( MD5, SHA )
  • 데이터 축약
해시는 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있다. 이런 특성을 이용하여 커다란 데이터를 해시하면 짧은 길이로 축약할 수 있음 ( 커다란 원본 데이터끼리 비교하는것에 비해 효율이 매우 높아진다 )
 

해시테이블

notion image
  • 데이터를 담을 테이블을 미리 크게 확보해놓은 후 입력 받은 데이터를 해싱하여 테이블 내 주소를 계산하고 이 주소를 데이터에 담는 것
  • 해싱으로 주소값을 얻는 과정은 상수시간임
  • 해시테이블은 데이터가 입력되지 않은 여유 공간이 많아야 성능을 발휘할 수 있다.
 

해시함수

  • 충돌 Collision :서로 다른 입력값에 대해 동일한 해시값 ( 해시 테이블 내의 동일한 주소를 반환함 )
  • 클러스터 Cluster: 해시 테이블 내 일부 지역의 주소들을 집중적으로 반환함으로써 데이터가 한곳에 모이는 문제
나눗셈법
해시 함수가 테이블 내 공간을 효율적으로 사용하기 위해서는 테이블의 크기 n을 소수로 정해야 함
  • 2의 제곱수와 먼 소수를 이용하는 해시 함수가 좋은 성능을 발휘
자릿수 접기 → 충돌이나 클러스터링을 완벽히 해결해주는 해싱 알고리즘 X 하지만 문제를 일으킬 가능성을 줄인 알고리즘
종이를 접듯이 숫자를 접어 일정한 크기 이하의 수로 만드는 방법
숫자의 각 자릿수를 더해 해시값을 만드는 것, 문자열을 키로 사용하는 해시 테이블에 잘 어울리는 알고리즘
notion image
해시 테이블의 크기가 12289라면
문제는 문자열의 키의 최대 길이가 10자리면 10 * 127 = 1270이므로 1271~12288사이의 주소는 활용되지 않게 되는 문제가 생긴다
12710 = 1,091,533,853,073,393,531,649가지가 된다는 사실을 생각하면 매우 심각한 문제임
notion image
나머지 3개의 비트는 사용하지 않는 문제를 발견 → 3개의 비트를 모두 활용한다면 해시테이블의 안쓰는 부분을 사용할 수 있음

해시 함수의 한계 : 충돌

💡
해시 함수든 알고리즘이 아무리 정교하게 설계되었다고 해도 모든 입력값에 대해서 고유한 해시값을 만들지는 못한다.
해시 충돌을 해결하는 방법은 크게 2가지
  • 해시 테이블의 주소 바깥에 새로운 공간을 할당 → 개방해싱 (Open Hashing )
  • 주어진 해시 테이블의 공간 안에서 문제를 해결하는 방법 → 폐쇄해싱 (Closed Hashing )
 

개방해싱에 충돌 해결 기법이 체이닝

해시함수가 서로 다른 키에 대해 같은 주소값을 반환해서 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 기법
충돌이 일어날 때 마다 데이터를 링크드 리스트에 사슬처럼 주렁주렁 엮는다는 의미
notion image
  • 삽입 연산 : 앞으로 발생할 충돌을 고려
  • 삭제 연산과 탐색 연산 : 이미 발생한 충돌을 고려
체이닝 성능 향상 방법
→ 원하는 데이터를 찾기 위해 순차 탐색을 해야 하는 링크드 리스트의 단점
→ 해시 함수의 성능이 좋지 않아 충돌이 잦다면 해시 테이블과 이진 탐색 트리의 결합
 

개방 주소법 Open Addressing

💡
충돌이 일어날 때 해시 함수에 의해 만들어진 주소가 아니더라도 얼마든지 다른 주소를 사용할 수 있도록 허용하는 충돌 해결 알고리즘
개방 주소법은 탐사가 전부
  • 선형 탐사 Linear Probing : 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 있으면 현재 주소에서 고정 폭 만큼 주소를 이동
    • 문제점 : 선형 탐사를 쓰다 보면 클러스터 현상이 많이 발생함 → 개선하기 위해서 제곱 탐사를 사용
  • 제곱 탐사 Quadratic Probing : 고정 폭이 제곱수로 늘어나는 것
    • 서로 다른 해시값을 가진 데이터에 대해 클러스터가 형성되지 않도록 하는 효과가 있지만, 같은 해시값을 가진 데이터는 2차 클러스터를 형성하는 문제를 갖는다
       

이중 해싱

💡
해시 함수에서 키를 입력하여 얻어낸 주소에서 충돌이 일어나면 새로운 주소를 향해 이동해야 하는데 이 때 이동폭을 제 2의 해시 함수로 계산하는 방법
재해싱 (Rehashing)
남은 공간이 거의 없는 해시 테이블에서 연쇄 충돌이 자주 일어남 → 이 문제를 해결할 수 있는 하나의 방법임
→ 재해싱은 해시 테이블의 크기를 늘리고 늘어난 해시 테이블의 크기에 맞춰 테이블 내의 모든 데이터를 다시 해싱한다.
🧐 통계적으로 해시테이블의 공간 사용률이 70~80%에 이르면 성능 저하가 나타난다. 공간 사용률이 이보다 적은 수준일 때 미리 재해싱해둬야 성능 저하를 막을 수 있음 또한 너무 빈번하게 일어나면 안되기에 75%로 설정하는 것이 일반적
Share article
RSSPowered by inblog