Hash와 HashMap에 대한 이해

해시 개념은 컴퓨터 공부를 하다보면 흔히 등장하는 개념이다. 오늘은 자바의 HashMap을 공부하면서 해시와 자바의 HashMap 에 대해 정리해보고자 한다.

1. Hashing(해싱)이란?

Hash function(해시함수)을 이용해서 데이터를 HashTable(해시테이블)에 저장하고 검색하는 기법을 말한다. 해시함수는 데이터가 저장되어 있는 곳을 연산을 통해 빠르게 알려 주고 해시테이블은 내부적으로 배열을 사용하고 있어 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.

 

2. HashTable(해시테이블)

해시함수를 사용하여 변환한 값을 index(색인)으로 삼아 키(key)-데이터(value) 쌍을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array(연관배열)

 

파이썬의 dictionary, 루비의 Hash, 자바의 Map이 해시 테이블의 대표적인 예다.

 

해시함수를 사용하여 변환한 값을 해시값이라고하며, 해시테이블은 내부적으로 배열을 사용하여 데이터를 저장하는데 여기서 실제 값이 저장되는 장소를 bucket(버킷) 또는 slot(슬롯)이라고 한다.

 

위의 그림은 해시 함수의 동작원리를 보여주는 대표적인 그림이다. 예를 들어, Key-Value 값이 (“John Smith” , “521-1234”) 인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자.

먼저, 해시 함수를 통해 “John Smith”의 인덱스 값을 구해야 한다. 인덱스는 키값을 해시 테이블의 크기인 16으로 나눴을 때 나머지라고 할 수 있고 이를 수식으로 나타내면 index = hash_fucntion(”John Smith”) % 16 이다. 그리고 해당 index 값에 해당하는 곳(버킷)에 “521-1234” 를 저장한다.

 

3. Hash function(해시 함수)

해싱을 구현하는 과정에서 제일 중요한 것은 해시함수이며 Division Method가 위에서 설명한 대표적인 방식이다. 해당 방식은 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다. 즉, (index = 입력값(Key) % 테이블의 크기) 이며, 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.

 

4. Hash Collision(해시 충돌)

서로 다른 키에 대해 동일한 해시값이 나온다면 어떻게 해야 할까? 배열에 2가지 값을 넣을 수는 없다. 이와 같은 상황을 Hash Collision(해시 충돌) 이라고 하며 해결방법으로는 Separate Chaining(분리 연결법), Open Addressing(개방 주소법) 2가지가 있다. 자바의 HashMap 에서는 Separate Chaining 방식을 사용해 해시 충돌을 해결하고 있다.

4-1. Separate Chaining

체이닝이란 충돌이 발생했을 때 이를 동일한 버킷에 저장하는데 이를 연결리스트 형태로 저장하는 방법을 말한다. 위의 그림을 보면 John Smith 와 Sandra Dee 의 인덱스가 152로 충돌하게 된 경우이다. 이때 Sandra Dee 를 John Smith 다음에 연결함으로써 충돌을 처리하는 것을 볼 수 있다.

 

체이닝을 통해 해시테이블을 구현하면 삽입의 경우 연결리스트에 추가하만 하면 되기 때문에 시간복잡도가 상수시간인 O(1) 이 걸린다. 하지만 탐색과 삭제의 경우 최악일때 키 값의 개수인 K에 대해 O(K) 가 걸리게 된다.

 

** 참고 : Java 8(JEP 180 참조)에서 버킷에 8개 이상의 값이 포함되어 있으면 버킷 내부의 값이 저장된 데이터 구조가 목록에서 균형 트리로 변경되고 버킷에 6개 값만 남아 있으면 다시 목록으로 변경된다. 이렇게 하면 성능이 O(log n)로 향상된다.

 

5. 자바의 HashMap

HashMap은 Map 인터페이스를 구현하고 있는 대표적인 클래스이다. Map의 구조인 Key-Value쌍으로 구성되어 있다. Map의 대표적인 특징은 하나의 key는 정확히 하나의 value만 가질 수 있다는 것이다.

 

자바의 HashMap은 해싱을 구현한 컬렉션 클래스로 이외에도 HashSet, HashTable 등이 있다. HashTable은 컬렉션 프레임윅이 도입되면서 HashMap으로 대체되었으나 이전 소스와의 호환성 문제로 남겨 두고 있다.

 

둘의 차이점은 동기화 지원 여부에 있다. 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 해시테이블(HashTable)을 사용해야 하며, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시맵(HashMap)을 사용하면 된다.

 

