해시 충돌이란

해시 충돌에 대해 알아보기 전에, 먼저 해싱과 HashMap부터 짚고 넘어간다.

해싱(Hashing)이란 Key가 있는 위치를 산술연산으로 찾아가는 검색 방법을 말한다. 이 때 Key 값을 원소 위치로 바꿔주는 함수를 해시 함수라 하고 해시 함수에 의해 계산된 주소에 저장할 값을 저장한 표를 해시 테이블이라고 한다.

 

HashMap이란 Map 인터페이스의 구현체 중 하나로, 키밸류 쌍의 형태로 데이터를 매핑(Mapping)시켜 보관하는 동적 배열 형태의 자료구조다. HashMap 안에서 내가 원하는 데이터를 꺼내려면 키 또는 값을 넘겨서 그에 맞는 값 또는 키를 얻을 수 있다. 순서는 보장되지 않으며 매핑시키기 때문에 삽입, 삭제, 검색에 걸리는 시간이 평균 O(1)이다. 또한 이 HashMap의 Key는 중복을 허용하지 않지만 Value는 허용하며, 키밸류는 모두 null을 사용할 수 있다.

 

이 HashMap의 내부 구조는 배열로 구성돼 있고 Key는 이 내부 배열의 인덱스가 될 수 있다. 이 때 이 배열(=값이 저장되는 장소)을 버킷(Bucket)이라고 한다.

 

이제 해시 충돌에 대해 다른 포스팅에선 어떻게 설명하는지 확인해본다.

 

https://www.baeldung.com/java-hashmap-advanced

HashMap Under the Hood | Baeldung

충돌 또는 더 구체적으로 해시맵의 해시 코드 충돌은 2개 이상의 Key 객체가 동일한 최종 해시값을 생성해서 동일한 버킷 위치 또는 배열 인덱스를 가리키는 상황이다. 이 시나리오는 equals 및 hashCode 계약에 따라 자바에서 2개의 서로 다른 객체가 똑같은 해시 코드를 가질 수 있기 때문에 발생할 수 있다. 크기 조정 전의 기본 배열의 유한한 크기 때문에 발생할 수도 있다. 이 배열이 작을수록 충돌 가능성이 높아진다. 객체가 저장될 버킷을 결정하는 건 Key의 해시 값임을 명심하라. 따라서 두 Key의 해시 코드가 충돌하더라도 해당 항목은 여전히 동일한 버킷에 저장된다.
기본적으로 구현에서는 링크드 리스트를 버킷 구현으로 사용한다...(중략)

 

https://odol87.tistory.com/4

[JAVA] HashMap의 해시충돌(hash collision)과 자바의 대응책

해시함수를 써서 해시값으로 특정 자료를 분류하는 데 항상 따라오는 문제로 충돌 이슈가 있다...(중략)...해시맵에서 Key로 쓰이는 각종 자료형들에 대해 완벽한 해시 함수를 제공할 순 없다. 서로가 구별되거나 Number 객체는 객체가 나타내려는 값 자체를 해시 대상 값으로 쓸 수 있기 때문에 완전한 해시 함수 대상으로 삼을 수 있지만 String, POJO에 대해 완전한 해시 함수를 만드는 건 사실상 불가능하다
또한 자바에서 해시값을 만드는 메서드인 hashCode()의 리턴형은 int다. 32비트 정수 자료형으론 완전한 해시 함수를 만들 수 없다. 객체 수가 2^32보다 많을 수 있고 모든 해시맵이 2^32만큼의 배열을 갖고 있을 순 없기 때문이다
따라서 해시맵을 비롯한 해시 함수를 사용하는 많은 연관 배열(Dictionary, Map, Symbol Table 등) 구현체에선 메모리 절약을 위해 실제 해시 함수의 정수 범위 N보다 작은 M개의 원소가 있는 배열만을 사용한다.

int index = X.hashCode() % M;

이런 방식을 사용하면 서로 다른 해시 코드를 갖는 서로 다른 객체가 1/M의 확률로 같은 해시 버킷을 사용하게 된다. 이것이 자바의 해시 충돌 문제다. 해시 함수 구현상의 문제가 아닌 또 다른 종류의 해시 충돌인 셈이다...(중략)

 

http://wiki.hash.kr/index.php/%ED%95%B4%EC%8B%9C%EC%B6%A9%EB%8F%8C

