[자료구조] 해시 충돌 Hash Collision

출처

https://ryu-e.tistory.com/87

해시(Hash)와 해시 충돌 해결 방법

 

https://www.geeksforgeeks.org/introduction-to-hashing-2/

Introduction to Hashing - GeeksforGeeks

 

ChatGPT

 

 

---

해치 충돌을 말하기 전 알아야할 개념들 

해시란  Hash

임의의 크기의 데이터를 해시 함수를 통해 고정된 크기의 데이터로 매핑한 값. 해시 값이라고도 한다. 해기 코드라 부르기도 한다.

해싱이란 Hashing

임의의 크기의 데이터를 입력 값으로 받아 해시값으로 변환하는 과정 또는 방법. 

해시 함수란 Hash Function

임의의 크기의 입력값(예: 문자열, 정수)을 고정된 크기의 값으로 변환하는 함수

• 목표 : 서로 다른 입력값이 고유한 해시값을 가지게 한다.
  • 그래서 동일한 입력값에 대해 항상 동일한 해시값을 반환해야 한다.
• 하지만 이것을 완벽히 보장하는 건 불가능하다. 서로 다른 입력 값의 해시값들이 동일한 상황을 해시 충돌이라고 한다.

해시 테이블이란 Hash Table

해싱을 통해 키와 값을 매핑한 자료구조. 배열이다. 입력값인 키로 생성된 해시값을 이 배열의 인덱스 값으로 이용한다.

 

🤔 배열은 연속된 저장공간이고, Java는 해시값을 정수로 쓰니까, JVM안 메모리 영역에 정수 크기만큼 Hash Table이 할당되어야 하는 거 아닌가?

💡 아니다. 해시코드의 범위 전체가 해시 테이블의 크기로 할당되는 것이 아니다. 해시코드는 일반적으로 32비트 정수(자바에서는 int)이므로, 모든 정수의 범위(약 43억 개)를 인덱스로 사용하려면 엄청난 양의 메모리가 필요하게 된다. 대신, 해시 테이블은 보통 적절한 크기로 설정되고, 해시코드를 테이블 크기에 맞게 조정해 인덱스를 결정한다. 

 

자바에서 해시코드와 테이블 크기의 간의 관계

1. 해시코드 생성 및 변환

• 자바에서 객체의 해시코드는 int 타입으로 표현되며, 이는 32비트 정수 값으로 표현된다.
• 해시코드는 모든 정수 범위를 가질 수 있지만, 해시 테이블의 크기는 보통 이를 훨씬 작은 값으로 제한한다.

2. 해시 테이블의 크기와 인덱스 결정

• 실제로 해시 테이블은 일반적으로 고정된 크기의 배열이다. 이 배열의 크기를 보통 더 나은 성능을 위해 소수(예: 101, 1009 등)로 설정되며, 데이터의 양에 다라 동적으로 조정되기도 한다.
• 해시코드를 해시 테이블의 크기에 맞게 변환하기 위해, 보통 모듈러 연산(%)을 사용해 해시코드를 테이블의 크기에 맞는 인덱스로 저장한다.
  • 예를 들어, 해시 테이블의 크기가 100이라면, hashcode % 100을 통해 해시코드를 0에서 99사이의 값으로 변환해 해시 테이블의 인덱스를 결정한다.

 3. 메모리 사용의 효율화

• 해시 테이블의 크기는 키의 해시값과 다르며, 모든 가능한 해시코드에 대해 별도의 슬롯을 메모리에 할당하는 것이 아니다.
  • 슬롯 slot : 해시 테이블에서 데이터를 저장할 수 있는 개별적인 저장 공간. 배열의 특정 위치와 동일한 개념
• 해시 테이블의 크기는 일반적으로 실제 저장해야 하는 데이터의 수와 충돌의 빈도를 고려하여 설정되며, JVM은 이를 효율적으로 관리한다.
• 특히, 해시코드 전체 범위를 인덱스로 사용하지 않고, 해시 테이블의 크기에 맞게 변환하여 배열의 특정 위치에 값을 저장하는 방식으로 메모리 사용을 효율화한다.

 

🤔 해시 테이블과 해시맵은 뭐가 다르지?

특징	해시 테이블 Hash Table	해시맵 HashMap
역사적 배경	자료 구조의 개념을 설명하는 데 사용된다. 해시 테이블은 해시 함수와 배열 기반 인덱싱을 통해 데이터를 저장하고 검색하는 자료구조이다.	해시 테이블의 한 구현체이다. 주로 프로그래밍 언어의 구체적인 자료구조 클래스나 타입으로 사용된다.
표현 방식 사용 관점	어떻게 데이터를 효율적으로 저장하고 검색할 지에 대한 아이디어와 기술적이 동작을 설명할 때 주로 사용된다.	특정 언어에서 제공하는 구현된 자료구조를 설명하는 용어이다.

 

 

