Hash와 HashMap
서비스를 개발하거나 알고리즘, 자료구조를 공부하면서 Map, Set 등의 자료구조를 자주 이용했었다. Map 이나 Set 자료구조를 사용하면 자료의 양이 엄청 많아도 검색하는데 O(1) 만큼의 시간복잡도를 가지게 된다. 이렇게 빠른 검색을 위해 Map, Set을 구현하려고 보면 HashMap, HashSet 이라는 구현체를 통해 생성했을 것이다. 처음에는 그냥 당연히 Map과 Set 을 사용하려면 이렇게 써야 한다고 생각했었다. 하지만 계속해서 쓰다 보니 앞에 Hash가 의미하는 것이 뭔지가 궁금해졌다. 그렇다면 이번 글에서는 Hash의 개념과 Map에 대하여 살펴보자.
해싱이란?
해싱은 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 찾아가는 검색 방식이다. 키값을 원소 위치로 변환하는 함수를 해시 함수(Hash Function)라 한다. 해시 함수에 의해 계산된 주소에 저장할 값을 저장한 표를 해시 테이블(Hash Table)이라 한다. 해시 테이블은 빠른 검색 속도를 제공하는데 이유는 내부적으로 버킷(배열)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 key 값에 해시 함수를 적용해 배열의 고유한 인덱스를 생성한 후 인덱스를 이용해 값을 저장한다. 실제 값이 저장되는 장소를 버킷이라 한다.
어떤 수업을 듣는 10명의 학생에게 자리를 배정한다고 생각해보자. 이때 자리가 딱 10자리가 있고 10명의 학생은 각각 다른 이름을 가지고 있다. 그리고 좌석 번호를 생성하는 번호 생성기에 이름을 입력하면 좌석 번호가 나오게 된다. 이때 번호 생성기가 해시 함수의 역할을 한다. 그리고 좌석 번호와 학생 정보를 기록한 테이블은 해시 테이블이 된다.
해시 충돌
앞서 번호 생성기를 통하여 10명의 학생을 각각 자리에 앉혔다. 10명의 학생을 각각의 자리에 안내할 수 있었던 것은 사실 번호 생성기의 성능이 좋아 겹치지 않았다. 하지만 수업의 퀄리티가 좋아져 학생의 수가 갑자기 엄청나게 늘어났다. 기존의 번호 생성기는 0~20까지의 번호밖에 만들지 못했는데 학생의 수가 어느덧 30명이 되었다. 이제 필연적으로 겹치는 번호가 생성될 수밖에 없다. 그럼 이미 좌석 배정이 받은 학생이 있는 자리에 새로운 학생을 배정하게 되는데 이러한 경우가 해시 충돌 상황이다.
이러한 해시 충돌을 해결하는 방법에는 크게 두 가지 방법이 있다.
- Open Addressing
- Separate Chaining
Open Addressing은 이미 자리에 누군가가 있으면 다른 곳으로 배정하는 방식이다. 다른 곳에 배정하는 방식에 따라 Linear Probing과 Quadratic Probing 등의 방법이 있다.
Separate Chaining은 해시 테이블의 구조를 변경하여 하나 이상의 키값을 저장할 수 있도록 하는 방법이다. 이때 주로 사용하는 자료구조로 연결 리스트를 사용한다.
HashMap 에서의 Separate Chaining
HashMap에서 사용하는 충돌기법 방식은 Separate Chaining이다. Java 8 이전에의 HashMap에서는 단순히 연결 리스트를 사용하였다. 하지만 Java 8 이후부터는 데이터의 개수가 많아지면 연결 리스트가 아닌 트리 자료구조를 사용한다. 정확히 말하자면 레드 블랙 트리 자료구조이다. 그렇다면 데이터의 개수가 많아진다는 기준점은 무엇일까?
하나의 해시 버킷에 8개의 키-값 쌍이 모이면 연결 리스트를 트리로 변경하게 된다. 또한 버킷의 데이터를 삭제하여 개수가 6개에 이르면 다시 연결 리스트로 변경한다. 그럼 왜 6과 7 또는 7과 8이 아닌 6과 8이 기준이겠냐는 의문이 생길 수 있다. 이유는 차이가 1일 경우 삽입/삭제가 반복되어 일어나면 불필요하게 트리와 연결 리스트로 변경하는 일이 발생하기 때문이다.
해시 버킷의 확장
앞서 버킷에 관해 설명했듯이 버킷은 결국 배열로 구성되어 있다. 우리가 HashMap을 구현할 때 따로 버킷의 개수를 지정 해주지 않았다면 기본값인 16으로 버킷의 개수가 지정된다. 해시 버킷의 개수가 일정 개수 이상이 되면 버킷의 개수를 2배로 늘리게 된다. 버킷을 늘리면 해시 충돌의 가능성도 낮아져 해시 충돌로 인한 문제를 해결할 수도 있다. 하지만 두 배로 증가할 때마다 새로운 Separate Chaining을 구성해야 하는 문제가 있다. 가장 좋은 것은 버킷의 개수를 예측할 수 있다면 지정하여 HashMap을 생성하는 것이다. 따라서 데이터의 개수가 예측 가능하다면 지정하여 생성자의 인자로 넣어주면 불필요한 Separate Chaining을 줄일 수 있다.
Load Factor
해시 버킷의 개수가 일정 개수 이상이 되면 버킷의 수를 두 배로 늘린다 했는데 그럼 일정 개수는 어떻게 정할까? HashMap 클래스에 들어가 load factor 부분을 살펴보면 0.75f이라고 설정된 것을 볼 수 있다.
이 의미는 데이터의 개수가 현재 버킷 개수의 0.75 즉 3/4 이 되었을 때 두 배로 확장한다는 뜻이다.
정리
이번 글을 통하여 Hash와 HashMap에 대하여 알아보았다. 프로그래밍을 하는 사람이라면 배열이나 리스트만큼 자주 쓰는 자료구조인 Map일 것이다. 하지만 그 어떤 방식으로 Map이 구현되어 있는지는 관심 있게 보지 않으 면 모르고 지나갔을 부분일 것 같다. HashMap은 해시 함수를 통하여 해시 테이블을 만들고 이를 기반으로 검색 시 빠른 속도를 낸다. 또한 해시 충돌을 방지하는 방법으로 open addressing과 separate chaining 방법이 있었다. 자바에서는 separate chaining을 이용하여 해시 충돌을 해결하였다.