해시충돌 - 해시넷

해시 충돌이란 해시함수가 서로 다른 2개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 해시 충돌은 해시함수를 이용한 자료구조, 알고리즘의 효율성을 떨어뜨리기 때문에 해시함수는 해시 충돌이 자주 발생하지 않도록 구성돼야 한다
입력값은 다른데 출력값이 같다는 건 특정 키의 버킷에 데이터가 집중된다는 것을 의미하기 때문에 해시 충돌은 해시테이블의 성능을 저하시킨다. 해시테이블에서 쓸 수 있는 모든 키의 숫자는 테이블 인덱스 개수보다 많기 때문에 불가피한 충돌을 야기하고, 그렇기 때문에 해시 충돌을 피할 수 있는 알고리즘은 없다

- 원인

1. 비둘기집 원리 : 대부분의 해시 알고리즘들은 항상 고정된 길이의 결과 문자열을 리턴한다는 특징을 갖고 있다...(중략)...무차별 대입으로 해시 결과가 동일한 두 입력 값을 찾으려면 개인용 컴퓨터로는 상당히 많은 시간을 요하게 된다. 하지만 아무리 큰 숫자라도 무한은 아니란 점에서 특정한 두 입력값의 결과 해시값이 동일한 경우가 발생할 수 있다. 비둘기가 5마리일 때 상자가 4개 뿐이라면 비둘기를 균등하게 분배해도 최소한 한 상자에는 2마리의 비둘기가 들어간다. 이런 원리를 비둘기집 원리라고 한다. 이 원리에 따라 해시에서는 '서로 다른 입력값의 해시 결과값이 동일한 문제'인 해시 충돌이 발생할 여지가 있다

2. Birthday Paradox : 생일 패러독스란 366명의 사람이 모였을 때 생일이 겹치는 사람이 최소 2명 이상이 된다는 것으로 모든 경우의 수를 넘어서는 통계 표본이 존재할 때 중복되는 값이 필연적으로 발생한다는 수학적 원리를 기술한 것이다. 일반적으로 존재할 수 있는 생일의 수가 총 365가지이므로 임의의 두 사람의 생일이 같을 확률은 1/365이다. 365명이 모여야 생일이 같은 경우가 있을 거라고 생각할 수 있다. 그러나 실제론 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘고 57명이 모이면 99%를 넘는다. 생일 패러독스와 비슷하게 암호학적 해시 결과가 같은 두 입력값을 찾는 것 역시 모든 입력값을 계산하지 않아도 충분히 높은 확률로 해시 충돌을 찾을 수 있다. 이런 암호 공격을 생일 공격이라고 부른다

 

정리하면 해시 충돌이란

 

• 서로 다른 2개의 입력값을 넘겼는데 같은 출력값이 오는 경우를 말한다
• 해시 함수가 무한한 입력값을 받아 유한한 개수의 출력값을 만드는 경우 비둘기집 원리에 의해 해시 충돌은 항상 존재한다
• 해시 함수를 사용한 자료구조, 알고리즘의 효율성을 떨어뜨린다

 

실제 서비스를 운영하거나 해시 함수를 사용한 어떤 암호 처리를 수행하는 프로그램의 경우 해시 충돌을 최대한 예방하는 게 중요할 것 같은데, 이것의 예방법은 어떤 것이 있을까?

 

https://en.wikipedia.org/wiki/Hash_collision

Hash collision - Wikipedia

해시 충돌은 불가피하므로 해시 테이블에는 충돌 해결이라고 하는 처리 매커니즘이 있다. 가장 일반적인 2가지 전략은 개방형 주소 지정(Open Addressing), 개별 연결(Separate Chaining)이다. 캐시 인식 충돌(Cache-Conscious Collision Resolution)은 과거에 문자열 해시 테이블에 대해 논의된 또 다른 전략이다

- 개방형 주소 지정 : 해시 테이블의 Cell에는 이 메서드의 3가지 상태(사용됨, 비어 있음, 삭제됨) 중 하나가 할당된다. 해시 충돌이 발생하면 테이블을 검색해 레코드를 비어있는 것으로 표시된 대체 Cell로 이동시킨다. 해시 충돌이 발생하고 이 방법이 구현될 때 발생하는 다양한 유형의 프로빙이 있다...(중략)...개방형 주소 지정은 폐쇄형 해싱이라고도 한다

