Hash Table

 

 

자료구조

key - value로 저장하는 자료 구조

 

What ?

HashTable

데이터를 키 - 값 (key - value)로 저장하는 자료 구조입니다.

 

빠르게 데이터를 검색할수 있게 하는 자료 구조입니다.

 

검색, 삽입, 삭제를 효율적이게 하기 때문에 알고리즘에서 많이 사용됩니다.

 

---

 

Why ?

HashTable

키 (key)를 해시 함수에 입력하여 해시 값(인덱스)을 계산하고 해당 위치의 값을 삽입, 검색, 삭제를 합니다.

 

내부적으로 배열( 버킷 : 해시 테이블 내에서 데이터가 저장되는 실제 공간 )을 사용해 데이터를 저장하기 때문에 빠른 검색속도를 제공합니다.

 

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

 

해시테이블의 평균 시간복잡도는 " O(1) " 입니다.

 데이터 충돌 시, Chaining에 연결된 리스트들까지 검색을 해야 하므로  시간복잡도가 O(N)이 될 수 있습니다.

 

 

키 - 값(Key, Value)가 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장되어있습니다.

 

먼저 index = hash_function("John Smith") % 16 연산을 통해 index 값을 계산합니다.

 

그리고 array[index] = "521-1234" 로 전화번호를 저장하게 됩니다.

 

키(Key)값으로 해시 함수를 1번만 수행해 데이터를 저장, 삭제, 조회할 수 있습니다.

 

---

 

How?

HashFunction

해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것입니다.

 

대표적인 해시 함수 4가지

 

    Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산합니다.

   

• • 💡  테이블의 크기를 소수로 설정하고,  2의 제곱수와 먼 값을 사용해야 효과가 좋습니다.
  • 💡   공식 : h(k) = k , mod m ( k = Key, m= hashTable key), 주소 = 입력값 % 테이블의 크기 
  •  예시 : 테이블 크기: 10, 키 값 : 15, 22, 7

Key	계산 ( K %  m)	주소 (해시 값)
15	15 % 10 = 5	5
22	22 % 10 = 2	2
7	7 % 10 = 7	7

 

 

 

     Digit Folding: Key를 ASCII 코드로 바꾸고 이를 나누어 합산하여 해시값을 생성하는 방식입니다.

• • 💡  문자열의 키를 숫자로 변환하고 테이블 크기로 나누어 주소를 생성합니다.
  •  예시 : 테이블 크기: 10, 문자열 키 : "abc" 
  • ASCII 코드 : a = 97, b = 98, c = 99
    합산 값 : 294
    결과 : 294 % 10 = 4

   

 

    Multiplication Method: 숫자로 된 Key값 실수를 곱한 뒤, 값을 이용해 해시값을 계산합니다.

 

• • 💡 공식 : h(k) = ⌊m(kA mod1)⌋ 주소 = 테이블 크기  X ( 키 X 실수 ( 0과 1 사이)  % 1 ) 
  •  예시 : 테이블 크기(m) : 10, 키값(k) : 123, 실수(A): 0.6180339887
  • kA = 123 * 0.6180339887 = 76.006
    kA mod 1 = 76.006 mod 1 = 0.006
    m * (kA mod 1) = 10 * 0.006 = 0.06
    h(k) = ⌊ 0.06 ⌋ = 0

 

 

    Universal Hashing: 여러 개의 해시 함수를 미리 정의하고, 요청이 올 때마다 무작위로 하나를 선택해 사용합니다.

 

• • 💡 해시 함수의 충돌을 줄이고, 최악의 경우를 방지하고, 동적 해시 함수 선택으로 성능 최적화를 합니다.
  •  
  •  예시 : 해시 함수들 : h1(k) = k % 10, h2(k) = (k * 3) % 10, h3(k) = (k * 7) % 10, 키값 : k = 123
  • h1(k) = 123 % 10 = 3
    h2(k) = (123 ∗ 3) % 10 = 369 % 10 = 9

 

---

 

How ?

충돌 방지

 

만약 "John Smith"와 "Mang Kyu"의 해시 함수 결과 값이 동일하면 충돌이 발생합니다.

 

이때, 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing) 로 충돌을 해결합니다.

 

 

분리 연결법 ( Separate Chanining )

동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용해 다음 데이터의 주소를 저장합니다.

 

위의 그림과 같이 동일한 버킷으로 접근을 한다면 데이터들을 연결을 해서 관리해줍니다.

 

이러한 Chaining 방식은 해시 테이블의 확장없이 구현이 가능하며, 손쉽게 삭제할 수 있습니다.

 

하지만 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아져 캐시의 효율성이 감소합니다.

Java는 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현하였다.

---

 

개방 주소법 ( Open Addressing )

 

추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다.

