자료구조 - 해쉬 테이블

대표적인 자료구조 해쉬 테이블을 알아보다 정리해 놓으면 좋을 것 같은 부분들이 있어 정리하려고 한다.

 

해쉬 테이블

https://en.wikipedia.org/wiki/Hash_table

• 키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조
• Hash Function을 통해, 배열에 키에 대한 데이터를 저장할 수 있는 인덱스를 계산
• Key를 통해 바로 데이터가 저장되어 있는 인덱스를 알 수 있다는 것은 저장 및 탐색 속도가 획기적으로 개선
• Hash Function이 생성할 수 있는 인덱스 번호에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장, 탐색

---

간단한 해시 테이블을 작성해보면서 구조를 이해해 보자.

import java.io.*;

public class Main{

    static class Hash{
        public Item[] hashTable;

        public Hash(Integer size){
            this.hashTable = new Item[size];
        }
        public static class Item{
            String value;
            public Item(String value){
                this.value = value;
            }
        }

        public int hashFunc(String key){
            return (int)(key.charAt(0)) % this.hashTable.length;    // 0 ~ length-1 -> index
        }

        public boolean put(String key, String value){
            Integer idx = this.hashFunc(key);
            if(this.hashTable[idx] != null){
                this.hashTable[idx].value = value;
            }
            else{
                this.hashTable[idx] = new Item(value);
            }
            return true;
        }
        public String get(String key){
            Integer idx = this.hashFunc(key);
            if(this.hashTable[idx] != null) return this.hashTable[idx].value;
            return null;
        }
    }
    public static void main(String[] args) throws IOException {
        Hash hash = new Hash(10);

        hash.put("YeJun", "1998");
        hash.put("Dennis", "1990");

        System.out.println(hash.get("YeJun"));
        System.out.println(hash.get("Dennis"));
    }

}

// System.out
// 1998
// 1990

구현을 직접 해보면서 느낄 수 있었던 점과

 

• 장점
  
  • 데이터의 저장 및 검색 속도가 빠르다.
    • 해쉬 함수를 통해 idx로 접근을 할 수 있어 O(1)에 해결
  • 키에 대한 데이터가 있는지 중복 확인에 용이하다
    • 해쉬 함수를 통해 idx로 접근하여 값이 있는지 확인 O(1)
• 단점
  • idx를 통해 접근해야 하기 때문에 크게 배열을 생성해놔야 한다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌이 발생
    • 위의 해쉬 함수를 보면 String의 첫 번째 문자로 키 인덱스를 결정하기 때문에 맨 앞글자만 같으면 충돌
    • 충돌을 해결하기 위한 알고리즘, 자료구조가 필요
• 적합한 사용 용도
  • 검색이 많이 필요한 경우 (Key - Value 형태면 더 편리)
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐시 (중복 확인이 용이)

---

해쉬 충돌(Collision) 해결 알고리즘

 

1. 복잡한 해쉬함수 혹은 키에 따라 다양한 값이 나오도록 해쉬 함수를 정의
   • 해쉬 테이블 저장공간이 확대되지만 빈번한 해쉬 충돌이 일어나는 것보단 낫다
2. Chaining 기법
   • 개방 해슁, Open Hashing 기법 - 해쉬 테이블 저장공관 외의 공간을 활용하는 기법
   • 충돌이 일어나면, LinkedList의 구조로 데이터를 추가로 뒤에 연결시키는 방법

https://twinparadox.tistory.com/518

    3.  Linear Probing 기법

•  폐쇄 해슁, Close Hashing 기법 - 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 Hash Address의 다음 Address부터 맨 처음 나오는 빈 공간에 저장하는 기법
  • 저장공간 활용도가 높아짐

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=babobigi&logNo=220457310976

 

---

시간 복잡도

• 일반적인 경우(Collision이 없는 경우)는 O(1)
• 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)
  • n개의 데이터를 넣었는데 n개 모두 해쉬 충돌이 일어나면 n개의 key값을 다 확인해야 함
• 해쉬 테이블의 경우 일반적인 경우를 기대하고 사용!

검색에서 해쉬 테이블 사용 시 배열과 차이

• 배열에 데이터를 저장하고 검색 시 O(n)
• 이상적 해쉬 테이블의 경우 데이터를 저장하고 검색 시 O(1)

---

자바에서는 주로 HashMap이라는 구현체를 사용하며, 특히 key값을 정렬하여 가지고 있어야 하는 경우에는 SortedMap 인터페이스의 구현체인 TreeMap을 자주 사용하는데, 간단하게 정리해 놓고 사용하려고 한다.

 

SortedMap 구현 클래스 TreeMap

SortedMap은 생성자로 Key 정렬을 위한 Comparator를 전달할 수 있으며, No Arguments 생성자로 생성할 시에는 Key가 구현한 Comparable 인터페이스를 따라 정렬을 한다.

public static void main(String[] args) {
	// No Arguments
    SortedMap<String, Integer> map = new TreeMap<>();

    map.put("banana", 50);

    map.put("cocoa", 90);

    map.put("avocado", 10);

    

    map.keySet().forEach(key -> {

        System.out.println(key + " -> " + map.get(key));

    });

}
/*
avocado -> 10
banana -> 50
cocoa -> 90
*/

public static void main(String[] args) {
	// Comparator 람다식
    SortedMap<String, Integer> map = new TreeMap<>(
                            		(s1, s2) -> s1.length() - s2.length());

    map.put("banana", 50);

    map.put("cocoa", 90);

    map.put("avocado", 10);

    

    map.keySet().forEach(key -> {

        System.out.println(key + " -> " + map.get(key));

    });

}
/*
cocoa -> 90
banana -> 50
avocado -> 10
*/

SortedMap Methods

Map 인터페이스와 달리 SortedMap에서 추가적으로 제공하는 메서드

1. Comparator comparator()
   - SortedMap에 등록된 Comparator가 있으면 해당 인스턴스를 리턴하고, 별도로 등록된 게 없으면 null을 리턴
2. K firstKey()
   - 첫 번째 Key를 리턴합니다. 오름차순의 경우 가장 작은 값(lowest)을 리턴
3. K lastKey()
   - 마지막 Key를 리턴합니다. 오름차순의 경우 가장 큰 값(highest)을 리턴
4. SortedMap headMap(K toKey)
   - 인자로 받은 toKey 보다 작은 Key들을 가지고서 부분적인 Map을 리턴
5. sortedMap tailMap(K fromKey)
   - 인자로 받은 fromKey 보다 큰 Key들을 가지고서 부분적인 Map을 리턴