해시는 비둘기 집, 충돌이 일어날 수 있으니 충돌을 관리하자!
📖 해시(Hash)란?
💡 해싱(Hashing) : 타 검색 방법처럼 비교 방식을 사용하지 않고, 산술 연산으로 키 값의 위치를 산출, 데이터로 직접 접근하는 검색 방법
💡 해시 함수 = 해시 : 해싱 과정에서 사용하는 산술 연산, 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
💡 해시 값 : 해시 함수를 적용하여 나온 고정된 길이의 값, 데이터 저장 주소
💡 해시 테이블 : 해시 함수로 산출된 주소의 위치에 데이터를 저장한 표(key-value 형태로 저장)
1. 해시의 장점
ArrayList,LinkedList와 비교했을 때,
ArrayList는 내부 인덱스를 이용하여 검색이 한 번에 이루어지기 때문에 빠른 검색 속도를 보장하는 반면, 데이터의 추가/삭제시 많은 데이터가 밀리거나 당겨져야하기 때문에 많은 시간이 소요됨LinkedList는 데이터 추가/삭제시 인근 노드들의 참조값만 수정해 줌으로써 빠른 처리가 가능하지만 데이터 검색시 해당 노드를 찾기 위해 처음부터 순회 검색을 해야하기 때문에 데이터 수가 많아질수록 검색 효율이 떨어짐
Hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖고, 데이터 추가/삭제시 기존 데이터를 밀어내거나 당기는 작업 없이 해쉬 함수를 활용하여 해시 값(주소 값)을 만들고 이를 인덱스로 활용하기 때문에 데이터 추가/삭제 속도도 빠름
2. 해시의 충돌(Collusion)
📌 장점 많은 해시의 필수 고려사항, 충돌(collusion)
이미지 및 내용 출처: Preamtree의 행복로그
충돌: 각각 다른 두 개의 값이 동일한 해시 값을 가져 동일한 위치에 저장되는 경우
(해시 함수의 입력값은 무한하지만, 출력값의 가짓수는 유한하기 때문에 충돌 발생 cf. 비둘기집 원리)
예를 들어, 각각 다른 값인k1과k2가 있을 때
이 둘의 해시 값인hash(k1)과hash(k2)가 같은 경우 충돌 발생
해시 충돌을 해결하는 방법
-
체이닝(Chaining) : 버켓 내에 LinkeList 할당, 충돌 발생 시 LinkedList로 데이터 연결, 데이터의 주소값은 바뀌지 않음(Closed Addressing)
-
개방 주소법(Open Addressing) : 체이닝의 경우 버켓이 꽉 차더라도 LinkedList로 계속 데이터를 연결하여 늘려가기에 데이터의 주소값이 바뀌지 않지만, 개방 주소법은 충돌 발생시 다른 버켓에 데이터 삽입
①
선형 탐색(Linear Probing): 해시 충돌시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터 삽입②
제곱 탐색(Quadratic Probing): 해시 충돌시 제곱만큼 건너뛴 버켓에 데이터 삽입③
이중 해시(Double Hashing): 해시 충돌시 다른 해시 함수를 한 번 더 적용한 결과 이용 데이터 삽입
