Hash에 대해서 알아보자

✅ 아래 내용들에 대해서 알아보자

- 해싱(Hashing)이란
- 해쉬 함수
- 해시 테이블
- 해시 값 충돌 해결 방법
- 자바에서 충돌 해결 방법

 

해싱이란

해싱이란 임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 길이의 데이터로 변환하는 작업을 말한다.

해싱 과정

 

위의 그림처럼 key 값들을 해쉬 알고리즘(hash functio)을 통해 해싱을 하여 그 값들을 해시값, 해시 코드라고 하는데

이 값들은 해시 테이블이라는 자료구조에 사용되며 매우 빠른 데이터 검색을 위해 사용되는 자료구조이다.

 

 

해시 함수

해시 함수는 암호학적/비 암호학적 해쉬함수로 구분된다.

암호학적 해시함수는 MD5, SHA계열 해시함수가 있으며, 비암호학적 해시함수로는 CRC32등이 있다.

 

간단한 해시 함수의 예로 input 값을 받아 10으로 나눈 나머지를 반환하는 함수가 있다고 가정한다.

ex) 22 % 10=2 , 31 % 10=1 , 54 %10=4..

 

해싱 과정을 통해 나온 값들이 해시 테이블의 색인 값이 되어 사용된다.

하지만 해시 함수를 최적화를 하여도 입력값(input)이 달라도 같은 해시값이 나오는 경우가 발생하는데 이러한 현상을 

"해시 충돌(hash Collision)"이라고 하며 충돌이 적은 해시 함수가 좋은 해시 함수라고 한다

 

 

해시 테이블

해시 테이블이란 해시함수를 사용하여 변환한 값(해시 값)을 색인으로 삼아 키와 데이터를 저장하는 자료구조를 말한다.

 

해쉬 테이블에는 버킷이라는 자료에 데이터를 저장하는데 버킷에는 키와 데이터를 저장되어 있으며 hashing을 통해 나온 해시값을 버킷의 주소 값으로 활용하여 해당 버킷에 접근하여 실제 저장되어 있는 데이터를 조회할 수 있다.

 

해시 테이블에도 해시값 충돌 문제가 발생하는데, 적재율(Load Factor)에 대해서 먼저 이해해 보도록 하자.

 

적재율이란 해시 테이블의 크기 대비, 키의 개수를 말한다. 즉 키의 개수 K, 해시 테이블의 크기 N이라고 할 때 적재율은 K/N이다. 만약 충돌이 발생하지 않다고 할 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)에 수행되지만 충돌이 발생할 경우 최악의 O(K)만큼 걸리게 된다. 

 

따라서, 충돌을 최대한 줄여서 연산 속도를 빠르게 하는 것이 해시 테이블의 핵심인데.. 결국 해시값 충돌을 적게 해주는 해시 알고리즘이 가장 중요한 요소이다.

 

 

해시 충돌 해결법

충돌 해결법에는 2가지 방법이 있다. 각각에 대해서 알아보자

 

1. Chaning 방법

충돌이 발생했을 때 동일한 버킷에 저장하는 방법을 체이닝 방법이라고 한다.

아래 그림처럼 152번 버킷에 충돌이 발생하고 있는데 (John Smith, Sandra Dee 해시값 충돌) 이러한 데이터를 연결 리스트 형태로 저장하여 해결하는 방식이다.

 

그런데 연결 리스트 방식으로 데이터를 저장하게 된다면 데이터 탐색 시 해당 버킷에 값의 개수 K에 대해 O(K) 만큼 걸리게 돼서 기존 해시 테이블의 탐색 속도의 의도를 벗어나게 되는데.. 이러한 문제를 자바에서는 해결하는 방법이 따로 존재한다.(추후 설명하겠음)

 

2. Open Addressing 방법

해시함수로 얻은 해시값에 따라 키와 데이터를 저장하지만 동일한 주소에 다른 데이터가 있을 경우 다른 주소로 이용할 수 있게 하는 방법이다. 

 

아래 그림을 보면 John Smith과 Sandra Dee 해시값이 충돌하는데 다음 비어있는 버켓에다가 데이터를 저장하는 구조이다

 

 

자바 해시 충돌 해결법

자바에서는 HashMap과 HashTable이라는  Map인터페이스를 상속받은 구현체 자료구조를 제공하는데

내부적으로 HashTable 구조를 가지게 되므로 결국 해시 충돌 문제가 발생하게 된다.

 

자바에서는 충돌 해결을 위해 chaning 방식을 사용하고 있는데 결국 chaining 방식은 충돌로 인해 해당 버킷에 데이터가 많아질수록 탐색 속도가 느려지는 단점이 발생하게 된다.

 

java8에서는 이러한 문제를 해결하기 위해 충돌된 키-값 쌍의 데이터가 8개가 모이면 링크드 리스트 -> 트리로 변경하게 된다.

 

하지만 트리의 특성상 트리 순회 시 판단 기준이 대소에 대한 구분이 있어야 하는데 이를 자바 8에서는 레드 블랙 트리라는 것을 적용시켰다.(참조)

 

따라서 트리 자료구조를 활용하여 탐색 속도의 시간을 줄여 탐색 속도가 느려지는 단점을 해결하게 된다!

 

---

참고자료

• https://baeharam.netlify.app/posts/data%20structure/hash-table
• https://namu.wiki/w/%ED%95%B4%EC%8B%9C
• https://odol87.tistory.com/4