🥽 해시함수?

해시함수란 임의의 길이를 갖는 어떤 데이터를 고정된 길이의 데이터로 매핑시키는 함수입니다.

해시 테이블 자료구조에서 사용되며, 빠른 데이터 검색을 위한 것으로 많이 쓰입니다. key 를 해시함수에 넣어 Hash를 구하고 이것은 저장위치로서 데이터를 꺼내올 수 있습니다. 다만 서로다른 key가 해시값은 같을 수도 있습니다. 이것을 해시충돌 이라고 합니다.

💡 해시는 색인 또는 인덱스, hash function은 key->hash로 만들어 주는 함수, 해시테이블은 hash를 주소로 삼아 데이터를 저장하는 자료구조입니다.

장점
해시테이블은 key-value가 1:1로 매핑되어 삽입, 삭제 등의 과정에서 평균적으로 O(1)의 시간복잡도를 가집니다.

단점
해시충돌이 발생

😅 해시충돌 해결 방법 ?

1. 체이닝(Chaining)

체이닝은 저장소에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법입니다.

• 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적다.
• 해시테이블이 채워질수록, 조회시 성능저하가 덜 발생한다.

2. 개방주소법(Open Addressing)

해시충돌이 일어나면 다른 저장소에 데이터를 삽입하는 방식입니다.

• 대표적인 3가지

선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입
제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함!

• 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요 X
• 삽입, 삭제시 오버헤드가 적다.
• 저장할 데이터가 적을 때 더 유리

출처
https://ko.wikipedia.org/wiki/해시_함수
https://preamtree.tistory.com/20