자바의 해시, 해시테이블

Posted Nov 17, 2023

By vectorch9 20 min read

자바의 hashCode()와 해시를 이용하는 HashMap 자료구조에 대해 찾아보고 정리해보자.

해시에 대해 설명하기 전에 eqauls()를 짧게 짚고 넘어가자.

equals

자바의 Object 클래스의 equals()는 아래와 같다.

  
public boolean equals(Object obj) {  
    return (this == obj);  
}

단순히 this == obj를 반환하여 참조값(주소)이 같은지 비교하는 메서드다.

자바 문서의 equals()에 대한 설명은 다음과 같다.

Indicates whether some other object is "equal to" this one.

The `equals` method implements an equivalence relation on non-null object references:

- It is _reflexive_: for any non-null reference value `x`, `x.equals(x)` should return `true`.
- It is _symmetric_: for any non-null reference values `x` and `y`, `x.equals(y)` should return `true` if and only if `y.equals(x)` returns `true`.
- It is _transitive_: for any non-null reference values `x`, `y`, and `z`, if `x.equals(y)` returns `true` and `y.equals(z)` returns `true`, then `x.equals(z)` should return `true`.
- It is _consistent_: for any non-null reference values `x` and `y`, multiple invocations of `x.equals(y)` consistently return `true` or consistently return `false`, provided no information used in `equals` comparisons on the objects is modified.
- For any non-null reference value `x`, `x.equals(null)` should return `false`.

An equivalence relation partitions the elements it operates on into _equivalence classes_; all the members of an equivalence class are equal to each other. Members of an equivalence class are substitutable for each other, at least for some purposes.

Implementation Requirements:

The `equals` method for class `Object` implements the most discriminating possible equivalence relation on objects; that is, for any non-null reference values `x` and `y`, this method returns `true` if and only if `x` and `y` refer to the same object (`x == y` has the value `true`). In other words, under the reference equality equivalence relation, each equivalence class only has a single element.

equals()는 동등성, Eqaulity을 비교하기 위한 메서드로 몇가지 성질을 만족하여야 한다. Object의 equals()는 위에서 살펴본대로 가장 분별력이 높은 == 연산을 통해 비교한다.

==은 인스턴스의 참조값을 직접 비교하는 연산으로 동일성, Identity을 비교한다. 다시말하면, Object의 eqauls() 메서드는 단 하나의 객체(자기자신)만을 동등하다고 판단한다.

동등성과 동일성은 차이가 있으며 동등성을 비교하고자 할 땐 eqauls()를 오버라이딩하여 작성한다. eqauls()를 재정의할 땐 핵심 필드의 값을 비교한다.

예를 들어 String의 equals()는 아래와 메서드를 이용하여 값을 비교한다.

  
public static boolean equals(byte[] value, byte[] other) {  
    if (value.length == other.length) {  
        for (int i = 0; i < value.length; i++) {  
            if (value[i] != other[i]) {  
                return false;  
            }  
        }  
        return true;  
    }  
    return false;  
}

이때, Primitive 타입인 경우엔 ==를 통해 값을 비교할 수 있다. 이는 실제 저장된 상수는 Runtime Constant Pool에 저장되고, 스택 프레임에서 해당 주소를 가리키고 있기 때문이다. 즉, 같은 값을 가지는 Primitive 타입은 항상 같은 주소를 가리킨다. 엄밀히 말하면 Primitive 타입도 참조값 비교지만, 값이 같다면 참조값도 항상 같으므로 동일한 결과를 낸다.

그렇다면 equals()는 항상 재정의해야할까? 그렇지 않다.

각 객체 인스턴스는 본질적으로 고유한 경우가 있다. 예를 들면, Thread는 같은 값을 갖더라도 동등하다고 생각하지 않는다. equals()는 위에서 살펴본 String과 같이 논리적 동등성을 비교하고 싶은 경우에만 재정의한다.

hashCode

equals() 메서드는 추가적으로 아래 사항을 명시한다.

