[자료구조] 해시(Hash), 자바에서의 해시 충돌

Hash란?

입력 데이터를 고정된 값으로 변환한 값이다. 해시 값이라고도 부른다.

해시 값은 해시함수(hash function)에 의해서 얻게 된다.

아래의 그림과 같은 방식으로 변환이 된다.

이렇게 정수로 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하거나 검색할 때 활용된다.

 

 해시 함수(Hash Function)란

임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수

위에서 언급했듯이 해시 함수(Hash function)는 입력받은 데이터를 해시 값으로 출력시키는 알고리즘을 말한다.

 

 해시 테이블(Hash Table)란

배열과 해시 함수를 사용해서 map을 구현한 자료구조이다.

일반적으로 상수시간에 접근하기 때문에 빠르다. 

 

해싱(Hashing)이란?

해싱은 해시 함수에서 해시를 출력하고, 해시 테이블에 저장하는 과정까지의 행위를 말한다

그림으로 설명하면 다음과 같다 

 

아래의 예시로 추가설명을 하자면 put값을 해시 함수가 일정한 정수로 바꿔준 후 , 

테이블의 크기만큼의 모듈러 연산을 통해 나머지로 해당 인덱스에 저장하게 된다.

 

해시 예시)

이전에 다룬 data class의 hashCode()를 디컴파일 해보면 다음과 같이 해시값을 구성하게 된다.

public int hashCode() {
   int result = this.name.hashCode();
   result = result * 31 + Integer.hashCode(this.age);
   return result;
}

 

다음과 같은 정수값이 나온다.

 

이 정수를 모듈러 연산을 통해 해시 테이블에 저장하게 되는 것이다!

---

해시 충돌(Hash Collision) 이란?

상기한 설명과같이 모듈러 연산을 하면, 인덱스가 겹치는 경우가 발생할 수 있다.

서로 다른 두개의 입력데이터가 인덱스 2를 가리키게 된다면, 어떻게 해결해야할까?

 

충돌 해결법 1. Separate Chaining

데이터를 삽입하다 해시충돌이 발생한다면, 연결 리스트를 활용해 데이터들을 연결하는 방식이다.

그림과 같이 같은 인덱스에 할당되게 된다면 연결 리스트를 통해서 데이터를 연결해준다!

연결리스트로 늘려가기에, 데이터의 주소값은 바뀌지 않는다.

충돌 해결법 2. Open Addressing

충돌시 같은 인덱스에 두지않고, 다른 비어있는 인덱스에 충돌된 데이터를 저장하는 방식이다.

대표적으로 다음과 같은 방식이 있다.

 

- Linear Probing (선형조사)

현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.

 

- Quadratic Probing

해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.

 

- Double Hashing Probing

 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

 

추가적으로, Open Addressing에서 데이터 삭제 시, 삭제된 공간은 Dummy Space로 활용된다. 더미를 통해서 다른곳에 배치된 데이터들을 추적할 수 있기 때문이다. 따라서 Hash Table을 재정리 해주는 작업이 필요하다.

---

해시테이블(HashTable) 시간복잡도

평균: O(1) - 각각의 Key값은 해시함수에 의해 고유한 index를 가지므로 데이터에 바로 접근

최악: O(N) - 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로

---

 

자바에서의 해시

자바에서는 Separate Chaining으로 해시 충돌을 관리한다고 한다.

 

해시를 학습 후  자바에서는 어떻게 세세하게 구현되어있는지 궁금하여

HashMap의 내부코드를 살펴보며 확인하였다.

기본 용량은 1<<4 인 16으로 설정되어 있었다.

맥시멈은 1<<30인 2의 30제곱으로 설정되어 있었다. (약 10억 7천만)

 

 

해시테이블이 75%만큼 찼을 때, 테이블 크기를 2배로 늘리도록 설정되어있었다.

 

 

 

하나의 버킷(bin)에 들어가는 노드 개수가 8개 이상일때 , 연결 리스트(linked list)에서 트리(tree)로 전환된다.

데이터를 삭제하여 개수가 6개에 이르면 다시 연결 리스트로 변경이 된다.

 

Q. 왜 트리로 변경이 될까 ?

A. 연결 리스트를 사용했을 때는 조회에 대한 시간복잡도가 O(N/M)을 보여줬지만 트리를 사용하게 되면 O(log N/M)의 복잡도를 가지게 되기 떄문이다.

• N: HashMap에 저장된 전체 요소의 개수를 의미.
• M: HashMap의 버킷(bucket)의 개수를 의미합니다.
• 연결 리스트를 사용하면 한 버킷 안에서 탐색할 때 시간 복잡도가 해당 리스트의 길이에 비례하므로, 평균적으로 탐색 시간은 O(N/M)이란 뜻.

Q. 무슨 트리를 사용할까? 

A. 레드 블랙 트리를 사용한다. 이후에 작성할 트리 관련 글에서 다루도록 하겠다.

 

Q. 왜 8과 6으로 2개의 차이를 두었을까? 

만약 차이가 1이라면 어떤 한 키-값 쌍이 반복되어 삽입/삭제되는 경우, 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문이다.

---

HashMap이 트리화(treeify) 작업을 수행하기 위한 최소 테이블 용량이다.

테이블 크기가 64보다 작으면 트리화 대신 테이블 크기를 늘리는 작업이 우선된다.

이를 통해 작은 테이블에서는 불필요한 트리화를 방지할 수 있다.

 

 

 

 

참고 링크

https://kang-james.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9CHASH-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0

[자료구조] 해시(HASH) 알아보기

https://www.youtube.com/watch?v=ZBu_slSH5Sk&t

 

https://dkswnkk.tistory.com/679

해시 자료구조와, 해시 충돌 그리고 Java의 HashMap 동작 방법