HashMap의 source code 주석 내용을 살펴보며 HashMap에 대해 이해해보자.

 

1번째

• HashMap 클래스는 자바의 Map 인터페이스를 구현한 해시 테이블 기반의 자료 구조이다.
• 키(Key)-값(Value) 쌍을 저장하고 관리하며 Map 인터페이스에서 정의된 다양한 맵 연산을 제공한다.
• 키(key)나 값(value)으로 null을 사용할 수 있다.
• Hashtable 클래스와 대략적으로 비슷하다. 두 클래스 간의 차이는 동기화 여부와 , null 값 허용 여부에 있다.
• HashMap 클래스는 맵 내부의 순서에 대한 어떤 보장도 하지 않는다. 특히, 맵의 순서가 시간이 지남에 따라 일정하게 유지될 것을 보장하지 않는다.

2번째

• 기본적인 연산인 get과 put에 대해서 상수 시간(complexity) 성능을 제공한다.
• 상수 시간 성능이 해시 함수가 엘리먼트들을 적절하게 해시 버킷(buckets)에 분산시키는 경우에만 성립한다는 점을 강조한다. 만약 해시 함수가 엘리먼트를 고르게 분산시키지 못한다면 성능에 문제가 발생할 수 있다.
• 맵의 크기가 클수록 순회하는 데 더 많은 시간이 걸릴 수 있습니다.
• 만약 순회 성능이 중요하다면 초기 용량(initial capacity)을 너무 높게 설정하거나 로드 팩터(load factor)를 너무 낮게 설정하지 않는 것이 매우 중요하다. (초기 용량과 로드 팩터 개념은 3번째 주석에서 설명한다.)
• 초기 용량을 너무 높이면 메모리 사용량이 증가할 수 있고, 로드 팩터를 너무 낮게 설정하면 해시맵이 재조정(rehashing)되는 빈도가 높아져서 성능 저하를 초래할 수 있습니다.

3번째

• HashMap 인스턴스는 성능에 영향을 미치는 두 가지 매개변수, 초기용량과 로드 팩터를 가지고 있다.
• 초기 용량 : 해시 테이블 내에 버킷의 갯수, 즉 해시맵이 생성될 때 해시 테이블에 할당되는 초기 버킷의 수
• 로드 팩터 : 해시 테이블이 얼마나 채워질 때까지 기다릴지를 나타내는 지표
• 테이블 내 엔트리(키-값 쌍) 갯수 > (로드 팩터 * 현재 용량) 일때, 해시 테이블은 재해시된다. 이때 테이블의 용량이 대략 2배로 증가한다.

4번째

• 기본 로드 팩터인 0.75는 시간과 공간 비용 사이의 좋은 균형을 제공한다.
• 더 높은 로드 팩터 값은 메모리 사용량을 감소시키지만, 조회 비용을 증가시킨다.

5번째

• 만약 많은 매핑(키-값 쌍)을 HashMap 인스턴스에 저장해야 한다면, 초기 용량을 충분히 크게 설정하여 해시맵이 크기를 동적으로 조정하는 빈도를 줄일 수 있다.

6번째

• 이 구현체(HashMap 클래스)는 스레드 동기화를 제공하지 않음에 주의해야 한다. 여러 스레드가 동시에 해시 맵을 접근하고, 그 중 하나 이상의 스레드가 맵을 구조적으로(modify structurally) 수정하는 경우, 외부에서 반드시 스레드 동기화를 수행해야 한다.

아래 2가지만 더 보고 마무리하려고 한다.

hashCode() 함수

HashMap 에서는 Object 클래스에 정의된 hashCode()를 해시함수로 사용한다. Object 클래스에 정의된 hashCode() 는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체에 대해 hashCode() 를 호출한 결과가 서로 유일한 훌륭한 방법이다.

Key 의 불변성

HashMap 에서는 Key 값이 고유해야 하며, 이미 존재하는 키에 대한 값을 저장하면 기존의 값을 새로운 값으로 덮어쓴다. 이때 객체를 구별하기 위해 클래스를 정의할 때 equals() 와 hashcode() 를 오버라이딩한다.

 

참고

• java HashMAp source code 살펴보기 https://hoonzi-text.tistory.com/107
• [자료구조] 해시테이블이란? https://mangkyu.tistory.com/102
• [DS] 해시 테이블이란? https://baeharam.netlify.app/posts/data%20structure/hash-table
• [Java] HashMap 이란 무엇인가 ? https://devlog-wjdrbs96.tistory.com/241
• 자바의 정석(남궁성)