It is generally necessary to override the `hashCode` method whenever this method is overridden, so as to maintain the general contract for the `hashCode` method, which states that equal objects must have equal hash codes.

hashcode()메서드는 객체의 주소 값을 해싱하여 해시코드를 만든다. hashcode() 메서드는 주소에 직접 접근하는 native 함수기 때문에 JNI에 의해 실행된다.

  
public native int hashCode();

equals()를 오버라이딩 하는 경우 hashcode()도 오버라이딩하라는 경고가 발생한다.

이는 자바가 equals()의 결과가 true라면 hashcode()의 결과도 같아야함을 권고하기 때문이다. 컬렉션을 사용한다면 문제가 생길 수 있으므로 주어지는 권고사항이다.컬렉션은 객체의 hashcode()가 같은 지 먼저 확인 후 같다면 equals()까지 호출하여 두번의 검증 과정을 거치도록 최적화되어있다.

이는 다시말하면 equals() 내에서 논리적 동등성 비교를 위해 사용한 필드만 hashCode()에서 사용해야 함을 의미한다. 만약 hashcode()를 오버라이드 한 경우 참조값을 이용한 원본 해시코드가 필요한 경우엔 identityHashCode()를 호출하여 얻을 수 있다.

해시도 지켜야만 하는 몇가지 성질이 존재한다.

동일한 객체에 대해 수행하였을 때 equals()내에 사용되는 객체의 상태가 변하지 않는한, 동일한 정수를 반환해야만 한다.
equals()를 통해 동등함이 확인되었다면 해시코드 또한 동일해야한다.
equals()가 다르다고 hashCode()가 반드시 다를 필요는 없다. 그러나 해시 테이블의 성능을 위해선 가능한 다른 것이 좋다.
- 이유를 모른다면 해시 충돌을 키워드로 검색해보길 바란다.

HashMap

hashCode()가 정의된 이유 중 하나인 HashMap 자료구조를 살펴보자. HashMap을 간단히 설명하면, Map의 구현체로 키의 해시 코드를 사용하여 키-값 쌍을 저장하고 조회한다. 내부적으론 배열을 통해 저장한다. HashMap의 기능 자체가 궁금하다면 공식 문서를 참고하자.

참고로 이때 배열의 각 칸을 버킷이라고 한다. 자바의 HashMap에선 Node라는 표현을 사용한다.

Hash function 자체가 궁금하다면 문서를 참조하자.

해시 충돌

자바의 해시는 int를 반환한다. 즉, 2^32개의 결과를 표현이 가능하다. String을 해싱한다고 생각해보자. 새상에 존재하는 모든 문자열을 2^32개로 함축할 수 있을까? 문자열이 2^32 + 1개만 존재하더라도 비둘기집의 원리에 의해 불가능함을 알 수 있다. (심지어 실제 문자열은 무한한 경우의 수를 가진다!)

이 처럼 서로 다른 입력을 해싱하더라도 같은 결과가 나올 가능성이 있으며 이를 해시 충돌, Hash Collision이라고 부른다.

해시 충돌을 해결하는 방법은 크게 두가지가 존재한다.

Seperate Chaining
- 각 버킷을 별도의 링크드 리스트로 관리한다. 충돌 발생 시 해당 자료 구조에 삽입하면 된다.
Open Addressing
- 해당 하는 버킷에 이미 데이터가 존재하는 경우, 다른 버킷에 데이터를 저장한다. 다른 버킷을 선정하는 여러 알고리즘이 존재한다.
- 조회 시엔 빈 버킷을 만나기 전까지 모든 버킷을 순차적으로 탐색해야 한다.
  - 삭제 연산 시에도 단순히 값을 삭제하는 것이 아닌, Deleted와 같은 추가적인 표시를 해주어야 한다.
- Linear Probing은 단순히 다음 버킷에 저장하는 방식이다.
- Quadratic Probing, Double Hashing Probing의 방식도 존재하며 Linear보다 더 나은 성능을 보인다.

