[알고리즘] 자료구조: 해쉬

1. 해쉬 테이블

• 키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조
• 해쉬 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산
• Key를 통해 바로 데이터가 저장되어 있는 주조를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라짐
• 미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장 및 탐색 지원

 

2. 알아둘 용어

• 해쉬 함수(Hash Function): 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수
  • 해쉬(Hash), 해쉬 값(Hash Value), 또는 해쉬 주소(Hash Address): 해쉬 함수를 통해 리턴된 고정된 길이의 값
• 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  • 슬롯(Slot): 해쉬 테이블에서 한 개의 데이터를 저장할 수 있는 공간

 

3. 해쉬 테이블의 장단점과 주요 용도

• 장점
  • 데이터 저장/읽기 속도가 빠르다(검색 속도가 빠르다)
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉽다.
• 단점
  • 일반적으로 저장공간이 좀 더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다
• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현 시 (중복 확인이 쉽기 때문)
    
    

4. 충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 상용하기)

해쉬 테이블의 가장 큰 문제는 충돌(Collision)의 경우이다. 이 문제를 충돌 또는 해쉬 충돌이라고 부른다.

 

4.1 Chaining 기법

• 개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

4.2 Linear Probing 기법

• 폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈 공간에 저장하는 기법
  • 저장공간 활용도를 높이기 위한 기법

4.3 빈번한 충돌을 개선하는 기법

• 해쉬 테이블 저장공간을 확대 및 해쉬 함수 재정의
  
  

5. 시간 복잡도

• 일반적인 경우(Collision이 없는 경우) O(1)
• 최악의 경우(Collision이 모두 발생한 경우)는 O(n)
• Linear Probing, Chaining 기법 둘 다 동일

해쉬 테이블의 경우는 일반적인 경우를 기대하고 작성한다.

검색 기능에서 해쉬 테이블의 사용 예

• 배열에 데이터를 저장하고 검색할 때 O(n)
• 이상적인 해쉬 테이블 케이스에서 데이터를 검색할 때 O(1)
  
  

6. Java의 HashMap과 HashTable의 차이

참고: JAVA HashMap

• 해쉬 테이블 구조를 활용하여 구현된 JAVA Collection Framework 에 속한 클래스

Java 개발자라면 (Key,Value)로 저장하는 익숙한 자료구조인 HashMap이 있다. 그렇다면 Java에서 HashTable과 HashMap의 차이가 당연히 있을 텐데, 그 차이는 동기화 지원 여부에 있다.

   // 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;
}

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

위의 코드에서 첫번째 put은 해시 테이블의 put이며, 두 번째 put은 해쉬 맵의 put이다. 첫 번째 해쉬 테이블의 put에는 synchronized 키워드가 붙어있는 것을 확인할 수 있는데, 이것은 병렬 프로그래밍을 할 때 동기화를 지원해준다는 것을 의미한다. 이것은 해당 함수를 처리하는 시간이 조금 지연됨을 의미한다.

그렇기 때문에 우리는 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 해쉬 테이블(HashTable)을 사용해야 하며, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해쉬 맵(HashMap)을 사용하면 된다.