[자료구조] Hash

Aug 18, 2023

Contents

해시테이블 해시함수

💡

데이터를 입력받아 완전히 다른 모습의 데이터로 바꾸는 것

해시테이블

해시 테이블은 데이터의 해시값을 테이블 내 주소로 이용하는 탐색 알고리즘, 이진 탐색보다 훨씬 빠름

암호화

해싱은 원본 데이터를 다른 모습으로 바꿔놓는다. 해싱은 같은 데이터에 대해 같은 결과를 출력하지만, 다른 데이터에 대해서는 다른 결과를 출력한다.

해시는 데이터의 지문 역할을 할 수 있다. 이런 특징으로 디지털 서명이나 블록체인에 많이 사용됨 ( MD5, SHA )

데이터 축약

해시는 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있다. 이런 특성을 이용하여 커다란 데이터를 해시하면 짧은 길이로 축약할 수 있음 ( 커다란 원본 데이터끼리 비교하는것에 비해 효율이 매우 높아진다 )

해시테이블

데이터를 담을 테이블을 미리 크게 확보해놓은 후 입력 받은 데이터를 해싱하여 테이블 내 주소를 계산하고 이 주소를 데이터에 담는 것

해싱으로 주소값을 얻는 과정은 상수시간임

해시테이블은 데이터가 입력되지 않은 여유 공간이 많아야 성능을 발휘할 수 있다.

해시함수

충돌 Collision :서로 다른 입력값에 대해 동일한 해시값 ( 해시 테이블 내의 동일한 주소를 반환함 )

클러스터 Cluster: 해시 테이블 내 일부 지역의 주소들을 집중적으로 반환함으로써 데이터가 한곳에 모이는 문제

나눗셈법

해시 함수가 테이블 내 공간을 효율적으로 사용하기 위해서는 테이블의 크기 n을 소수로 정해야 함

2의 제곱수와 먼 소수를 이용하는 해시 함수가 좋은 성능을 발휘

자릿수 접기 → 충돌이나 클러스터링을 완벽히 해결해주는 해싱 알고리즘 X 하지만 문제를 일으킬 가능성을 줄인 알고리즘

종이를 접듯이 숫자를 접어 일정한 크기 이하의 수로 만드는 방법

숫자의 각 자릿수를 더해 해시값을 만드는 것, 문자열을 키로 사용하는 해시 테이블에 잘 어울리는 알고리즘

해시 테이블의 크기가 12289라면

문제는 문자열의 키의 최대 길이가 10자리면 10 * 127 = 1270이므로 1271~12288사이의 주소는 활용되지 않게 되는 문제가 생긴다

12710 = 1,091,533,853,073,393,531,649가지가 된다는 사실을 생각하면 매우 심각한 문제임

나머지 3개의 비트는 사용하지 않는 문제를 발견 → 3개의 비트를 모두 활용한다면 해시테이블의 안쓰는 부분을 사용할 수 있음

해시 함수의 한계 : 충돌

💡

해시 함수든 알고리즘이 아무리 정교하게 설계되었다고 해도 모든 입력값에 대해서 고유한 해시값을 만들지는 못한다.

해시 충돌을 해결하는 방법은 크게 2가지

해시 테이블의 주소 바깥에 새로운 공간을 할당 → 개방해싱 (Open Hashing )

주어진 해시 테이블의 공간 안에서 문제를 해결하는 방법 → 폐쇄해싱 (Closed Hashing )

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

해시함수가 서로 다른 키에 대해 같은 주소값을 반환해서 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 기법

충돌이 일어날 때 마다 데이터를 링크드 리스트에 사슬처럼 주렁주렁 엮는다는 의미

삽입 연산 : 앞으로 발생할 충돌을 고려

삭제 연산과 탐색 연산 : 이미 발생한 충돌을 고려

체이닝 성능 향상 방법

→ 원하는 데이터를 찾기 위해 순차 탐색을 해야 하는 링크드 리스트의 단점

→ 해시 함수의 성능이 좋지 않아 충돌이 잦다면 해시 테이블과 이진 탐색 트리의 결합

개방 주소법 Open Addressing

💡

충돌이 일어날 때 해시 함수에 의해 만들어진 주소가 아니더라도 얼마든지 다른 주소를 사용할 수 있도록 허용하는 충돌 해결 알고리즘

개방 주소법은 탐사가 전부

선형 탐사 Linear Probing : 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 있으면 현재 주소에서 고정 폭 만큼 주소를 이동

문제점 : 선형 탐사를 쓰다 보면 클러스터 현상이 많이 발생함 → 개선하기 위해서 제곱 탐사를 사용

제곱 탐사 Quadratic Probing : 고정 폭이 제곱수로 늘어나는 것

서로 다른 해시값을 가진 데이터에 대해 클러스터가 형성되지 않도록 하는 효과가 있지만, 같은 해시값을 가진 데이터는 2차 클러스터를 형성하는 문제를 갖는다

이중 해싱

💡

해시 함수에서 키를 입력하여 얻어낸 주소에서 충돌이 일어나면 새로운 주소를 향해 이동해야 하는데 이 때 이동폭을 제 2의 해시 함수로 계산하는 방법

재해싱 (Rehashing)

남은 공간이 거의 없는 해시 테이블에서 연쇄 충돌이 자주 일어남 → 이 문제를 해결할 수 있는 하나의 방법임

→ 재해싱은 해시 테이블의 크기를 늘리고 늘어난 해시 테이블의 크기에 맞춰 테이블 내의 모든 데이터를 다시 해싱한다.

🧐 통계적으로 해시테이블의 공간 사용률이 70~80%에 이르면 성능 저하가 나타난다. 공간 사용률이 이보다 적은 수준일 때 미리 재해싱해둬야 성능 저하를 막을 수 있음 또한 너무 빈번하게 일어나면 안되기에 75%로 설정하는 것이 일반적

Contents

[자료구조] 우선순위 큐 - Priority Queue

[자료구조] Heap