Hash
임의의 크기를 가지는 데이터(문자, 파일 등)를 해시 함수에 입력하게 되면 고정된 크기의 데이터를 출력하게 되는데 이를 Hash(또는 해시값, 해시코드)라고 한다.
해시 함수는 알고리즘을 이용해서 입력받은 키 값으로 키 값의 크기와 상관없이 해시를 만들어 준다.
해시 함수는 같은 입력값에 대해서 같은 출력값을 보장한다.
(입력값에 대한 무결성을 보장한다고 한다.)
해시 값을 이용해서 키 값을 찾는 것은 불가능하여 일방향성을 갖는다고 얘기한다.
Hash Table
해시 테이블은 이러한 해시 함수를 이용해 키에 대한 해시 코드를 반환받아 해시 코드를 통해 배열(bucket)의 인덱스로 환산해서 데이터의 접근하는 방식의 자료구조이다.
(Java에서는 HashTable, HashMap등을 통해 해당 자료구조를 사용할 수 있다.)
해시 테이블의 필수 조건은 고정된 크기의 배열을 선언하는 것이다.
일반적으로 테이블의 크기와 상관없이 키를 통해 상수 시간으로 빠르게 데이터에 접근이 가능하다.
인덱스는 해시 코드와 배열의 크기를 나머지 연산을 하여 환산한다.
HashCode % 배열의 크기
환산한 인덱스를 통해 배열에 데이터를 저장하게 된다.
해시 충돌 (Hash Collision)
나머지 연산을 통해 인덱스를 환산할 때 서로 다른 키더라도 같은 인덱스를 환산하는 경우가 발생한다.
이를 해시 충돌이라고 한다.
해시 충돌은 2가지 경우에 해당한다.
1. 서로 다른 키가 같은 해시 코드를 반환한다.
2. 키와 해시 코드가 서로 다르지만 같은 인덱스를 환산한다.
이와 같은 해시 충돌에 대한 해결 방법으로는 2가지 방법이 있다.
분리 연결법 (Separate Chaining)
배열에 LinkedList를 사용하여 동일한 인덱스를 반환할 경우 List에 추가하는 방식을 사용하여 해시 충돌을 해결할 수 있다.
단, 동일한 인덱스에 너무 많은 데이터가 저장된다면 List를 탐색해야 하기 때문에 성능이 저하될 수 있다.
개방 주소법(Open Addressing)
선형 조사법 (Linear Probing)
해시 충돌이 발생한 배열 방에 다음 비어있는 배열방으로 데이터를 저장하는 방식이다.
배열의 경계를 넘어갈 경우 맨 앞으로 넘어가게 된다.
만약 비어있는 배열방이 없는 경우 빈 배열방을 탐색하는 시간이 늘어나게 된다.
이차원 조사법 (Quadratic Probing)
선형 조사법의 단점을 보완한 방법이 이차원 조사법이다.
선형 조사법에서는 하나씩 배열방을 탐색했다면 이차원 조사법은 제곱으로 빈 배열방을 탐색한다.
특정 영역에 데이터가 몰려도 그 영역을 빠르게 벗어날 수 있는 장점이 있으나 동일한 인덱스를 환산할 경우 탐색해왔던 경로를 그대로 탐색하여 빈 배열방을 찾게 되는 단점이 있다.
더블 해싱 (Double Hashing)
두 개의 해시 함수를 사용하는 방식이다.
인덱스를 반환하여 해시 충돌이 발생하면 다른 해시 함수를 통해 이동할 폭을 얻는다.
해시 함수를 두번 사용하다보니 이동 폭이 같을 확률이 매우 적어 서로 다른 보폭으로 빈 배열 방을 탐색하게 된다.
해시 테이블에서 데이터를 삭제할 때
해시 테이블에서 데이터를 삭제할 때 분리 연결법을 사용할 경우 LinkedList에서 포인터 값을 수정하여 데이터를 제거하거나 추가할 수 있다. 그러나 개방 주소법의 경우 해시 충돌이 발생하게 되면 빈 배열방에 데이터를 저장하게 되는데 기존 인덱스에 저장된 데이터가 삭제될 경우 해당 배열방에 더미 데이터를 통해서 데이터가 지워졌다는 내용을 남기거나 빈 배열방에 저장한 데이터를 다시 기존 배열방에 옮겨주어야 하는 작업이 발생하게 된다.
즉, 데이터 삭제시 분리 연결법이 개방 주소법 보다 성능상 이점을 가지고 있다.
Java에서의 Hash
Java에서는 HashTable과 HashMap을 통해 해시 테이블 자료구조를 제공하고 있다.
HashTable은 Java 1.0에서 추가된 자료구조로 동시성을 보장하나 구현의 거의 변화가 없다.
반면 HashMap의 경우에는 지속적으로 개선되고 있으니 되도록 HashMap을 사용하는 것을 권장한다.
(동시성 문제의 경우 java.util.concurrent 패키지의 라이브러리를 사용하면 된다.)
Java의 해시 충돌 해결 방법
Java는 분리 연결법 (Separate Chaining)을 사용하여 해시 충돌을 해결하고 있다.
단순히 LinkedList를 사용하는 것이 아니라 레드-블랙 트리도 혼용된 방식으로 사용하고 있다.
Java 8부터 해당 방식을 사용하게 되었는데 상수 형태로 기준을 정하게 된다.
동일 버킷에 데이터가 8개가 넘게 되면 LinkedList대신 레드-블랙 트리로 자료구조를 변경한다.
그러다 데이터가 6개가 되면 다시 LinkedList로 자료구조를 변경한다.
2라는 버퍼를 둔 이유는 1개 차이로 데이터의 삽입/삭제가 빈번하게 발생할 경우 불필요한 자료구조 변경으로 인해 성능 저하를 막기 위함이다.
상기에 기술하였듯이 주소 개방법이 데이터 삭제에 있어서 처리가 효율적이지 않기 때문에 Java에서는 분리 연결법을 채택하게 되었다.
버킷에 저장된 데이터가 일정 개수 이상으로 많아지면 일반적으로 주소 개방법이 분리 연결법보다 느리게 되는데 주소 개방법의 경우 버킷을 채운 밀도가 높아질 수록 Worst Case 발생 빈도가 높아지기 때문이다.
주소 개방법의 경우 보조 해시 함수를 통해서 해시 충돌이 발생하지 않도록 조정한다면 Worst Case가 발생하는 것을 줄일 수 있다.
Hash Table Resizing
배열(버킷)에 데이터가 일정 수준 차이게 되면 크기를 늘려줘야 한다.
Java에서 HashMap의 경우 전체 버킷 크기(capacity)가 75%가 차게 되면 버킷의 크기를 2배 늘려주게 된다.
여기서 75%라는 수치를 로드 팩터라고 하는데 HashMap, HashSet등 생성자를 통해 설정해줄 수 있다.
이때 기존 버킷에 저장된 데이터들은 늘어난 버킷 사이즈를 통해 해시 코드와 나머지 연산을 하여 다시 인덱스를 환산해 데이터를 저장하게 된다.
Java에서의 HashMap Resizing
상기에 기술하였듯이 Java에서는 버킷을 resizing할 때 항상 2배로 늘려주게 된다.
이말은 즉, 해시코드와 버킷 갯수를 나머지 연산 할때 해시 코드의 하위 x개의 비트만 사용하게 된다는 말이다.
해시 함수가 32비트 영역을 고르게 사용하도록 만들었다고 해도 해시 값을 2의 승수로 나누면 해시 충돌이 쉽게 발생하게 된다.
이러한 이유 때문에 Java에서는 보조 해시 함수를 사용하게 된다.
보조 해시 함수
보조 해시 함수는 객체 해시 코드의 상위 16비트 값을 해시코드와 XOR 연산을 해주는 것이다.
보조 해시 함수는 Java 1.4에 등장하여 Java 5 ~ Java 7까지 같은 방식을 사용하다가 Java 8부터 이전 버전에서 사용하던 것보다 단순한 새로운 방식의 보조 해시 함수를 사용한다.
그 이유는 Java 8부터 버킷의 데이터가 많을 경우 레드-블랙 트리를 사용하기 때문에 성능 문제가 완화된 것과 해시 함수 자체가 균등 분포가 잘되게 만들어져 이전 버전에 사용하던 방식이 효과가 크지 않기 때문이다.
인덱스를 반환할 때 HashCode % 버킷 개수 로 연산하는 것이 맞지만 버킷의 개수가 2의 제곱으로 증가할 때는 해시 코드의 하위 x개의 비트만 사용하는 것과 값이 같기 때문에 나머지 연산 대신 HashCode & (버킷의 개수 - 1) 연산을 사용하는 것이 성능상 이점이 있다.
Java에서는 보조 해시 함수를 통해 hashcode를 생성한 이후에 HashCode & (버킷의 개수 - 1) 연산을 하게 된다.
Java에서 Hash를 많이 사용하는 이유
- Java는 객체지향 언어이기 때문에 단순히 배열에 데이터를 저장하기 보다는 key-value 구조로 다루는 일이 많으며, 이때 가장 직관적인 자료구조가 Map이다.
- Hash를 사용하게 되면 데이터의 검색, 삽입, 삭제 속도가 빠르기 때문에 HashMap을 자주 사용하게 된다.
- Java의 컬렉션 프레임워크가 Hash 기반 구조를 기본으로 제공한다.
- Java의 모든 객체의 부모는 Object로 hashCode()와 equals() 메서드를 제공한다.
- 이런 구조 덕분에 Java에서는 Hash 관련 자료구조를 범용적으로 사용할 수 있다.
- C나 C++처럼 해시 함수를 따로 만들어주지 않아도 된다.
- Java는 해시 기반 자료 구조를 계속해서 튜닝하여 성능 최적화를 해왔다.
참고
'Study > Java' 카테고리의 다른 글
| [Java] 메모리 구조로 알아보는 JVM (0) | 2025.04.04 |
|---|
