HashMap 동작과정

해시 테이블은 key-value로 데이터를 저장하는 자료구조로 데이터를 빠르게 검색할 수 있는 자료구조이다.

해시 테이블은 내부적으로 배열(버킷)을 사용하여 데이터를 저장한다.

해시테이블의 각각의 key 값에 해시함수를 적용해 배열의 고유한 index를 생성하고 이 index를 활용해서 값을 저장하거나 검색한다. 여기서 실제 값이 저장되는 장소를 버킷이라고 한다.

해시테이블은 해시함수를 사용하여 데이터의 키를 해시값으로 변환한다. 변환한 해시값을 버킷 인덱스로 사용하여 해당 버킷에 데이터를 저장한다. 해시함수가 리턴한 해시값은 버킷 인덱스를 결정하는데 사용된다. 버킷 인덱스는 데이터가 실제로 저장되는 위치를 가리치는데 이 과정을 해싱이라고 한다.

지금까지 해시테이블에 객체를 저장하는 방법을 잘못 알고 있었다.

Member member = new Member(”th”) 라는 객체를 해시테이블에 저장할 때,

member.hashCode() 값을 key로, member 객체를 value로 저장했었다. 즉 HashMap<Integer, Member> hashMap = new HashMap<>(); 의 형태로 저장을 했던것이다. 하지만 이렇게 객체를 저장하는 방법은 드물다고 한다.

해시테이블에 key로 객체의 특정 필드를 사용한다.

해시 테이블의 키(key)는 고유한 값으로서 객체를 식별하는 역할을 수행해야 한다. 따라서 객체의 해시값은 키(key)로 사용하기 적합한 값이어야한다. 일반적으로 객체를 해시테이블에 저장할 때는 특정 필드를 키(key)로 사용하고, 해당 객체를 밸류(value)로 사용한다. 예를들어 핸드폰 번호, 주민등록번호, 이메일 주소와 같이 중복될 일이 없는 데이터를 키로 사용한다. → 예전에 공부했었는데..

해시테이블에 키값은 내부적으로 버킷에 저장된다.

아무튼 해시테이블은 key 값을 내부적으로 hashCode() 메서드를 호출하여 반환값인 해시코드를 버킷의 인덱스로 사용하여 데이터를 저장한다. 이때 해시충돌이 발생할 수 있기 때문에 이를 고려하여 해결하는 방법이 필요하다. 해시함수의 품질이 좋을 수록 해시 충돌이 최소화되어 해시테이블의 성능을 향상시킬 수 있다.

해시 충돌이 발생할 경우 충돌을 해결하는 방법들 중 하나인 Separate Chaining 또는 Open Addressing 등의 기법을 사용하여 데이터의 일관성을 유지할 수 있다.

해시 자료구조에 데이터를 저장할 때에는 반드시 hashCode() 메서드를 정의해야한다.

객체를 해시테이블에 저장하려면 해당 객체를 생성한 클래스에 hashCode() 메서드가 정의되어 있어야한다. hashCode() 메서드는 객체의 해시코드를 반환하는 역할을 수행하며, 해시테이블은 이를 사용하여 버킷의 인덱스를 결정한다. 또한 hashCode() 메서드의 반환값은 equals() 메서드와 함께 객체의 동일성을 판단하기 때문에 일관성 있는 동일성 판단을 위해 equals() 메서드도 함께 정의하는 것이 좋다.

만약 hashCode() 메서드가 **정의되어 있지 않다면?**

객체를 생성한 클래스에 hashCode() 메서드가 정의되어 있지 않다면 Object 클래스의 hashCode() 메서드가 호출되어 기본 해시코드를 반환한다. 이 경우 객체의 내용과 무관하게 객체의 메모리 주소를 기반으로 해시코드가 생성되기 때문에 동일한 내용을 가진 객체더라도 다른 해시코드를 가질 수 있다.

이는 해시테이블의 성능을 저하시킬 수 있다. 객체의 동일성 판단에 오류를 발생시킬 수 있다.

추가

// 해시테이블 생성
Hashtable<String, MemberDto> hashtable = new Hashtable<>();

// 객체생성
MemberDto member = new MemberDto("th");

// 해시 테이블에 객체 저장
hashtable.put(member.getName(), member);

hashtable의 key는 member.getName() 이다. member.getName() 은 String 타입이다. 하지만 MemberDto 클래스에 hashCode() 메서드가 정의 되어 있다면 String 클래스가 아닌 MemberDto의 hashCode() 메서드가 호출된다.

---

해시충돌

해시충돌(Hash Collision) 이란 해시함수가 서로다른 두 개의 입력 데이터에 대해 같은 해시 값을 출력하는 현상을 의미한다.

완전해시함수

서로다른 두 객체 x, y 가 있다.

x.eqauls(y) 가 false 일 때 x.hashCode() ≠ y.hashCode() 라면 이때 해시함수는 완전해시함수이다.

X.hashCode() % M

자바에서는 hashCode() 메서드가 반환하는 해시 코드의 표현 범위는 32비트이므로, 이는 최대 2^32개의 서로 다른 해시 코드 값을 가질 수 있다는 것을 의미한다. 따라서 해시 테이블등 해시 기반의 데이터 구조에서는 이 범위 내에서 최대 2³² 개의 버킷을 가질 수 있다.

