Hash Map Collision Resolution Techniques Explained

해시 충돌은 체인 또는 오픈 주소 지정 방법을 사용하여 해결할 수 있습니다.

### 해시 충돌 해결에 대한 이해: 체인 및 오픈 주소 지정
* 🔍 오늘은 해시 충돌이 무엇인지에 대한 이전 논의를 바탕으로 **해시 충돌을 해결하는 방법**을 살펴보겠습니다.
* 🛠 해시 충돌을 해결하는 두 가지 주요 방법에는 **체인 연결과 오픈 주소 지정**이 있습니다.
* 📦 체인 방식은 충돌하는 요소를 저장하기 위해 추가 공간을 활용하며, 종종 이러한 충돌을 효과적으로 관리하기 위해 **연결된 목록**을 사용합니다.
* 🚪 반면, **오픈 어드레싱은 추가 공간을 사용하지 않고 기존 배열에서 인접한 빈 슬롯**을 찾아 충돌을 해결합니다.
* 🔄 오픈 주소 지정은 **선형 프로빙, 쿼드 프로빙, 이중 해싱**의 세 가지 기술로 더 나눌 수 있으며, 각 기술은 충돌을 처리하는 방식이 다릅니다.
* 📊 예를 들어, 선형 프로빙에서 충돌이 발생하면 알고리즘은 **빈 슬롯을 찾을 때까지 다음 사용 가능한 슬롯을 순차적으로 확인**합니다.
* 📈 그러나 이차 프로빙은 **충돌 횟수의 제곱**을 기준으로 다음 슬롯을 계산하므로 클러스터링 문제를 줄이는 데 도움이 됩니다.
* ⚖ 연결 목록이 너무 길어지면 검색 시간이 길어질 수 있는 반면, **오픈 주소 지정은 클러스터링이 발생**할 수 있으므로 사용 사례에 따라 올바른 방법을 선택해야 합니다.

### 오픈 주소 지정 및 해시 충돌 해결 기술 이해하기
* 🔍 값을 삽입하는 과정에서 **200 및 787과 같은 키를 삽입하려고 할 때 충돌**이 발생하여 사용 가능한 슬롯을 찾기 위한 일련의 모듈식 산술 연산이 발생했습니다.
* ⚙ 충돌을 해결하기 위해 이차 프로빙 기법을 사용했는데, **선형 프로빙에 비해 비교 횟수가 줄어들어 클러스터링을 피하는 데 효율적**이라는 점이 강조되었습니다.
* 📊 토론에서는 **506, 200, 787과 같은 특정 키 간의 충돌이 발생하지 않아** 해시 테이블 항목 관리에 있어 프로빙 방법이 효과적이라는 점이 강조되었습니다.
* 🔄 프로빙 시퀀스가 반복적인 패턴에 빠지지 않도록 **두 번째 해시 함수를 적용**하여 공간 활용도를 높이는 **이중 해싱 개념**이 도입되었습니다.
* ⚠ 두 번째 해시 함수의 출력은 비효율적인 공간 액세스로 이어질 수 있는 주기적 패턴을 방지하기 위해 **테이블 크기와 일치해야 한다는 지적**이 있었습니다.
* 🗑 오픈 주소 지정에서 키를 삭제할 때의 문제점, 특히 **키가 없을 경우 사용 가능한 슬롯을 잘못 해석**하여 중복 항목이 발생할 수 있다는 점에 대해 논의했습니다.
* 🔖 **삭제된 슬롯을 표시하고 후속 항목을 이동하는 등의 솔루션**이 제안되었지만, 각 방법에는 고유한 복잡성과 성능 오버헤드가 발생합니다.
* 💻 마지막으로, **JDK 7의 링크드 리스트에서 JDK 8의 링크드 리스트와 레드블랙 트리의 조합**으로 진화한 Java의 해시 충돌 처리 방식이 강조되어 **검색 효율성이 크게 개선**되었음을 보여줬습니다.

해시맵의 해시 충돌 해결 방법 (hash map & hash collision 해결)

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널


쉬운코드

해시 충돌 해결 방법을 설명한다.

해시 충돌 해결 방법은 체인 방식과 오픈 어드레싱 방식 두 가지로 나뉜다.

체인 방식은 추가적인 공간을 활용하여 충돌을 해결한다.

체인 방식의 대표적인 방법은 링크드 리스트를 사용하는 것이다.

오픈 어드레싱 방식은 추가적인 공간을 사용하지 않고, 비어있는 인접 공간을 활용한다.

해시맵의 내부 구현 방식과 예제에서 사용할 키-밸류 쌍의 특징을 설명한다.

링크드 리스트를 이용한 체인 방식으로 해시 충돌을 해결하는 과정을 예제를 통해 보여준다.

키 100, 921, 506 등을 순차적으로 해시맵에 추가하며 충돌 발생 시 링크드 리스트를 활용하는 방법을 설명한다.

충돌 발생 시 새로운 노드를 링크드 리스트의 헤드에 추가하는 이유를 설명한다.

체인 방식의 장단점을 간략하게 언급한다.

오픈 어드레싱 방식: 리니어 프로빙

오픈 어드레싱 방식의 개념과 리니어 프로빙 방식의 동작 원리를 설명한다.

리니어 프로빙은 충돌 발생 시 해시 값에 충돌 횟수(i)를 더하여 빈 공간을 찾는 방식이다.

리니어 프로빙 방식을 사용하여 키 100, 921, 506, 200, 787을 해시맵에 추가하는 과정을 예제로 보여준다.

리니어 프로빙 방식의 단점으로 클러스터링 현상을 지적한다.

오픈 어드레싱 방식: 쿼드래틱 프로빙

쿼드래틱 프로빙 방식은 해시 값에 충돌 횟수의 제곱을 더하여 빈 공간을 찾는 방식이다.

쿼드래틱 프로빙 방식을 사용하여 키 100, 921, 506, 200, 787을 해시맵에 추가하는 과정을 예제로 보여준다.

쿼드래틱 프로빙은 리니어 프로빙에 비해 클러스터링 현상이 덜 발생하고, 충돌 해결을 위한 이동 횟수가 상대적으로 적다.

오픈 어드레싱 방식: 더블 해싱

더블 해싱은 충돌 발생 시 다른 해시 함수를 사용하여 빈 공간을 찾는 방식이다.

더블 해싱은 동일한 해시 값을 생성하는 서로 다른 키 값의 문제를 해결한다.

더블 해싱에서 두 번째 해시 함수의 결과값은 해시맵의 크기와 서로소여야 한다.

오픈 어드레싱 방식의 주의점 및 삭제 처리

오픈 어드레싱에서 키 삭제 시 발생할 수 있는 문제점을 설명한다.

삭제된 키의 위치를 '삭제' 표시로 남겨 다음 탐색 시 확인하도록 하는 방법을 설명한다.

삭제 시 삭제 위치의 다음 키들을 앞으로 당겨 공간을 재활용하는 방법을 설명한다.

JDK 7까지는 링크드 리스트(체인 방식)를 사용했고, JDK 8부터는 링크드 리스트와 레드 블랙 트리를 혼용한다.

충돌 횟수가 임계치를 넘으면 링크드 리스트를 레드 블랙 트리로 변경하여 성능을 향상시킨다.

JDK 8의 변경으로 인해 해시 충돌 처리 성능이 향상되었다.