해시 충돌이란 Hash Collision

해시 함수는 입력을 고정된 크기의 해시값으로 변환하기 때문에, 서로 다른 입력값이 같은 해시값을 가지는 것.

해시 충돌의 발생 확률은 알고리즘의 크기, 해시 값의 부포 및 해시 함수의 효율성에 따라 달라진다.

해시 충돌이 발생하면, 새로 입력받은 키의 해시값이 이미 점유된 슬롯으로 매핑되기 때문에 충돌 처리 기술을 사용해 처리해야 한다.

 

해시 충돌을 예방하는 방법

해시 충돌을 완벽하게 예방할 수는 없지만, 발생 확률을 줄일 수는 있다.

1. 좋은 해시 함수를 설계

🤔 좋은 해시 함수는 어떤 특징을 가지고 있나?

1. 효율적으로 계산한다.

• 입력 데이터를 가능한 빠르게 해시값으로 변환해야 한다.

2. 키를 균등하게 분배해야 한다. (각 테이블 위치가 동일한 확률을 갖는다.)

• 모든 가능한 입력값데 대해 해시값이 균등하게 분포되도록 설계해야 한다. 이를 통해 특정 영역에 데이터가 몰리지 않게 한다.

3. 충돌을 최소화해야 한다.

• 비슷한 입력값에 대해 비슷한 해시값을 생성하지 않도록 설계해야 한다. 

4. 로드 팩터가 낮아야 한다.

• 로드 팩터 load factor : 해시 테이블에 저장된 데이터 개수를 테이블의 크기로 나눈 값.
• 로드 팩터 = 해시 테이블의 총 데이터 수 / 해시 테이블의 크기
• 로드 팩터로 알 수 있는 것 : 해시 테이블이 얼마나 빽빽하게 채워져 있는지. 해시 테이블의 성능 및 확장 시기를 결정하는 지표이다.
  
  • 일반적으로 로드 팩터가 특정 기준 이상(예: 0.7~0.75 이상)이 되면, 해시 테이블의 크기를 두 배로 늘리는 재해싱을 수행한다.
    • 재해싱 : 해시 테이블이 충돌로 인해 효율이 떨어지거자 데이터가 많아진 경우, 새로운 더 큰 해시 테이블로 모든 데이터를 재배치하는 방법
    • 재해싱의 장점 : 해시 충돌을 줄이고 성능을 개선할 수 있다.
    • 재해싱의 단점 : 재해싱 과정에서 추가적인 연산이 필요해 리소스가 많이 소모된다. 
• 낮은 로드 팩터 : 해시 테이블에 많은 빈 슬롯이 있다는 것을 의미한다. 충돌 가능성이 낮아지고 탐색 성능이 좋아질 수 있지만, 메모리 낭비가 발생할 수 있다.
• 높은 로드 팩터 : 해시 테이블에 많은 데이터가 저장되어 있다는 것을 의미한다. 충돌 가능성이 높아지고, 그에 따라 데이터 검색과 삽입의 성능이 저하될 수 있다.

2. 해시 테이블의 크기 조정

해시 테이블의 크기글 적절히 큰 소수로 설정하면 해시 충돌 발생 가능성이 낮아진다.

🤔 왜 해시 테이블의 크기를 소수로 설정하면 해시 충돌 발생 가능성이 줄어드나?

💡 소수의 특징으로 인해 고른 분포를 가진다. + 모듈러 연산의 균일성 증가 + 패턴 회피

해시 함수는 일반적으로 해시값을 테이블 크기로 나누고(모듈러 연산 사용), 그 나머지를 사용해 인덱스를 결정한다. 

해시 테이블의 크기가 소수가 아닌 짝수이거나 다른 특정한 수(예: 10, 20, 100 등)일 경우, 해시 함수가 생성한 해시값이 특정 패턴을 가지면, 일부 인덱스에 값이 집중되어 충돌이 자주 발생할 수 있다.

소수는 다른 수와 공통 인수를 가지지 않으므로, 해시값의 패턴에 관계없이 해시값들이 더 다양한 인덱스에 분포하게 된다.

 

해시 충돌을 처리하는 방법

1. 체이닝 Chaining : 충돌 시 연결 리스트에 추가하는 방법

