Hash, HashTable, HashMap

March 7th, 2021

Hashing

해싱은 데이터를 다루기 위한 하나의 기법으로, 효율적인 리소스로 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 때 맵핑 전 원래 데이터를 키(key), 매핑 후 데이터의 값을 해쉬 값(hash value)라고 하며 매핑하는 과정을 해싱(hashing)이라고 한다.
보통 해싱을 할 때, 데이터의 키 값이 해쉬 값보다 많은 경우가 대부분이기 때문에(many-to-one) 해시함수가 서로 다른 두 개의 키에 대해 동일한 해쉬 값을 내는 해쉬충돌(collision)이 발생한다.

해시테이블의 장점

  • 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
    • 무한에 가까운 데이터(키)를 유한한 개수의 해시 값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있다.
  • 해싱함수를 이용하여 빠르게 검색/삽입/삭제를 할 수 있다.(삽입/삭제시 해당 데이터를 지워도 다른 데이터를 이동할 필요가 없기 때문)
  • 키와 해시값이 연관성이 없어 보안에도 쓰인다.

해시테이블의 단점

  • 해시 충돌이 발생할 수 있다.
  • 공간 복잡도가 커진다.
  • 순서가 있는 배열에는 어울리지 않는다.
  • 해시 함수에 따라 성능이 좌지우지 된다.

해시 테이블

해시함수를 이용하여 키 값을 해쉬 값으로 매핑하고, 이 해쉬 값을 index삼아 데이터의 값(value)을 키와 함께 저장하는 구조를 해시테이블(hash table)이라고 한다. 이 때, 데이터가 저장되는 곳을 버킷(bucket) 혹은 슬롯(slot)이라고 한다.

해시 충돌을 해결하는 방법

체이닝(Chaining)

한 버킷당 들어갈 수 있는 엔트리의 수를 제한을 두지 않는 방법. 해당 버킷에 데이터가 존재 한다면, 체인처럼 노드를 추가하여 다음 노드를 가르키는 방식으로 구현(연결리스트)한다.

  • 장점 :
    • 연결리스트만 사용하면 된다. 즉, 개방 주소법에 비해 복잡한 계산식을 사용할 일요가 없다.
    • 해시테이블이 채워질 수록, Lookup 저하가 Linear하게 발생한다.
  • 단점 :
    • 연결리스트를 통해 데이터를 무제한으로 추가하기에, 메모리 문제를 야기할 수 있다.(또한 외부저장 공간을 사용해야 한다)
    • 데이터가 균등하게 나뉘어지지 않을 경우 비효율적이다.

개방 주소법(Open Addressing)

한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시 테이블이다. 해당 버킷이 이미 사용중인 경우 다른 해시 버킷에 해다아 데이터를 삽입하는 방식이다.

개방 주소법의 대표적인 3가지 방법

  • 선형 탐색(Linear Probing) : 해시 충돌시 다음 버킷, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
  • 제곱 탐색(Quadratic Probing) : 해시 충돌시 제곱만큼 거너뛰 버킷에 데이터를 삽입한다.(1,4,9,16…)

  • 이중 해시(Double Hashing) : 해시 충돌시 다른 해시함수를 한 번 더 적용한 결과를 이용한다.

  • 장점:
    • 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장 공간도 필요없다.
    • 삽입, 삭제시 오버헤드가 적다.
    • 저장할 데이터가 적을 때 유리하다.
    • 연속된 공간에 데이터를 저장하기 때문에 Seperate Chaining에 비해 캐시 효율이 높다.
  • 단점 :
    • 비어있는 공간을 찾는 알고리즘 성능에 따라 해시테이블 성능이 바뀐다.

리사이징

체이닝 기법의 경우, 버킷이 일정 수준으로 차버리면 각 버킷에 연결되어있는 List의 길이가 늘어나 검색 성능이 떨어져 버킷 개수를 늘려주어야 한다. 개방 주소법은, 고정 크기 배열을 사용하기 때문에 데이터를 더 넣기 위해서는 배열을 확장해야 한다. 이를 리사이징(Resizing)이라고 한다.
보통 두 배로 확장으 해주는데, 확장하는 임계점은 현재 데이터 개수가 해시 버킷 개수의 75%가 될 때이다. 리사이징은 더 큰 버킷을 가지는 array를 새로 만든 후, 다시 새로운 Array에 hash를 계산해 복사해주어야 한다.

해시함수

데이터의 키 값을 고르게 버킷에 분포시키기 위해서는, 적절한 해시함수를 적용해야 한다.

division method

나눗셈법은 간단하면서도 빠른 연산이 가능한 해시함수이다. 숫자로 된 키를 해시테이블 크기 m으로 나눈 나머지를 해시값으로 반환한다. m은 보통 소수를 쓴다.

multiplication method

