해시(Hash) 간단하게 정리

해시?

다양한 길이의 데이터를 고정된 길이 데이터로 mapping한다.

이렇게 고정 크기 값으로 변환된 데이터를 해시라고 한다.

여기서 변환해주는 함수를 해시 함수라고 부른다.

어떤 문자가 들어가도 일정 길이의 데이터로 변환된다. 이미지는 해시 함수의 눈사태 효과를 설명하고 있음.

해시 테이블?

Key, Value로 이루어지는 data에서 Key값에 해시 함수를 사용하여 Key 값을 index로 변환하여 만들어지는 테이블

사람 이름이 Key, 전화번호가 Value인 데이터에 해시 함수를 적용시켰다.

문자열이던 Key는 해싱되어 두자리 정수 해시값이 된다. 이 고유 index에 Value값이 저장되는 것이다.

이로 인한 이득?

정렬을 안하므로 검색과 삽입이 정말 빠르다. 평균 시간복잡도 O(1)

그냥 hash function에 내가 찾고자 하는 값을 넣어서 index 변환을 하면 끝

주의점

1. 해시 함수의 성능이 떨어지면 해시 방식을 채택하는 의미가 없다.

2. 충돌이 일어날 수 있다.

서로 다른 키 값인데, 해시 함수의 매핑 결과값으로 같은 값이 나올 수 있다.

위 이미지에서는 John Smith와 Sandra Dee의 해시값이 중복이다.

이를 충돌(Collision)이라고 한다.

충돌의 해결방법

Seperate Chaining

충돌이 발생하면 연결 리스트로 연결한다. 

Sandra Dee는 John Smith에 연결 리스트로 연결되었다.

기본적인 해시 테이블에는 변화가 없고 연결 리스트로 추가되기 때문에 구현이 쉽고 삭제도 쉬움. 가장 전통적인 방식.

Open Addressing

충돌이 발생하면 다른 해시 버킷에 데이터를 삽입한다.

'다른 해시 버킷'을 '어떻게 지정하느냐'에 따라 방법이 여러개로 갈리게 된다.

위의 예시는 Linear Probing

어떻게 보면 해시값대로 저장되는게 아니기 때문에, 삭제 성능이 떨어지게 됨.

다음 Index로 검색을 연결해주는 Dummy Code까지 있어야 하며, 사실상 검색할때도 연속적으로 여러 Bucket을 접근하게 되는 것이다. 이런 이유로, 일정 수용률 이하에서는 Linear Probing Open Addressing의 성능이 좋지만, 일정량을 넘어가는 순간부터 성능이 확 떨어짐.

추가 역시 해시 버킷의 크기에 제약된다. 메모리는 Seperate Chaining에 비해 덜 사용함.