• 해시 테이블의 각 슬롯을 연결 리스트(또는 다른 자료구조)로 관리해 충돌이 발생한 데이터를 모두 저장하는 방식
• 해시 값이 같은 데이터가 추가될 때, 해당 슬롯의 연결 리스트에 데이터를 추가한다.
• 장점 : 테이블 크기에 제한이 없으며, 데이터가 계속 추가될 수 있다.
• 단점 : 연결 리스트에 데이터가 많아지면, 탐색 시간이 O(n)으로 증가할 수 있다. 해시를 사용하는 이유는 탐색, 삽입, 삭제 기능이 O(1)이라는 장점으로 사용하는 것이기에 문제가 된다. 
  • 이런 문제로 연결 리스트 대신 균형 이진 탐색 트리를 사용해 탐색 시간을 O(log n)으로 개선할 수 있다.

• 관련 글 -> [자료 구조] 이진 탐색 트리 Binary search Tree, BST

2. 개방 주소법 Open Addressing : 충돌 시 다른 주소 공간에 데이터를 저장하는 방법

대표적인 기법으로 선형 프로빙(Linear Probing), 이차식 프로빙(Quadratic probing), 이중 해시(Double hashing)이 있다.

1. 선형 프로빙 Linear Probing

충돌이 발생하면 고정된 크기만큼 계속해서 다음 슬롯을 탐사해 빈 슬롯을 찾는다.

 

동작 방식

1. 충돌 발생 시 : 해시 함수에 의해 계산된 인덱스가 이미 사용 중인 경우, 한 칸씩 순차적으로 이동해 빈 슬롯을 찾는다.

2. 새로운 슬롯을 찾을 때까지 다음 인덱스로 이동하며(보통 +1), 빈 슬롯이 나오면 해당 위치에 데이터를 저장한다.

3. 해시 테이블의 끝에 도달하면 순환하여 테이블의 처음부터 탐색을 이어간다.

 

수식 표현

• h() = 해시 함수
• k = 해싱되는 키
• i = 충돌 횟수
• n = 해시 테이블의 크기
• h(k, i) = (h(k) + i) % n

선형 프로빙의 장점

구현이 간단하고 추가적인 자료구조가 필요없다.

 

선형 프로빙의 단점

1차 클러스터링 발생 : 여러 충돌이 인접한 슬롯에 모이게 되면, 새로운 데이터를 삽입하거나 검색할 때 같은 영역에서 탐색이 이루어지므로 탐색 시간이 길어지는 문제가 발생한다.

 

2. 이차식 프로빙 Quadratic Probing

선형 프로빙과 다르게 점점 더 큰 폭으로 탐사하는 방식으로, 빈 슬롯을 찾기 위해 제곱 단위로 이동한다.

 

동작 방식

1. 충돌 발생 시 : 기본 해시 인덱스에서 충돌이 발생하면 제곱 간격으로 이동해 새로운 슬롯을 찾는다.

2. i 번째 충돌에서는 i 제곱만큼의 간격으로 이동한다. 예를 들어, +1, +4, +9, +16 등으로 탐색한다.

 

수식 표현

• h() = 해시 함수
• k = 해싱되는 키
• i = 충돌 횟수
• n = 해시 테이블의 크기
• h(k, i) = (h(k) + i * i) % n

이차식 프로빙의 장점

1차 클러스터링 문제를 줄일 수 있다. 슬롯이 제곱 간격으로 떨어지기 때문에, 충돌된 요소들이 서로 멀리 떨어져 저장될 가능성이 높아져 밀집 문제가 완화된다.

 

이차식 프로빙의 단점

2차 클러스터링 문제 : 동일한 해시값을 가지는 키들이 동일한 순서로 탐사하는 경향이 있어, 여전히 충돌 문제를 완전히 해겨하지는 못한다.

빈슬롯을 찾을 때 이동 간격이 커질 수 있어, 모든 슬롯을 탐색하기 전에 배열을 순회하지 못하는 경우가 생길 수 있다. 이를 해결하기 위해 테이블 크기를 소수로 설정하는 것이 중요하다.

3. 이중 해시 Double Hashing

두 개의 해시 함수를 사용한다. 충돌 발생 시, 두 번째 해시 함수를 사용해 탐색 간격을 결정하고 다른 위치로 이동한다.

이중 해시를 사용할 경우의 해시 함수의 조합은 다음과 같다.

 

• i = 충돌 횟를 나타내는 음이 아닌 정수
• k = 해싱되는 키
• n = 해시 테이블의 크기
• h1() = 첫 번째 해시 함수
• h2() = 두 번째 해시 함수
• h(k, i) = (h1(k) + i * h2(k)) % n

 

개방 주소법의 장점 : 별도의 자료구조가 필요하지 않으며, 모든 데이터가 해시 테이블 내에 저장된다.

개방 주소법의 단점 : 테이블이 가득 찼을 때 성능이 급격히 저하될 수 있다.