숫자로 된 키가 k이고 A는 0과 1 사이의 실수일 때, 아래와 같은 곱셈법을 이용한다. m이 얼마가 되든 중요하지 않으며, 보통 2의 제곱수로 정한다고 한다. 위 division method보다는 더 느리다.

universal hashing

다수의 해시함수를 만들고, 이 해시함수의 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법이다. H에서 무작위로 뽑은 해쉬함수가 주어뎠을 때, 임의의 키값을 임의의 해쉬값에 매핑할 확률을 1/m로 만드는 것이 목적이다.

HashMap과 HashTable 그리고 ConcurrentHashMap

HashMap과 HashTable은 키에 대한 해시 값을 사용하여 값을 저장하고 조회하여, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array이다. 내부 코드를 타고타고 보면 알 수 있겠지만 둘의 사용법은 거의 동일하다.

HashMap

  • Map 인터페이스의 구현체이다.
  • null값의 key와 value를 허용한다.
  • synchronized 키워드가 없어 동기화를 보장하지 못한다. 그 대신, 검색 속도는 상당히 빠르다.
  • Fail-Fast Iterator를 이용해 저장된 요소를 반환한다.
    • 순차적 접근이 모두 끝나기 전, 객체에 변경이 일어날 경우 순차적 접근이 실패하며 ConcurrentModificationException예외를 반환한다.
  • 보조 해시 함수를 사용하기 때문에 HashTable과 비교했을때 해시 충돌이 덜 발생할 수 있다.
    • 키의 해시 값을 변형하여 해시 충돌 가능성을 줄인다. Java 5 ~ Java 7까지 동일한 방식이며 Java 8부터는 훨씬 간결해졌다.
      • 최근의 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아, Java 7까지 사용했던 보조 해시 함수의 효과가 크지 않다.
      • Java 8은 해시 충돌이 많이 발생하면 링크드리스트 대신 트리를 이용하여 성능문제가 많이 완화되었다.
  • Seperate Chaining 방법으로 구현했다.
    • 이전에는 단순히 LinkedList를 이용하여 구현하였지만, Java 8 부터는 데이터의 개수가 많아지면 LinkedList대신 Tree를 이용한다.(하나의 해시 버킷에 8개의 키-값 쌍이 모이면 연결리스트를 트리로 변경, 반대로 6개일경우 트리에서 링크드리스트로 변경한다)
      • 이는 트리가 링크드 리스트보다 메모리 사용량이 많기 때문이다.
      • 8과 6으로 2 이상의 차이를 둔 것은, 만약 차이가 1이라면 어떤 한 키-값 쌍이 반곡되어 삽입/삭제되는 경우 불필요하게 트리와 링크드리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문이다.

HashTable

  • HashTable의 모든 data 변경 메서드는 synchronized로 선언되어있어, 메서드 호출 전 동기화 락을 통해 data의 무결성을 보장해준다. => 속도가 느리다.
    • 해당 HashTable 객체를 참조하는 쓰레드의 개수가 많아질수록 락을 획득하기 위해 대기하는 시간이 길어져 성능이 급격히 나빠진다(Collections.synchronizedMap 객체도 마찬가지이다)
  • key, value에 null값을 허용하지 않는다.
  • 주로 하위버전 호환성을 위해 사용한다.
  • Enumeration을 이용해 저장된 요소를 접근한다.
    • 컬렉션 프레임워크 이전에 사용되었던 인터페이스로, vector 및 hashtable의 객체에서 사용된다. new 연산자로 생성이 불가하고, vector를 이용해 생성한다.
    • 순차적 접근시 콜렉션 객체에 변경이 일어나도 이를 무시하고 끝까지 동작한다.

ConcurrentHashMap

  • 멀티스레드 환경에서 HashMap의 문제점을 보완하기 위해, 동기화 처리를 지원하는 Map 인터페이스 구현체이다.
    • 내부적으로 여러 개의 세그먼트를 두고, 각 세그먼트마다 락을 주는 방식이다. 여러 쓰레드에 ConcurrentHashMap 객체에 동시에 데이터를 삭제,참조하더라도 그 데이터가 다른 세그먼트에 위치하면 서로 락을 얻기 위해 경쟁하지 않는다.
  • 하지만 HashMap과 다르게 key, value 값에 null을 허용하지 않는다.
  • HashMap과 비교했을때 putIfAbsent라는 메서드가 추가되었다.
  • Fail-Safe Iterator를 이용해 저장된 요소를 반환한다.
    • Map의 복사본을 참조하는 Iterator를 반환하며, 다시 반환받은 시점에 Map에 수정이 있을 경우 해당 Iterator는 반영되지 않는다. 즉, 기존 Collection을 수정하더라도 오류가 발생되지 않고 계속 진행한다.

참고 자료 :

  1. 해싱, 해시함수, 해시테이블
  2. Java HashMap은 어떻게 동작하는가?
  3. ConcurrentHashMap vs. HashTable

oksusutea's blog

꾸준히 기록하려고 만든 블로그