메모리를 절약하기 위해 `int index = X.hashCode() % M;` 와 같이 버킷 인덱스 값을 줄일 수 있다.

이 방식을 사용하면 서로 다른 해시 코드를 가지는 서로 다른 객체가 1/M 확률로 같은 버킷을 사용하게 된다. 이는 해시 함수가 해시 충돌을 잘 회피하도록 구현되었느냐에 상관없이 또 다른 해시 충돌을 발생시킬 수 있다. 이렇게 해시충돌이 잘(?) 발생하게구현되어도 키-값 쌍 데이터를 잘 저장하고 조회할 수 있게 하는 방식이 있다.

대표적으로 두가지가 있는데 하나는 Open Addressing(개방 주소법)이고, 다른 하나는 Separeate Chaning(분리 연결법)이다. 이외에도 다양한 방법이 있지만 거의 이 둘을 응용한 것이다.

Separate Chaining

데이터를 추가할 버킷이 이미 사용중인 경우 해당 버킷의 인자 뒤에 링크드 리스트 형태로 데이터를 추가한다.

자바에서는 기본적으로 Separate Chaining 방식을 사용하여 해시충돌을 처리하기 때문에, 개발자는 별도의 충돌 처리 로직을 구현할 필요가 없다.

public class MemberDto {
	// 생략

	@Override
	public int hashCode() {
	    return 1;
	}
}

코드에서 MemberDto 클래스의 해시코드는 항상 1을 리턴한다.

// 해시테이블 생성
Hashtable<String, MemberDto> hashtable = new Hashtable<>();

MemberDto member1 = new MemberDto("th1");
MemberDto member2 = new MemberDto("th2");

따라서 member1과 member2 모두 버컷 인덱스는 1이다.

hashtable.put(member1.getName(), member1);
hashtable.put(member2.getName(), member2);

해시테이블에 member1을 저장하면 1번 버킷에 저장된다.

member2도 1번 버킷에 저장되어 해시충돌이 발생하지만 자바는 Separate Chaining 방식을 제공하기 때문에 해시충돌이 생기지 않고 링크드리스트 형태로 저장된다.

member1이 해당 버킷 인덱스에 링크드리스트의 첫 노드로 저장된다. 그리고 member2는 member1 다음 노드를 가리키는 포인터를 저장하는 형태로 저장된다. 즉, member1의 다음 노드 포인터가 member2를 가리키게 된다.

시간복잡도(검색, 추가, 삭제)

• 해시테이블 1번 버킷에 [member1-1, member1-2, member1-3]이 저장되었다.
• 2번 버킷에 [member2]가 저장되었다.
• 3번 버킷에 [member3]이 저장되었다.

member2와 member3을 검색할 때는 O(1)의 시간이 걸린다.

member1-3을 검색할 때는 O(M)의 시간이 걸린다. 이때 M은 1번 버킷의 링크드리스트의 크기이다.

링크드리스트의 크기에 따라 선형적인 검식 시간이 소요되기 때문이다.

Open Addressing

데이터를 삽입하려는 해시 버킷이 이미 사용중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식이다. 데이터를 검색, 추가, 삭제할 때 Linear Probing, Quadratic Probing 등의 방법을 사용한다.

Open Addressing방식은 연속된 공간에 데이터를 저장한다. 예를들어, 지금 추가하려는 데이터의 버킷 인덱스가 1이다. 하지만 이미 1번 버킷을 사용중이라면 2번 버킷에 데이터를 추가하게 된다. 만약 100번까지 버킷이 모두 사용중이라면 새로운 데이터는 101번 버킷에 저장된다.

Separate Chaining / Open Addressing 비교

둘 모두 Worst Case는 O(M)이다. 하지만 Open Addressing은 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 높다. 따라서 데이터 개수가 적다면 Open Addressing 방식이 Separate Chaining 방식보다 효율이 좋다. 하지만 배열의 크기가 커질수록 캐시효율이라는 Open Addressing의 장점이 사라진다. 배열의 크기가 커지면(데이터가 많아지면) 캐시적중률이 낮아진다.

자바에서는 기본적으로 Separate Chaining방식을 사용한다. Open Addressing 방식은 데이터 검색/추가/삭제 작업이 Separate Chaining에 비해 효율적이지 않다. 하지만 HashMap에서 remove() 메서드는 자주 호출될 수 있다. 게다가 HashMap에 저장되는 데이터가 많아지면 Open Addressing은 Separate Chaining보다 느리다. 즉, 데이터가 많질수록 Open Addressing는 WorstCase 발생 빈도가 높아진다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 '조정'할 수 있다면 Worst Case 또는 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있다.

자바8부터 데이터 개수가 많아지면 링크드 리스트 대신 트리를 사용한다.

자바8의 해시맵은 데이터 개수가 적을 때는 여전히 링크드리스트를 사용한다. 하지만 데이터 개수가 일정 개수 이상이면 트리를 사용하는 방식으로 동작한다. 즉, 데이터 개수가 적을 때는 링크드 리스트를 사용하고, 데이터 개수가 많아질 경우에는 트리를 사용하여 성능을 향상시킨다.