두 방식 모두 최악의 시간복잡도는 O(N), N: HashMap에 속한 데이터의 수가 된다. N이 작다면 메모리 캐시 효율로 인해 Open Addressing 방식이 더 효율적이지만, N이 커질수록 장점이 상쇄된다. 또 Open Addressing은 데이터 삭제 시 번거로운 작업이 필요하다.

자바는 Seperating Chaining 방식을 이용하여 충돌을 해결한다. 자바의 HashMap의 버킷을 링크드리스트와 트리로 구현하여 평균 시간복잡도를 낮춘다.

HashMap은 아래의 상수를 내부적으로 보유한다.

  
static final int TREEIFY_THRESHOLD = 8;  
static final int UNTREEIFY_THRESHOLD = 6;

각 버킷내 데이터의 수가 8개를 넘어가면 링크드리스트를 트리로 전환하고, 6개 이하로 내려가면 트리를 링크드리스트로 전환한다.

왜 동일한 숫자가 아닌 8과 6일까? 데이터 1개가 계속 삽입-삭제가 반복된다면 7-> 8-> 7-> 8과 같은 상황에 성능이 저하될 수 있기 때문이다.

아래는 putVal() 메서드의 일부다.

  
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
               boolean evict) {
	Node<K,V> p;
	
	// ...
	
	Node<K,V> e; K k;  
	if (p.hash == hash &&  // 첫번째 노드 검사
	    ((k = p.key) == key || (key != null && key.equals(k))))  
	    e = p;  
	else if (p instanceof TreeNode) // 버킷이 트리인 경우
	    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  
	else {  // 버킷이 링크드리스트인 경우
	    for (int binCount = 0; ; ++binCount) {  
	        if ((e = p.next) == null) {  
	            p.next = newNode(hash, key, value, null);  
	            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
	                treeifyBin(tab, hash); // 기준을 넘으면 트리화 한다
	            break;  
	        }        if (e.hash == hash &&  
	            ((k = e.key) == key || (key != null && key.equals(k))))  
	            break;  
	        p = e;  
	    }
	}
}

참고로 TreeNode는 Node를 상속한 클래스로, 트리 자료구조를 이용하는 경우에 사용한다. HashMap 내부의 트리 구현은 레드블랙트리로, TreeMap과 유사하다.

메모리

이번엔 메모리를 고려해보자. HashMap은 배열을 통해 내부 노드를 저장한다. 해시의 결과인 int를 그대로 배열의 인덱스로 사용하려면 배열의 크기 또한 2^32여야한다. 각 버킷의 크기가 8B라면 2^32 * 8B약 34 GB가 된다.

너무 많은 메모리가 필요하므로, 자바는 배열의 크기를 더 작게 동적으로 유지한다. HashMap은 생성 시 initial capacity와 load factor를 지정할 수 있다. 각각 기본값은 16, 0.75다. capacity는 현재 배열의 크기로, 최대값은 2^30이다.

메모리의 크기를 줄인 것은 좋으나, 배열에 값이 찰 때마다 충돌이 더 많이 발생하기 때문에 해시맵의 성능이 떨어지게 된다. 해시 배열이 일정 수준 이상 찰 때 마다 capacity를 두배로 늘린다.

일정 수준은 threshold라는 변수로 표현되어 capacity * load factor의 값으로 계산된다. 실제 배열을 늘리는 resize() 메서드를 보자.

  
final Node<K,V>[] resize() {  
    Node<K,V>[] oldTab = table;  
	int oldCap = (oldTab == null) ? 0 : oldTab.length;  
	int oldThr = threshold;  
	int newCap, newThr = 0;

	if (oldCap > 0) {  
	    if (oldCap >= MAXIMUM_CAPACITY) { // 최대값 처리
	        threshold = Integer.MAX_VALUE;  
	        return oldTab;  
	    } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
	             oldCap >= DEFAULT_INITIAL_CAPACITY) // capacity는 두배로 증가하므로 threshold도 두배만 증가하면 됨
	        newThr = oldThr << 1; // double threshold  
	}else {  // 초기화
	    newCap = DEFAULT_INITIAL_CAPACITY;  
	    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}  
	threshold = newThr;
  
	Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
	table = newTab;
	
	// ... 데이터를 rehash하고 옮기는 과정
	
	return newTab;
}

