Hash란? - Hashfunction, Hash Table, Hash Collision

Date: February 09, 2022

Hash

Hash란 데이터를 관리/유지하는 자료구조로써 리소스를 포기하고 속도를 높이는 방식이다. 문자열, 숫자 등을 특정 규칙에 맞춰 배열의 index값으로 변경하여 바로 그에 대응하는 데이터 값에 접근/반환 할 수 있는 자료구조이다. 이때 Key값에 대응하는 데이터에 O(1)의 속도로 접근/반환 할 수 있다(규칙을 잘못 짜게되면 O(n)이 될 수도 있다). 동일한 데이터에 대해서 똑같이 분류하는 규칙을 만들어 Table, Map 형식으로 만들어 사용하게 되는데, 이런 규칙을 의미하는 것이 Hash Function이고, 이런 일련의 작업들을 통틀어 Hashing이라고 한다.

데이터 관리/유지 자료구조
리소스를 사용하여 속도를 높임
동일한 데이터에 대해서만 똑같이 분류하는 규칙성을 만들어 분류
이런 규칙을 Hash Function
이런 작업을 진행하는 것을 hashing이라고 함

Hash Function

Key 값을 구분하는 일정한 규칙을 나타냄
검색하고자 하는 Key값을 입력하면 Hash Function에 의해 해시값을 얻어내고, 이 해시값을 배열의 길이로 나눈 나머지 값을 인덱스로 환산하여 접근
Key값의 데이터 Type과 상관없이 자연수를 반환하여 사용하게 됨
대부분 구현된 라이브러리르 사용하게 되지만, 최적화를 위해서는 상황에 맞게 Hash Function을 구성하여 사용할 수 있음
확률적으로 고르게 배분 될 수 있도록 만드는 것이 중요함

Hash Table

Hash Function을 통해 반환된 값으로 추출된 Index값과 그에 상응하는 Data를 표기해놓은 Table
하나의 배열로 생각할 수 있으며 배열에 Value값을 저장한 형태
Table의 요소 : 배열의 Index, Index에 매칭되는 배열의 공간을 버켓(혹은 슬롯), 버켓 안에 들어있는 데이터 값을 엔트리

Hash Collision

Hash Function은 다른 키 값으로 동일한 Hash Code를 만들기도함
Hash Code가 다르더라도 동일한 Index값을 만들 수도 있음
Key로 들어갈 수 있는 값은 무한개가 있고, 넣을 배열은 유한하기 때문에 이런 충돌은 빈번하게 일어날 수 있음
이런 충돌을 최소화 하는 것이 중요함
충돌에도 Hash Table을 동작하게 만들기 위해서 여러가지 해결방법이 제시됨

해결방법

Chaining
Open Addressing
Resizing

충돌해결 1) Chaining

체이닝 방식은 해시충돌일 발생했을때, 그 버켓안에 지속적으로 데이터를 채워 넣는 방법이다. 동일 Index에 데이터를 하나씩 추가하다 보니, 접근할 때, 해당 Index에 내에 쌓여있는 데이터 수 만큼의 탐색 횟수가 필요된다. 하지만 Hash Table의 전체적인 크기는 변동 없이 쉽게 구현할 수 있게 되고, 접근, 삭제, 추가 작업에 편리하게 진행 될 수 있다. 체이닝 방식은 Key값이 Hash Table의 전체 크기보다 더 많을 경우에 자주 사용된다.

Index가 겹치게 될 경우 체인으로 연결하는 방식
버켓에 데이터를 삽입하다 해시 충돌이 발생하면, 버켓 내에 Linked List(포인터로 연결)를 할당하여 데이터들을 연결하는 방식
지속적으로 충돌이 발생하면 선형적으로 성능저하가 일어남
최악의 경우 O(n)이 될 수도 있음
검색 : Index를 타고 들어가 Linked List에서 필요한 값을 찾아냄(O(k))
삽입 : Linked List에 추가로 연결(O(1))
삭제 : Linked List에서 제거하고 중간을 연결해줌 (O(k))
하지만 데이터가 n개, table 길이 m일 경우 linked list 내 갯수가 n/m(=k)로 이상적으로 들어가게 되어 k값이 2~3 정도만 되어도 O(1)로 볼수 있음

충돌해결 2) Open Addressing

Open Addressing 방법은 체이닝과 다르게 하나의 버켓에 하나의 엔트리인 해시 테이블이다. 해시충돌이 일어났을때 해시함수로 얻은 주소값이 아닌 다른 주소에 데이터를 저장할 수 있도록 허가되어 있어, Open Addressing이라는 이름이 붙여지게 되었다. 해시충돌이 일어났을때, 특정 조건 만큼 건너뛰어 빈 버켓에 그 데이터 값을 넣게 된다.

Index가 겹치게 될 경우 다른 비어있는 버켓에 넣어주는 방식(해시함수의 결과값과 다른 인덱스에 저장)
해시충돌이 일어난 인덱스에서 일정한 규칙을 가지고 건너뛰어 빈 버켓을 찾아 엔트리를 넣어줌
일반적으로 Hash Table의 크기가 데이터보다 많을 경우에 사용함
특정 해시값에 키가 몰리게 되면, 효율성이 크게 떨어짐
검색 : Index를 타고 들어가서 Key값을 비교한 후 다를 경우 다음 버켓을 찾아 값을 찾아 나감
삽입 : Index를 타고 들어가서 Key값을 비교한 후 다를 경우 다음 버켓을 찾아 비어있는 곳에 값을 입력함
삭제 : Index를 타고 들어가서 Key값을 비교하여 같을 경우 값을 지워주고, Dummy node를 넣어 검색할 때 다음 버켓으로 갈 수 있는 징검다리 역할을 해줌
해시충돌이 일어났을때 특정 조건을 활용하여 빈 버켓을 찾게 되는데, 이 조건을 잘 만드는 것도 중요함
계산 복잡성은 Table의 크기 대비 데이터 수에 따라 큰 편차를 가지게 됨(여유로울 수록 빨라지고, 빡빡할 수록 기하급수적으로 느려짐)

충돌해결 3) Resizing

전체적으로 Hash Table의 크기를 조정하고, 새롭게 만들어진 Hash Function으로 Hash Table를 Update(재정렬)하여 사용함
테이블에 할당되어 있는 공간을 모두 사용하였을때 사용하는 방법

📌reference

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡 

Hong Yohan