카테고리 없음

HashTable

꽃달린감나무 2024. 2. 1. 18:10
728x90

구글에게 물어보면 HashTable은 아래와 같이 답변해준다.

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

 

해시 테이블은 왜 데이터를 빠르게 검색할 수 있을까? 라는 의문이 들었다.

 

이에 대하여 물어보면,

- 내부적으로 배열( 버킷 )을 사용하여 데이터를 저장하기 때문

- 해시함수를 사용해 각각의 Key값에 해시함수를 적용해 배열의 고유한 Index로 활용하기 때문

 

그럼 버킷과 해시함수는 뭐야?

일단 그림을 통해 이해해보면 쉽다.

그림으로 보아하니,

- 해시함수는 John Smith라는 키를 "2"라는 버켓의 인덱스로 바꿔주는 함수

- 버켓은 데이터가 저장되는 배열

 

그럼 해시 테이블은 데이터를 어떻게 저장하고 조회하는가? 일련의 과정을 통해 이해해보자

 

1.  "John Smith"이라는 학생의 이름을 해시함수에 넣으면 해시값이 "2"이 출력

2.  이제 해시값인 "2"을 배열의 2(해시값)%15(배열의 크기)로 인덱스 2로 변환. 즉, "521-1234"를 배열의 2번째 위치에 저장

3.  "521-1234을 조회하기 위해서 Key값인 "John Smith"를 해시함수에 넣어 해당하는 인덱스 2을 조회

 

위의 순서로 데이터를 조회하므로, 일반적으로 데이터를 조회할 때, O(1)의 시간복잡도를 가진다.

하지만 문제가 있다. [Sarah, 521-3824]라는 Key : Value 페어가 있다고 가정을 해보자.

만약, "Sarah"를 해시함수에 넣어서, LisaSmith해시값이 "1"이 나와버리면 어떻게 해야할까?

 

이러한 상황을 해시 충돌이라고 한다. 이러한 해시 충돌을 해결하는데는 2가지 방법이 있다.

Open addressing(개방 주소법)과 Separate chaning이 있다.

 

Open addressing

해시 충돌이 발생했을 때, 다른 빈 버켓을 찾아 데이터를 저장하는 방법이다.

위 사항을을 예를 들어보면, 이미 "2" 인덱스에 John Smith가 존재하므로, (2(해시값) + 1) % 15(배열크기)의 위치인 "3"인덱스에

Sarah에 value인 "521-3824"가 저장되는 것이다.

 

OpenAddressing에 여러가지 방법이 있는 그중 3가지만 살펴보자면,

  • 선형 탐사 (Linear Probing) - 충돌이 발생하면 다음 빈 버킷을 찾아서 데이터를 저장, 즉, 충돌이 발생한 위치에서 선형적으로 한 칸씩 이동하면서 빈 버킷을 찾는다. i가 충돌이 발생한 위치에서의 시도 횟수일 때, 다음 위치는 (해시값 + i) % 배열크기가 된다.              
  • 이차원 탐사 (Quadratic Probing) 충돌이 발생하면, 선형 탐사와 달리 일정한 간격을 두고 다음 빈 버킷을 찾는다. 즉, 충돌이 발생한 위치에서 한 칸씩 이동하는 대신, i^2칸씩 이동하면서 빈 버킷을 찾는다. i가 충돌이 발생한 위치에서의 시도 횟수일 때, 다음 위치는 (해시값 + i^2) % 배열크기가 된다.
  • 랜덤 프로브 (Random Probing) 충돌이 발생하면 무작위로 다음 위치를 선택하여 데이터를 저장한다. 이는 충돌 해결을 더 무작위화하여 일정한 패턴을 방지합니다. i가 충돌이 발생한 위치에서의 시도 횟수일 때, 다음 위치는 (해시값 + 임의의 값(i)) % 배열크기가 됩니다.

Separate Chaning

해시 충돌이 발생했을 때, 각 충돌된 위치에 연결 리스트를 사용하여 데이터를 저장하는 방법이다. 동일한 해시값을 가진 데이터들이 한 위치에 모여있게 되며, 각각의 연결 리스트에는 충돌된 데이터들이 순서대로 저장된다. 

 

 

위 그림과 같이, JohnSmith가 이미 인덱스에 저장되므로, [Sandra Dee의 위치, John, 521-1234] 를 저장하고, 그 다음 노드에

[x, Snadre Dee, 521-9655]를 저장한다.

 

이러한 방식에는, 단점이 존재한다. 한 주소의 해시충돌이 반복적으로 일어나면, 연결리스트에서 원하는 key에 대한 데이터를 찾을 때 , 첫 노드부터 검색하게 되므로 시간복잡도가 O(n)이 될 수 있다.

 

 

Java HashTable vs HashMap

Open addressing으로 구현되어있는 CPython과는 다르게 Java에서 hashTable은 Separate Chaning방식으로 구현되어있다.

Java에서는 HashMap과 HashTable 그 외 클래스로 나누어져있는데, HashMap과 HashTable의 차이는 동기화 지원 차이이다.

 

// 해시맵
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 해시테이블
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    addEntry(hash, key, value, index);
    return null;
}

두 코드를 비교해보면, 해시 맵과 다르게 해시테이블에서는 sychronized 적혀있는 걸 확인할 수 있다.
즉,  멀티 쓰레드 환경에서 공유 데이터에 대해 동기화를 지원해준다는 것을 말한다. 따라서 HashMap은 싱글쓰레드 환경이나, 공유 데이터를 사용하지 않는 환경에서 사용하면 좋고, HashTable은 공유데이터를 사용해야하는 환경, 멀티쓰레드 환경에서 사용하는 것이 좋다.

 

728x90