데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되는데 Hash Table을 재정리합니다.

 

공간 활용 3가지

 

Linear Probing: 현재의 버킷 index로부터 고정폭 만큼 이동해 차례대로 비어 있는 버킷에 데이터를 저장한다.

Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식입니다.

예를 들어 처음 충돌이 발생한 경우에 1만큼 이동하고, 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.

Double Hashing Probing: 해시된 값을 한번 더 해싱해 해시의 규칙성을 제거합니다.

해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

 

---

 

With Java

(Key,Value)로 저장하는 익숙한 자료구조인 HashMap이 있다. 차이는 동기화 지원 여부에 있습니다.

// 해쉬table
public synchronized V put(K key, V value) {
    // 값이 null인지 확인
    if (value == null) {
        throw new NullPointerException();
    }

    // 주어진 key로부터 해시값을 계산
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // 부호 없는 양의 정수를 위해 16진수화 시킵니다.
    // 그후 테이블(tab) 크기를 벗어나지 않도록 나머지 연산
    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)) {
            // If key is already present, update value
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    // 키가 없으면 새로운 엔트리 추가
    addEntry(hash, key, value, index);
    return null;
}


// 해시Map 
// putVal을 통해 해시맵에 값 추가 (기본 메서드)
public V put(K key, V value) {
	// hash(key)는 key의 해시값을 계산하는 hashfunction
    return putVal(hash(key), key, value, false, true);
}

 

 

첫번째 해시테이블의 put에는 synchronized로 병렬 프로그래밍을 할 때 동기화를 지원해줍니다.

동기화 : 한 번에 하나의 스레드만 코드 블록을 실행할 수 있도록 보장하는 메커니즘

이것은 해당 함수를 처리하는 시간이 조금 지연됨을 의미힌다.

 

 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 해시테이블(HashTable)

 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시맵(HashMap)

 

---

 

How ?

HashTable

키-값 쌍을 다뤄야 할 때

해시맵의 핵심은 키(key)와 값(value) 쌍으로 데이터를 저장하는 것입니다.

문제를 해결할 때 데이터를 빠르게 조회하거나 특정 값을 기준으로 데이터를 그룹화해야 할 때, 해시맵은 매우 유용합니다.

2. 중복을 관리할 때

해시맵은 중복을 처리하는 데 유용합니다. 예를 들어, 어떤 값이 이미 존재하는지 체크하고 싶을 때 해시맵을 사용할 수 있습니다. 특히, 값을 세는 방식으로 중복을 확인하거나 그룹화할 수 있습니다.

 

3. 빠른 검색이 필요할 때

해시맵은 검색 시간 복잡도가 평균 **O(1)**이기 때문에, 특정 데이터를 빠르게 찾을 필요가 있을 때 매우 유용합니다. 문제에서 빠른 조회나 검색이 필요하다면 해시맵을 사용하는 것이 좋습니다.

 

4. 그룹화해야 할 때

문제에서 여러 개의 값을 그룹화하거나 카운팅해야 할 때, 해시맵을 유용하게 사용할 수 있습니다. 해시맵을 이용하면 각 키에 대한 값 목록을 관리하거나, 특정 값을 기준으로 데이터를 묶는 작업을 쉽게 할 수 있습니다.

 

5. 정렬된 데이터를 다뤄야 할 때

해시맵을 사용하여 값을 그룹화하고, 그 후 정렬을 해야 하는 경우에도 유용합니다. 다만, 해시맵 자체는 정렬되지 않지만, 맵에 저장된 데이터를 정렬해야 한다면 TreeMap이나 List와 결합하여 활용할 수 있습니다.

해시맵 사용을 결정하는 법

문제를 풀 때 해시맵을 사용할지 말지 결정하는 방법은 다음과 같은 질문들을 던져보면 됩니다:

1. 데이터를 키와 값의 쌍으로 저장할 수 있는가?
   • 예를 들어, 첫 3음 -> 노래 제목을 매핑하려면 해시맵을 사용할 수 있습니다.
2. 특정 키에 해당하는 값을 빠르게 찾거나 업데이트할 수 있어야 하는가?
   • 예를 들어, 중복을 찾거나 특정 키에 대해 빠르게 값을 업데이트해야 할 때 해시맵이 유용합니다.
3. 같은 데이터를 여러 번 묶어야 하는가?
   • 예를 들어, 같은 첫 3음에 해당하는 여러 제목들을 묶어서 저장해야 한다면 해시맵을 사용하여 키에 대한 리스트를 값으로 저장할 수 있습니다.
4. 반복적인 검색이 필요하거나 데이터를 빠르게 찾고자 하는가?
   • 예를 들어, 특정 음이 몇 번 등장했는지나 어떤 음이 있는지 빠르게 확인하고 싶을 때 해시맵이 유용합니다.

---