[자료구조] 해시 테이블(Hash Table)

해시 테이블(Hash Table / Hash Map)

---

🔍 개념

해시 테이블은 대량의 정보를 저장하고 특정한 요소를 효율적으로 검색할 수 있는 데이터 구조이다. 다소 복잡하다.
해시 테이블의 구조는 테이블 내에 내부적으로 더 작은 sub-group인 "버킷"에 key-value 구조의 쌍을 저장해둔다.

키를 저장할 때 메모리의 공간을 덜 차지할 수 있도록 해시 함수를 통해 키값을 해시라는 특정한 숫자 값으로 변환해준다.

해시 테이블은 메모리 확장이 필요한 경우에만 메모리 크기를 늘리고, 가능하면 최소 크기를 유지한다.

검색 시 key를 사용해서 원하는 value를 가져올 수 있다. 이는 두개의 값이 하나의 쌍이기 때문에 가능한 것이다.

검색된 key는 사전에 정의된 해시함수를 통해 해시값을 반환받고 해당 버킷을 가리킨다.

다시 말해서 해시 함수를 통해 반환된 값은 버킷의 index가 된다.

🔍 장단점

우선 장점으로는 새로운 요소들의 추가나 삭제가 효율적이라는 점이다.
그리고 LinkedList는 노드끼리 연결되어 있어 거꾸로 검색할 때 비효율적이었지만 해시 테이블은 key-value 쌍이기 때문에 검색/가져오기가 효율적이다.
메모리 크기가 동적이다. 단, 직접적으로 크기를 조절해주어야 한다.

단점으로는 충돌이 일어날 수 있어 해시 함수의 정비에 손이 많이 간다는 것이다.
입력된 키의 해시값이 기존에 데이터가 들어 있는 버킷을 가리키는 경우 충돌이 발생한다.

📌 기본 구조

📌 사용

import java.util.Hashtable;

public class Main {

    public static void main(String[] args) {

        Hashtable<Integer, String> ht = new Hashtable<>();

        // 내용 삽입
        ht.put(0, "김철수");
        ht.put(1, "홍길동");
        ht.put(2, "성춘향");
        ht.put(3, "홍두깨");

        // 내부 값 출력
        for (int i = 0; i < ht.size(); i++) {
            System.out.println(ht.get(i));
        }

        // 내부 값 수정
        ht.replace(1, "마동석");

        System.out.println("HashTable의 크기 : " + ht.size());                    // 4
        System.out.println("HashTable Key 확인 : " + ht.containsKey(3));        // true
        System.out.println("HashTable Value 확인 : " + ht.contains("홍두깨"));  // true
        System.out.println("HashTable의 크기가 0인지 확인 : " + ht.isEmpty());     // false
        System.out.println("HashTable의 전체 KeySet 확인 : " + ht.keySet());       // [3, 2, 1, 0]

    }
}