보통 링크드리스트 → 트리 전환은 버킷내의 데이터가 8개를 초과할 때 발생한다.
데이터를 삭제해서 6개가 되면 다시 링크드리스트로 변경한다.

트리는 링크드리스트에 비해 메모리 사용량이 많고, 데이터가 적을 때 트리와 링스트리스트의 Worst Case 차이의 의미가 없기 때문이다.

이를 통해 데이터 개수에 따라 최적의 데이터 구조를 선택하여 성능을 최적화하는 것이 Java 8에서의 Separate Chaining 방식의 특징 중 하나이다.

해시 버킷 동적확장

해시 버킷 개수의 기본값은 16개이다. 이후 버킷의 개수가 증가하여 로드팩터를 초과하면 버킷 개수를 2배로 늘리는 리해싱 작업을 수행한다. 버킷의 최대 개수는 230개다.

로드팩터의 기본값은 0.75이다. 즉 13개의 버킷에 데이터가 저장되어야 로드팩터의 값이 0.75를 초과하여 리해싱 작업이 일어난다.

극단적으로 하나의 버킷에 100개의 데이터가 저장되면 나머지 15개의 버킷은 비어있는 상태이다. 이때는 리해싱 작업이 일어나지 않는다 (그럴일은 없겠지만)

그런데 이렇게 버킷 개수가 두 배로 증가할 때마다, 모든 키-값 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는 문제가 있다. HashMap 생성자의 인자로 초기 해시 버킷 개수를 지정할 수 있으므로, 해당 HashMap 객체에 저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우에는 이를 생성자의 인자로 지정하면 불필요하게 Separate Chaining을 재구성하지 않게 하는것이 좋다.

보조 해시 함수

index = x.hashCode() % M 을 계산할 때 M은 소수일 때 index 값 붐포가 가장 균등할 수 있다. 만약 M이 소수가 아니라면 별도의 보조 해시함수를 이용해야 한다.

다음과 같은 방법으로 보조 해시함수를 구현할 수 있다.

// 보조 해시 함수 구현
private int supplementaryHash(int hash, int bucketCount) {
    // 임의의 소수 값이나 다른 비트 연산을 사용하여 보조 해시 값을 생성
    int supplementaryHash = hash ^ (hash >>> 16); // 예시로 XOR 비트 연산 사용
    return supplementaryHash % bucketCount; // 보조 해시 값을 버킷 개수에 맞게 모듈로 연산하여 인덱스 값 생성
}

supplementaryHash() 메서드는 원래의 hashCode() 값에 비트 연산(XOR)을 적용하여 보조 해시 값을 생성한 후, 버킷 개수에 맞게 모듈로 연산을 수행하여 최종적인 인덱스 값을 반환하도록 구현되어 있다. 이렇게 구현된 보조 해시 함수를 사용할 수 있다.

hashCode() 메서드 내에서 supplementaryHash() 메서드를 호출하여 리턴하는 방식으로 보조 해시 함수를 사용할 수 있다. 보조 해시 함수는 일반적으로 해시 함수의 결과로 얻은 버킷 인덱스를 보정하는 역할을 수행하여 충돌을 줄이는데 도움을 준다.

@Override
public int hashCode() {
    // 보조 해시 함수 호출하여 버킷 인덱스 보정
    int hash = this.x.hashCode() % M;  // 기본 해시 함수
    int supplementaryHash = supplementaryHash();  // 보조 해시 함수 호출
    return (hash + supplementaryHash) % M;  // 보정된 버킷 인덱스 리턴
}

// 보조 해시 함수 구현
private int supplementaryHash() {
    // ... 보조 해시 함수의 구현 ...
}

다만, 보조 해시 함수의 구체적인 구현 방식은 사용하는 언어, 해시 테이블의 구현 방식, 데이터의 특성 등에 따라 다양할 수 있기 때문에, 구현 환경에 맞는 적절한 보조 해시 함수를 선택하고 사용하는 것이 중요하다

String 객체에 대한 해시함수

String 객체에 대한 해시 함수 수행 시간은 문자열 길이에 비례한다.

public int hashCode() {
    int hash = 0;
    for (int i = 0; i < length(); i++) {
        // Horner's method:
        // 현재 문자의 해시 값을 이전 해시 값에 31을 곱한 뒤 현재 문자의 유니코드 값을 더함
        hash = 31 * hash + charAt(i);
    }
    return hash;
}

중요한 부분은 hash = 31 * hash + charAt(i);부분이다. 이 부분이 Horner's method를 적용한 부분으로, 현재 문자의 해시 값을 이전 해시 값에 31을 곱한 뒤 현재 문자의 유니코드 값을 더하여 해시 값을 누적한다. 이를 통해 각 문자의 유니코드 값을 사용하여 해시 값을 계산하고, 31을 소수로 사용하여 충돌을 최소화하고 해시 값을 균일하게 분포시킨다.

참고: https://d2.naver.com/helloworld/831311