- 개별 연결 : 이 전략을 쓰면 둘 이상의 레코드를 해시 테이블의 Cell에 연결할 수 있다. 두 레코드가 동일한 셀로 지정되는 경우 둘 다 해당 Cell에 연결된 리스트로 이동한다. 이는 동일한 해시 값을 가진 레코드가 동일한 Cell에 들어갈 수 있기 때문에 해시 충돌이 발생하는 걸 효율적으로 방지하지만 단점이 있다. 너무 많은 리스트를 추적하는 건 어렵고 사용되는 도구가 매우 느려질 수 있다. 개별 연결은 오픈 해싱이라고도 한다

 

위키백과에 설명돼 있지만 잘 모르겠으니 이번에도 다른 글을 확인해봤다.

 

https://zin0-0.tistory.com/294

HashMap과 해시 충돌

- 개방 주소 방법(개방형 주소 지정) : 데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식. 해시 테이블 내의 새 주소를 탐사(Probe)해서 데이터를 입력한다. 데이터 개수가 적다면 성능이 좋지만 배열 크기가 커질수록(=M이 증가할수록) 캐시 효율성이 사라진다

- 분리 연결 방법(개별 연결) : 자바에서 사용하는 방식. 개방형 주소 지정 방식은 해시 버킷의 밀도가 높을수록 Worst Case 발생 빈도가 높아지는 반면 개별 연결 방식은 해시 충돌이 잘 발생하지 않도록 조정하면 Worst Case를 최대한 방지할 수 있다

 

https://ysjee141.github.io/blog/jdk/java-hashmap/

Java HashMap 동작 원리

자바 해시맵의 경우 Separate Chaining 방법을 사용하며 현재 Value의 다음 Value를 연결하는 방식으로 해결한다

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
	e = p;
else if (p instanceof TreeNode)
	e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
	for (int binCount = 0; ; ++binCount) {
		if ((e = p.next) == null) {
			p.next = newNode(hash, key, value, null); // 새로운 Node 생성해 연결
			if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
				treeifyBin(tab, hash);
			break;
		}
		if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
			break;
		p = e;
	}
}

위 코드에서 중요한 코드는 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); 인데 해시 버킷 개수가 일정 수준을 넘어가면 버킷 관리를 트리 형태로 전환해 관리한다는 것이다. 반대로 버킷 개수가 일정 수준으로 내려가면 트리 형태에서 링크드 리스트 형태로 변경해 관리한다. 이는 해시 충돌 빈도를 낮추기 위한 조치이며 메모리를 효율적으로 사용하기 위해선 버킷 개수를 사전에 예상할 수 있다면 변경 기준을 사전 정의하는 게 좋다

 

https://jaehoney.tistory.com/169

해시 충돌(Hash Collision)이란? [+ 전략 비교]!

해시 충돌 전략은 크게 2가지로 나뉜다

1. 체이닝 : 버킷에 링크드 리스트를 할당해서 해시 충돌이 발생하면 링크드 리스트에 데이터를 추가하는 방법이다. 탐색 시에는 해시코드를 기반으로 비교한 후 equals()가 false라면 찾거나 리스트가 끝날 때까지 다음 노드를 탐색한다. 자바에선 기본적으로 체이닝을 사용한다

2. 개방 주소법(Open Addressing) : 해시 충돌이 발생했을 시 정해진 규칙에 따라 비어있는 다른 버킷을 정해서 그 버킷에 데이터를 보관하는 방법이다. 개방 주소법은 대표적으로 3가지 있다.

- 선형 탐색(Linear Probing) : 해시 충돌 시 다음 버킷 또는 비어있지 않다면 몇 개 건너뛰어 데이터 삽입
- 제곱 탐색(Quadratic Probing) : 해시 충돌 시 제곱만큼 건너뛴 버킷에 데이터 삽입
- 이중 해시(Double Hashing) : 해시 충돌 시 해시를 한번 더 적용해서 나온 버킷에 데이터 삽입

OcccWiki에 따르면 해시 알고리즘이 일반적으로 충분히 빠르고 메모리 사용량도 과하다고 간주되지 않는다. 그래서 이러한 해시충돌 전략은 사실 성능 차이는 미미하다고 한다