[JAVA] HashMap이란? 해시충돌(Hash Collision) 발생시 자바는 어떻게 대처할까?

HashMap

HashMap은 Map의 대표적인 구현 클래스로, Key값의 중복을 허용하지 않는다. Map의 구조인 key-value쌍으로 구성되어 있는것이 특징이다. 즉, 두 Key 객체의 hashCode()값이 같고, equals() 메서드가 true를 반환한다면 같은 객체로 인식한다. HashMap은 입출력 순서가 동일하지 않을 수 있고 초기 저장 용량의 기본값은 16이다. 원소의 개수가 16개가 넘어갈 경우 자동으로 늘어난다. 일정 사이즈가 넘어가면 자동으로 TreeMap으로 변환된다.

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

 

list 형태를 사용하지 않고 HashMap을 사용하는 이유는 성능때문이다. Key를 index로 접근하므로, 일반적으로 삽입, 검색에서 O(1)의 시간복잡도를 갖고 있다. 해시 충돌이 많이 나는 경우 연결리스트를 쭉 탐색하므로 O(N)까지도 증가할 수 있다.

 

주요 메서드

주요 메서드는 Map 인터페이스의 추상 메서드로, 크게 데이터의 추가, 변경, 정보 추출 및 삭제로 나눌 수 있다.

구분	리턴 타입	메서드명	기능
데이터 추가	V	put(K value, V value)	입력매개변수(key, value)를 Map 객체에 추가
	void	putAll(Map<? extends K, ? extneds V> m)	입력매개변수 Map 객체를 통째로 추가
데이터 변경	V	replace(K key, V value)	Key에 해당하는 값을 Value 값으로 변경(old값 리턴) 단, 해당 Key가 없으면 null 리턴
	boolean	replace(K key, V oldValue, V newValue)	(key, oldValue)의 쌍을 갖는 엔트리에서 oldValue를 new Value로 변경. 단, 해당 엔트리가 없으면 fasel 리턴
데이터 정보 추출	V	get(Object key)	매개변수의 Key값에 해당하는 oldValue를 리턴
	boolean	containsKey(Object key)	매개변수의 Key값이 포함되어 있는지 여부
	boolean	containsValue(Object key)	매개변수의 Value값이 포함되어 있는지 여부
	Set<K>	keySet()	Map데이터들 중 Key들만 뽑아 Set 객체로 리턴
	Set<Entry<K, V>>	entrySet()	Map의 각 엔트리들을 Set 객체로 담아 리턴
데이터 삭제	V	remove(Object key)	입력매개변수의 Key를 갖는 엔트리 삭제 단, 해당 Key가 없으면 아무런 동작X
	boolean	remove(Object key, Object value)	입력 매개변수의 key, value를 갖는 엔트리 삭제 단, 해당 엔트리가 없으면 아무런 동작X
	void	clear()	Map 객체 내의 모든 데이터 삭제

 

해시 함수(Hash Function)

해시 함수는 임의 길이의 입력 값을 고정 길이의 암호화된 출력으로 변환해주는 함수이다. key를 해시 함수에 넣어 나오는 결과가 hash이며, 결국 해시 함수란 key를 hash로 만들어주는 함수이다.

 

특징

• 어떤 입력 값에도 항상 고정된 길이의 해시값을 출력한다.
• 입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력한다.(눈사태 효과)
• 출력된 결괏값을 통해 입력값을 유추할 수 없다.

 

해시 충돌(Collisions)

HashMap이 올바르게 작동하기 위해선, 동일한 키는 같은 해시(hash) 값을 가져야 한다. 그러나 해시 함수는 입력 값의 길이가 어떻든 고정된 길이의 값을 출력하기 때문에 입력값이 다르더라도 같은 결괏값이 나오는 경우가 있다. 이를 해시 충돌이라고 말한다.

 

HashMap은 키 집합인 정의역과, 값 집합인 공역의 대응에 해시 함수를 이용하기 때문에 해시 충돌이 하나도 일어나지 않는 해시 함수를 만드는 것은 비둘기집 원리에 의해 불가능하다. 따라서 해시 충돌에 대해 안전하다는 해시 함수는 충돌이 거의 일어나지 않는 해시 함수를 의미한다.

비둘기집 원리란?
n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다는 원리를 말한다. 

 

 

해시 충돌 완화 방법

해시 충돌을 완화하는 방법에는 크게 개방 주소법(open addressing)과 분리 연결법(Separating Chaining)이 존재한다.

• 개방 주소법(open addressing) : 해시 테이블 크기는 고정하면서 저장할 위치를 찾는다.
• 분리 연결법(Separating Chaining) : 해시 테이블의 크기를 유연하게 만든다.

 

개방 주소법(open addressing)

한 버킷 당 들어갈 수 있는 엔트리는 하나이지만 해시 함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용하는 방법이다. 개방 주소법은 대표적으로 아래 3가지가 존재한다.

• 선형 탐색(Linear Probing) : 해시충돌 시 다음 버킷, 혹은 몇 개를 건너뛰어 데이터를 삽입
• 제곱 탐색(Quadratic Probing) : 해시충돌 시 제곱만큼 건너뛴 버킷에 데이터를 삽입
• 이중 해싱(Double Hashing) : 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용

 

분리 연결법(Separate chaining)

버킷에 linked list 혹은 tree를 사용하여 한 버킷당 들어갈 수 있는 엔트리 수에 제한을 두지 않는다. 개방 주소법(open addressing)과 비교했을 때 추가적인 메모리 공간이 필요하며, 테이블의 적재율(Load Factor)에 따라 선형적으로 성능이 저하된다. 

 

 

자바에서의 해시충돌(Hash Collision)

자바 HashMap에서는 분리 연결법(Separate Chaining)과 보조 해시 함수를 사용하여 해시 충돌을 방지한다. 개방 주소법(Open Addressing)은 데이터를 삭제할때 처리가 비효율적인데, HashMap에서 remove() 메서드는 매우 빈번하게 호출될 수 있기 때문이다. 또 한 HashMap에 저장된 엔트리 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리기 때문이다. 

 

https://dkswnkk.tistory.com/679