해시테이블 HashTable

해시테이블 HashTable

---

• 키Key와 값Value의 쌍으로 이루어진 자료구조입니다.

• 키를 해싱 함수Hash Function를 통해 고유한 인덱스로 변환한 후, 이 인덱스에 해당하는 위치에 값을 저장하는 방식으로 동작합니다.

해시테이블의 주요 특징

---

• 빠른 검색 속도

  • 키를 해싱 함수를 통해 바로 인덱스로 변환합니다.

  • 검색에 걸리는 시간이 상수 시간(O(1))에 가깝습니다.

• 중복된 키를 허용하지 않음

  • 각 키는 고유한 해싱 함수 값을 가지므로, 중복된 키를 저장할 수 없습니다.

• 저장 순서가 유지되지 않음

  • 저장된 순서대로 값이 저장되는 것이 아니므로, 저장 순서를 보장하지 않습니다.

Java에서의 HashTable & HashMap

---

자바에서는 HashTable과 HashMap 클래스를 제공하고 있습니다.

차이점

• Hashtable과 HashMap은 둘 다 key-value 쌍을 저장하는 데이터 구조입니다.

• 그러나 두 클래스 간에는 몇 가지 중요한 차이점이 있습니다.

• 동기화(synchronization)

  • Hashtable은 동기화(synchronization)된 메서드로 구성되어 있습니다.
  • 즉, 멀티스레드 환경에서 안전하게 사용할 수 있습니다.
  • 반면, HashMap은 동기화되지 않은(non-synchronized) 메서드로 구성되어 있습니다.
  • 따라서 멀티스레드 환경에서 HashMap을 사용할 때는 동기화를 보장하기 위해 별도의 처리가 필요합니다.

• null 값 허용 여부

  • Hashtable은 key나 value로 null 값을 허용하지 않습니다.
  • 반면, HashMap은 key나 value로 null 값을 허용합니다.

• 순서 보장 여부

  • Hashtable은 key-value 쌍의 순서를 보장하지 않습니다.
  • 반면, HashMap은 key-value 쌍의 순서를 보장하지 않지만, Java 8 이후로는 추가된 LinkedHashMap을 사용하면 순서를 보장할 수 있습니다.

• 속도

  • HashMap은 일반적으로 Hashtable보다 더 빠르게 동작합니다.
  • 이는 HashMap이 동기화를 하지 않기 때문입니다.

• 따라서, 멀티스레드 환경이 아니고 null 값을 허용해도 된다면 HashMap을 사용하는 것이 일반적으로 좋은 선택입니다.

Method

• Hashtable 클래스의 주요 메서드:

  • put(Object key, Object value): key-value 쌍을 추가합니다.
  • get(Object key): 지정된 key에 해당하는 value를 반환합니다.
  • remove(Object key): 지정된 key와 해당하는 value를 제거합니다.
  • containsKey(Object key): 지정된 key가 Hashtable에 포함되어 있는지 여부를 반환합니다.
  • keys(): Hashtable의 모든 key를 담은 Enumeration을 반환합니다.
  • size(): Hashtable의 key-value 쌍의 수를 반환합니다.
  • clear(): Hashtable의 모든 key-value 쌍을 제거합니다.

• HashMap 클래스의 주요 메서드:

  • put(Object key, Object value): key-value 쌍을 추가합니다.
  • get(Object key): 지정된 key에 해당하는 value를 반환합니다.
  • remove(Object key): 지정된 key와 해당하는 value를 제거합니다.
  • containsKey(Object key): 지정된 key가 HashMap에 포함되어 있는지 여부를 반환합니다.
  • containsValue(Object value): 주어진 value가 HashMap에 존재하는지 여부를 반환합니다.
  • isEmpty(): HashMap이 비어있는지 여부를 반환합니다.
  • keySet(): HashMap의 모든 key를 담은 Set을 반환합니다.
  • values(): HashMap의 모든 value를 담은 Collection을 반환합니다.
  • entrySet(): HashMap의 모든 key-value 쌍을 담은 Set을 반환합니다.
  • size(): HashMap의 key-value 쌍의 수를 반환합니다.
  • clear(): HashMap의 모든 key-value 쌍을 제거합니다.

import java.util.Hashtable;

public class Example {
    public static void main(String[] args) {
        // Hashtable 객체 생성
        Hashtable<String, Integer> hashtable = new Hashtable<>();

        // 데이터 추가
        hashtable.put("apple", 1);
        hashtable.put("banana", 2);
        hashtable.put("cherry", 3);

        // 데이터 검색
        int value = hashtable.get("banana");
        System.out.println("Value of banana: " + value);

        // 데이터 제거
        hashtable.remove("cherry");

        // 모든 key-value 쌍 출력
        for (String key : hashtable.keySet()) {
            System.out.println(key + " = " + hashtable.get(key));
        }
    }
}

import java.util.HashMap;

public class Example {
    public static void main(String[] args) {
        // HashMap 객체 생성
        HashMap<String, Integer> hashMap = new HashMap<>();

        // 데이터 추가
        hashMap.put("apple", 1);
        hashMap.put("banana", 2);
        hashMap.put("cherry", 3);

        // 데이터 검색
        int value = hashMap.get("banana");
        System.out.println("Value of banana: " + value);

        // 데이터 제거
        hashMap.remove("cherry");

        // 모든 key-value 쌍 출력
        for (String key : hashMap.keySet()) {
            System.out.println(key + " = " + hashMap.get(key));
        }
    }
}

Map과 HashMap의 차이

---

• Map과 HashMap은 모두 키-값 쌍(key-value pair)의 데이터를 저장하는 자료구조입니다.

• Map은 인터페이스interface이며, HashMap은 Map 인터페이스를 구현한 클래스class입니다.

• Map은 인터페이스이므로 인스턴스를 직접 생성할 수 없습니다.

• HashMap은 클래스이므로 인스턴스를 생성할 수 있습니다.

• Map은 다양한 구현체를 가질 수 있습니다. HashMap, TreeMap, LinkedHashMap

• HashMap은 Map 인터페이스를 구현한 구현체 중 하나입니다.

• HashMap은 내부적으로 해시 테이블(hash table)을 사용하여 데이터를 저장합니다.

  • 검색과 삽입에 상수 시간 O(1)에 가까운 시간 복잡도를 보장합니다.

• TreeMap은 이진 검색 트리binary search tree를 사용합니다.

  • 검색과 삽입에 로그 시간 O(log n)의 시간 복잡도를 가집니다.

• HashMap은 순서를 보장하지 않습니다. 즉, 저장된 순서대로 값을 가져올 수 없습니다.

• LinkedHashMap은 순서를 보장합니다. 즉, 저장된 순서대로 값을 가져올 수 있습니다.

• HashMap은 검색과 삽입 연산이 빠르고, 저장된 순서를 보장하지 않는 경우에 적합한 자료구조입니다.

• 만약, 저장된 순서를 보장하거나 검색과 삽입 연산이 느려도 되는 경우에는 TreeMap이나 LinkedHashMap을 고려할 수 있습니다.