[자료구조] 해싱, 해시 함수, 해시맵 이란?

이번 글에서는 해싱(hasing)에 대한 개념과 Java에서 사용하는 자료구조인 HashMap을 알아보겠습니다.

 

개념 (concepts)

해시 함수(hash function)란 데이터의 효율적인 관리를 목적으로 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시(hash) 또는 해시 코드(hash code)라고 합니다. 이렇게 매핑하는 과정을 해싱(hasing)이라고 합니다.

 

사실 앞에서 언급한 임의의 길이를 가진 데이터인 키(key)는 그 종류가 무한대에 가깝지만 해시 함수를 통해 매핑된 해시(hsah)는 정수형 데이터이기 때문에 그 값이 유한합니다. 이 말은 해싱을 하다 보면 서로 다른 키(key)가 같은 해시(hash)를 갖게 될 수 있다는 말과 같습니다. 이러한 현상을 충돌(collision)이라고 합니다.

 

이런 문제가 발생할 수 있음에도 해시 테이블을 사용하는 이유는 데이터를 효율적으로 관리할 수 있기 때문인데요, 해시 함수를 통해 매핑된 해시를 색인(Index)으로 활용하기 때문에 데이터에 대한 검색, 삽입, 제거 연산의 시간 복잡도가 O(1)이라는 확실한 장점이 있어서입니다.

 

 

충돌 (collision)

HashMap은 기본적으로 각 객체의 hashCode() 메서드가 반환하는 int 자료형의 값을 배열의 Index로 사용합니다. int 자료형은 32비트의 정수로 약 43억인데, HashMap은 메모리 절약을 위해서 그보다 작은 크기의 배열을 생성합니다. 

 

사용자가 배열의 크기를 지정하지 않으면 기본적으로 16의 크기(M)를 가진 배열을 생성하는데요, 객체의 해시 코드를 배열의 인덱스로 사용하기 위해 내부적으로 해시 코드와 배열의 크기를 나눈 나머지 값을 연산하여 사용합니다.

 

int index = Key.hashCode() % M;

해시를 사용하는 Java Map 구현체에서 저장/조회 할 배열 인덱스를 계산하는 방법

 

 

이 코드와 같은 방식을 사용하면, 서로 다른 해시 코드를 가지는 서로 다른 객체(Key)가 1/M의 확률로 같은 버킷을 할당받습니다. 이는 해시 함수가 얼마나 해시 코드를 중복 없이 골고루 분포될 수 있도록 구현되었는지에 관계없이 발생할 수 있는 또 다른 충돌(collision)입니다. 

 

하지만 이렇게 충돌이 발생하더라도 키-값 쌍 데이터를 잘 저장하고 조회할 수 있게 하는 두 가지 방법이 있는데요, 하나는 Open Addressing이고, 다른 하나는 Separate Chaining입니다.

 

출처 - https://d2.naver.com/helloworld/831311

open addressing 방식은 한 버킷에 하나의 노드만 들어갈 수 있습니다. 데이터를 삽입하려는 버킷이 이미 사용 중인 경우에 다른 버킷을 탐색해서 데이터를 저장 및 조회합니다. 객체의 해시 코드로 얻은 주소가 아니라 다른 주소에도 노드를 할당할 수 있기 때문에 open addressing이라는 이름이 붙은 것 같습니다. 

 

separate chaning 방식은 한 버킷에 여러 개의 노드가 들어갈 수 있고, Java의 HashMap에서 사용하고 있는 충돌 해결 방법입니다. Linked List 방식을 사용함으로써 버킷에 할당되어 있는 노드의 next 참조 변수에 다음 노드가 연결되어 있는 구조입니다. 노드(D)를 삽입하려는 버킷이 이미 사용 중인 경우에 Head에 있는 노드(C)를 D의 next 참조 변수에 할당하고, D를 버킷의 Head에 위치시킵니다. 

 

HashMap 내부 클래스인 Node의 Property

 

 

 

부하율 (load factor)

만약에 10개의 데이터를 해시 테이블에 저장한다고 할 때 버킷의 크기가 얼마나 되야 적당한지 생각해 보겠습니다.

 

해시 테이블에 버킷이 10개가 있다면 해시 함수의 성능이 좋다고 해도 한 두번의 충돌이 발생할 수 있습니다. 그렇다고 해서 버킷의 크기를 100개로 늘린다면, 저장할 데이터의 개수에 비해 버킷이 너무 크기 때문에 메모리 낭비가 될 수 있습니다. 좋은 해시 테이블은 메모리를 낭비하지 않으면서 데이터 개수와 버킷 크기 사이의 균형을 유지해야 합니다.

 

충돌을 조정하기 위해서 해시 테이블을 연구하는 사람들은 데이터가 7개 있을 때 버킷의 크기는 10이어야 한다고 규칙을 세웠습니다. 다시 말해서 데이터가 14개 있을 경우에는 버킷의 크기는 20이어야 합니다.

 

데이터와 버킷 간 이러한 비율을 부하율(load factor)이라 부르고, 위 규칙을 이 용어로 적용하면 이상적인 부하율은 0.7이 됩니다.  Java의 HashMap은 기본 부하율을 0.75로 적용하고 있습니다.

 

HashMap의 기본 부하율

 

HashMap은 부하율을 기준으로 배열의 크기가 부족하다고 판단되면 현재 배열의 두 배 크기의 배열을 새로 생성한다. 예를 들어, 버킷의 크기가 100인 HashMap이 있는데 데이터가 75개까지 저장이 되면 버킷이 200인 배열을 다시 만들어서 재할당 합니다.

 

데이터의 크기를 짐작할 수 있는 경우라면 내부적으로 배열을 재할당하는 시간을 줄이기 위해 부하율을 고려한 크기로 해시맵을 초기화해주는 것이 좋을 것 같습니다.

 

 

 

 

 

 

 

 

 

 

참고 사이트

• https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/
• https://d2.naver.com/helloworld/831311