메모를를 위해 배열의 크기를 줄였으니 각 인덱스에 해시 값을 어떻게 할당할까? 해시에선 주로 모듈러 연산을 사용한다. 배열의 크기가 capacity이므로 hashCode() % capacity의 연산을 통해 해당 값을 위치시킬 인덱스를 구할 수 있다.

이때 capacity는 항상 2의 제곱수로 유지된다. 모듈러 연산자의 값이 2의 제곱수인 경우엔 비트 연산으로 최적화할 수 있다. h % (2^n)의 결과는 h의 하위 n비트의 값과 같기 때문이다. 자바에서도 이점을 활용하여 아래와 같이 인덱스를 계산한다.

  
index = (n - 1) & hash; // n = 16 = 2^4 (10000) 라면 1을 빼면 1111로 치횐된다.

하지만 이처럼 하위 n개의 비트만 활용하는 방식은 해시 분포가 변질되어 충돌이 발생하기 쉬워진다. (Birthday Paradox를 떠올려보자.)

자바는 아래와 같은 추가적인 조치를 취해 모듈러 연산을 하더라도 해시의 분포가 균등하게 유지되도록 한다.

  
static final int hash(Object key) {  
    int h;  
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
}

그 외 자료구조

자바에 해시를 사용하는 자료구조는 HashTable도 존재한다. HashTable은 구버전에서 사용하던 자료구조다.

얼마나 오래전이냐면 컬렉션 프레임워크가 나오기도 전이다.

HashTable은 HashMap과 기능이 거의 유사하지만 위와 같은 해시 보조 함수를 지원하지 않아 성능상 느리다. 자바가 HashMap의 알고리즘은 지속적으로 개선하지만 HashTable은 그대로 유지되기 때문이다.

HashTable은 synchronized 키워드를 통해 동시성을 제어한다. 다시 말하면 모든 연산이 동시에 한 스레드만 실행이 가능하므로 성능이 더 낮아진다.

HashTable의 존재의의는 하위호환성으로만 두자.

HashMap 동시성 제어

HashMap은 동시성을 고려하지 않는데, 그럼 멀티스레드 환경에선 어떻게 처리해야할까? 두 가지 방법이 존재한다.

Collections.synchronizedMap(map)
ConcurrentHashMap

Collections.synchronizedMap(map)은 Map을 래핑해준다. 래핑된 맵은 동시성 제어를 통해 데이터 일관성을 보장한다. 읽기 쓰기 작업 모두 synchronized(mutex)를 통해 객체 수준의 락을 사용한다. 즉 HashTable의 사례와 동일하게 성능이 낮아진다.

ConcurrentHashMap은 이와 다르게 쓰기 작업 시에만 버킷 수준의 락을 사용한다. 읽기시에 락이 없으며 각 버킷별로 락을 관리하므로 위에 비해 성능이 뛰어나다. 직접 벤치마킹을 한 밸덩의 포스트 를 확인하자.

synchronizedMap은 null을 지원한다는 장점이 있다. ConcurrentHashMap는 키와 값 모두 null을 허용하지 않는다. synchronizedMap는 래핑 대상 객체에 따라 지원한다.

HashMap인 경우 null키와 값 모두 허용
TreeMap인 경우 null 값만 허용
참조
https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/HashMap.html
공식문서
https://d2.naver.com/helloworld/831311
https://www.baeldung.com/java-synchronizedmap-vs-concurrenthashmap

Java

Java DS

This post is licensed under CC BY 4.0 by the author.