🚀 들어가며
안정해쉬를 공부하면서 기존에 알던 해쉬를 다시 한번 정리해볼려고 합니다
1️⃣ 해시(Hash)란 무엇인가?
해시(Hash)란 데이터를 고유한 식별자로 매핑하는 과정입니다. 해시는 주로 데이터를 빠르게 검색하거나 저장하는 데 사용됩니다. 이 과정은 해시 함수(Hash Function)를 사용하여 데이터를 고정된 크기의 해시 코드로 변환하는 것을 포함합니다.
해시의 기본 개념은 매우 간단합니다. 예를 들어, 긴 문자열이나 큰 숫자 같은 복잡한 데이터를 입력하면, 해시 함수는 이를 고정된 길이의 숫자(해시 코드)로 변환합니다. 이 변환된 해시 코드를 통해 데이터에 빠르게 접근할 수 있습니다.
2️⃣ 해시 테이블(Hash Table)이란?
해시 테이블은 해시 함수를 사용하여 데이터를 효율적으로 저장하고 검색할 수 있는 데이터 구조입니다. 이 테이블은 배열과 유사하게 동작하지만 데이터가 인덱스가 아닌 해시 코드를 통해 저장된다는 점이 다릅니다.
🙋♂️ 동작방식
- 데이터를 삽입할 때 해시 함수가 데이터를 해시 코드로 변환합니다.
- 이 해시 코드를 배열의 인덱스로 사용하여 데이터를 해당 위치에 저장합니다.
데이터를 검색할 때도 동일한 해시 함수를 사용하여 데이터를 저장할 때 사용한 해시 코드를 다시 생성하고, 이를 통해 데이터를 빠르게 찾을 수 있습니다.
- 해시 테이블은 평균적으로 O(1)의 시간 복잡도로 데이터를 검색할 수 있어 매우 효율적입니다.
3️⃣ 해시 알고리즘(Hash Algorithm)?
해시 알고리즘은 입력된 데이터를 해시 코드로 변환하는 방법입니다. 자바에서 대표적으로 사용되는 해시 알고리즘은 객체의 hashCode() 메서드를 통해 구현됩니다.
결정성(Deterministic): 동일한 입력에 대해 항상 동일한 해시 코드를 생성해야 합니다.
빠른 계산 속도: 해시 함수는 매우 빠르게 실행되어야 합니다.
균일한 분포: 서로 다른 입력값에 대해 가능한 한 균일하게 해시 코드를 생성해야 합니다.
충돌 방지: 가능한 한 다른 입력에 대해 같은 해시 코드를 생성하지 않아야 합니다. 그러나, 현실적으로 완벽한 충돌 방지는 불가능하므로 충돌 해결 방법이 필요합니다.
4️⃣ 해시 충돌 해결 방법
해시 충돌을 해결하는 방법에는 여러 가지가 있습니다. 가장 일반적인 방법 두 가지는 체이닝(Chaining)과 오픈 어드레싱(Open Addressing)입니다.
체이닝(Chaining)
체이닝은 해시 테이블의 각 인덱스가 리스트(또는 다른 자료구조)를 가리키도록 하는 방법입니다. 해시 충돌이 발생하면, 충돌한 데이터를 해당 리스트에 추가합니다.
🙋♂️ 장점
- 구현이 간단하고, 충돌이 많이 발생할 경우에도 리스트로 관리할 수 있어 유연합니다.
🤣 단점
- 충돌이 많아지면 리스트가 길어져 검색 속도가 느려질 수 있습니다.
오픈 어드레싱(Open Addressing)
오픈 어드레싱은 충돌이 발생하면 다른 빈 공간을 찾아 데이터를 저장하는 방법입니다. 가장 많이 사용되는 오픈 어드레싱 방식은 선형 탐사(Linear Probing)입니다.
선형 탐사(Linear Probing): 충돌이 발생하면 바로 다음 인덱스를 확인하며 빈 자리를 찾습니다.
🙋♂️ 장점
- 추가적인 자료구조가 필요 없고, 메모리 사용이 효율적입니다.
🤣 단점
- 연속된 충돌이 발생할 경우, 해시 테이블의 성능이 급격히 저하될 수 있습니다.
🧀 정리
해시(Hash)와 해시 테이블은 데이터의 효율적인 저장과 검색을 가능하게 하는 핵심 개념입니다. 해시 함수는 데이터를 고정된 크기의 해시 코드로 변환하여 빠른 접근을 하지만 해시충돌을 일으킬수 있습니다. 이를 해결하기 위해 체이닝과 오픈 어드레싱 같은 방법이 사용됩니다. 자바에서는 체이닝 방식을 사용해서 해쉬충돌 해결하고 있습니다.
