[자료구조] 해시 테이블

Hash Table

키(Key)를 통해 값(Value)을 빠르게 찾기 위해 사용하는 자료구조이다.

해시 테이블은 해시 함수(Hash Function)를 사용하여 데이터를 배열의 인덱스에 매핑하는 방식으로 동작하며,

이를 통해 O(1)의 시간 복잡도로 데이터 검색, 삽입, 삭제 작업을 할 수 있다.

 

해시 테이블의 특징

출처: https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm

• 해시 테이블은 키-값 쌍을 저장하는 자료구조로, 해시 함수를 사용하여 키를 특정 인덱스로 변환하고, 그 인덱스에 값을 저장한다.
• 해시 함수(Hash Function)는 입력값(키)을 받아서 특정 해시 값을 반환하는 함수로, 이 해시 값은 배열의 인덱스가 된다.
• 해시 테이블은 해시 충돌(Hash Collision)이 발생할 수 있는데, 이는 다른 키들이 같은 해시 값을 가질 때 발생한다. 이를 해결하기 위해 충돌 해결 기법이 사용된다.

 

해시 테이블의 구조

• 해시테이블은 n개의 버킷으로 이루어지는 테이블로서 n-1개의 원소를 가진다.
• 하나의 버킷은 s개의 슬롯을 가질 수있으며, 하나의 슬롯에는 하나의 항목이 저장됨.
• 하나의 버킷에 여러개의 슬롯을 두는 이유이기도 하다.
• 서로 다른 두 개의 키가 해시 함수에 의해 동일한 해시 주소로 변활 될 수 있으므로 여러 개의 항목을 동일한 버킷에 저장하기 위함이다.

 

해시 함수의 예시

int hash = key.hashCode() % arraySize;

• key.hashCode()는 자바에서 제공하는 메서드로, 객체의 해시 값을 반환한다.
• 이 해시 값을 배열 크기로 나눈 나머지 값을 배열 인덱스로 사용한다.

 

해시 충돌 경우

• key는 다른데 hash가 같을 때
• key도 hash도 다른데 hash % arraySize 결과가 같을 때

 

해시 충돌 해결 방법

1. 체이닝(Chaining)
2. 개방 주소법(Open Addressing)

 

체이닝

출처:https://en.wikipedia.org/wiki/Hash_table#Separate_chaining

• 버킷 내에 연결리스트를 할당하여 버킷에 데이터를 삽입한다.
• 해시 충돌이 발생하면 연결 리스트(LinkedList)로 데이터들을 연결하는 방식

 

해시 테이블의 구조 예시

Index	0	1	2	3	4	..
Bucket	[NULL]	[NULL]	["apple", "banana"]	[NULL]	[NULL]	..

• "apple"과 "banana"는 해시 값이 같다고 가정해서 2번 인덱스에 함께 저장되었다.
• 버킷이 체이닝을 사용하여 연결 리스트로 이 두 항목을 관리한다.
• 해시 충돌이 발생했을 때, 같은 인덱스에 여러 값이 들어갈 수 있는 구조를 보여준다.

 

개방 주소법(Open Addressing)

출처:https://en.wikipedia.org/wiki/Hash_table#Open_addressing

1. 선형 탐사(Linear Probing): 충돌이 발생하면 다음 빈 공간을 찾는 방식.
2. 이차 탐사(Quadratic Probing): 충돌 시 더 먼 위치를 탐색하며, 점점 더 멀리 탐색하는 방식.
3. 이중 해싱(Double Hashing): 두 개의 해시 함수를 사용하여 충돌 시 다른 해시 함수를 적용해 새로운 위치를 찾는 방식.

 

주의할 점

Index	bucket	상황
0
1	010-2222-2222 홍진호 deleted(더미값) or 아래 데이터를 올려줘야 함	put(); - 해시값: 2 remove();
2	010-1010-1001 이진수	put(); - 해시값: 2
3
4	010-7777-7777 럭키짱
5

• key 값이 다르지만 해시값이 같아 해시 충돌이 일어난 상황이다.
• 해시 충돌이 일어나서 다음 빈 공간에 데이터를 넣었다면 더미값을 넣어주거나, 빈 공간에 넣어진 데이터를 원 위치로 돌려줘야 한다.
• 이유는 원래 해시 값이 2인 키값: "010-1010-1001"을 찾지 못할수 도 있기 때문이다.

 

리사이징(resizing)

• 새로운 배열에 기존 배열의 키를 새롭게 재 해싱
• 개방주소법에서 사용되는 고정 크기의 배열이 가득 차거나 체이닝의 연결 리스트가 길어지게되면 검색 효율이 떨어지기 때문에 버킷의 갯수를 늘려주는 방법
• 쉽게 얘기하면 데이터가 많이 차게 되면 크기를 늘려줘야 한다는 것이다.
• 자바의 HashMap 같은 경우에는 3/4이 차면 동적으로 크기를 2배 늘려준다. 

 

해시 테이블 사용 시 중요한 점

1. 해시 함수의 품질: 좋은 해시 함수는 데이터가 고르게 분포되도록 하여 해시 충돌을 최소화한다. 충돌이 많이 발생하면 해시 테이블의 성능이 저하될 수 있다.
2. 충돌 해결 방식: 체이닝과 개방 주소법 등 다양한 충돌 해결 방식이 있으며, 데이터의 특성에 맞는 충돌 해결 방식을 선택하는 것이 중요하다.
3. 동적 확장: 해시 테이블의 크기가 포화 상태에 도달하면 자동으로 확장이 이루어지지만, 확장 과정에서 성능 저하가 발생할 수 있다.
4. 메모리 효율성: 해시 테이블은 내부적으로 빈 공간을 많이 차지할 수 있으므로, 메모리 사용에 주의해야 한다.

---

HashMap

Map은 자바의 중요한 자료구조 중 하나로, 키(key)와 값(value) 쌍을 이용하여 데이터를 저장하는 연관 배열(associative array) 또는 해시 테이블(hash table) 형태의 자료구조이다. 자바에서는 Map 인터페이스를 통해 여러 종류의 맵을 구현할 수 있으며, HashMap, TreeMap, LinkedHashMap 등이 대표적인 구현체이다.

 

Map의 특징

• Map은 키(key)를 사용해 값을 저장하고, 키를 통해 값에 접근하는 자료구조이다.
• 각 키(key)는 유일해야 하며, 값(value)는 중복될 수 있다. 즉, 하나의 키에는 하나의 값만 대응된다.
• 중복된 키는 허용되지 않으며, 같은 키를 다시 저장하면 이전 값이 덮어쓰여 새로운 값으로 대체된다.

 

주요 연산:

• put(K key, V value): 맵에 데이터를 추가하는 메서드. 키와 값을 쌍으로 저장한다.
• get(Object key): 키에 대응되는 값을 반환하는 메서드. 키가 없으면 null을 반환한다.
• remove(Object key): 특정 키에 해당하는 값을 삭제하는 메서드.
• containsKey(Object key): 특정 키가 맵에 존재하는지 확인하는 메서드.
• size(): 맵에 저장된 키-값 쌍의 개수를 반환하는 메서드.

 

장점

1. 빠른 검색 속도: HashMap은 해싱을 사용하여 키를 통해 데이터를 빠르게 찾을 수 있다. 키를 기반으로 값을 검색하는 시간 복잡도는 O(1)로 매우 빠르다.
2. 유연성: 다양한 Map 구현체가 제공되어, 필요한 상황에 맞는 자료구조를 선택할 수 있다. 예를 들어, 정렬이 필요할 때는 TreeMap, 입력 순서 유지가 필요할 때는 LinkedHashMap을 사용할 수 있다.
3. 중복된 키 방지: 각 키는 유일해야 하므로, 키 값이 중복되는 것을 방지하여 데이터 관리가 용이하다.
4. 데이터 매핑: 키와 값을 쌍으로 매핑하여 사용하기 때문에, 직관적이고 명확한 데이터를 관리할 수 있다.

 

단점

1. 메모리 사용량: HashMap은 해시 테이블 기반이기 때문에, 메모리 사용량이 많아질 수 있다. 특히, 해시 충돌이 발생할 경우 메모리와 성능에 부정적인 영향을 미칠 수 있다.
2. 비순차적 저장: HashMap은 데이터가 입력된 순서나 정렬된 순서로 저장되지 않는다. 데이터의 순서가 중요한 경우, LinkedHashMap 또는 TreeMap을 사용해야 한다.
3. 멀티스레드 환경에서 주의 필요: 기본적으로 HashMap은 스레드 안전(thread-safe)하지 않으므로, 멀티스레드 환경에서 사용할 경우 추가적인 조치가 필요하다. (예: ConcurrentHashMap 사용)

 

HashMap 사용 예시

public class HashMapExample {
    public static void main(String[] args) {
        // HashMap 생성
        Map<String, Integer> map = new HashMap<>();
        
        // 데이터 추가 (put)
        map.put("Apple", 5);
        map.put("Banana", 3);
        map.put("Orange", 7);
        
        // 데이터 읽기 (get)
        System.out.println("Apple 개수: " + map.get("Apple"));  // 출력: Apple 개수: 5
        
        // 데이터 수정
        map.put("Banana", 10);  // Banana의 값을 10으로 수정
        System.out.println("Banana 개수: " + map.get("Banana"));  // 출력: Banana 개수: 10
        
        // 데이터 삭제
        map.remove("Orange");
        
        // 키가 존재하는지 확인
        if (map.containsKey("Orange")) {
            System.out.println("Orange가 있습니다.");
        } else {
            System.out.println("Orange가 없습니다.");  // 출력: Orange가 없습니다.
        }
        
        // Map 크기 확인
        System.out.println("Map 크기: " + map.size());  // 출력: Map 크기: 2
    }
}

 

• HashMap은 자바에서 가장 일반적으로 사용되는 Map 구현체이다.
• 해시 테이블을 기반으로 하여, 키를 해싱(hash)하여 값을 빠르게 찾는다.

 

TreeMap 사용 예시

public class TreeMapExample {
    public static void main(String[] args) {
        // TreeMap 생성
        Map<String, Integer> map = new TreeMap<>();
        
        // 데이터 추가
        map.put("Banana", 10);
        map.put("Apple", 5);
        map.put("Orange", 7);
        
        // 자동으로 키가 정렬됨
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
        // 출력:
        // Apple: 5
        // Banana: 10
        // Orange: 7
    }
}

• TreeMap은 키를 정렬된 순서로 저장하는 Map이다.
• 이진 검색 트리 기반으로 동작하며, 키가 자동으로 오름차순으로 정렬된다.

 

LinkedHashMap 사용 예시

public class LinkedHashMapExample {
    public static void main(String[] args) {
        // LinkedHashMap 생성
        Map<String, Integer> map = new LinkedHashMap<>();
        
        // 데이터 추가
        map.put("Banana", 10);
        map.put("Apple", 5);
        map.put("Orange", 7);
        
        // 입력된 순서대로 데이터 출력
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
        // 출력:
        // Banana: 10
        // Apple: 5
        // Orange: 7
    }
}

• LinkedHashMap은 데이터가 입력된 순서 또는 접근된 순서대로 저장된다.
• 순서를 유지해야 하는 경우 유용하다.

 

Map 사용 시 중요한 점

1. Null 허용 여부:
   • HashMap: null 키와 null 값을 허용한다.
   • TreeMap: null 키를 허용하지 않으며, null 값을 허용할 수는 있지만 주의해야 한다.
   • LinkedHashMap: HashMap과 마찬가지로 null 키와 값을 허용한다.
2. 동일 키의 처리:
   • Map은 동일한 키를 중복해서 저장할 수 없다. 동일한 키로 값을 다시 저장하면, 이전 값이 덮어쓰여진다.
3. 해시 충돌:
   • HashMap은 키의 해시 값을 사용하여 데이터를 저장한다. 해시 충돌이 발생할 경우, 성능이 저하될 수 있다. 이를 해결하기 위해 자바에서는 내부적으로 체이닝과 같은 충돌 처리 방식을 사용한다.
4. 멀티스레드 환경에서의 사용:
   • HashMap은 스레드 안전하지 않으므로, 멀티스레드 환경에서는 ConcurrentHashMap을 사용하는 것이 좋다. ConcurrentHashMap은 스레드 간의 충돌을 방지하고, 동시에 안전하게 데이터를 처리할 수 있도록 설계된 Map 구현체이다.

정리

• Map은 키-값 쌍을 관리하는 매우 강력한 자료구조로, 다양한 상황에서 효율적인 데이터 검색과 저장이 가능하다.
• HashMap은 자바에서 가장 일반적으로 사용되는 Map 구현체로, 빠른 데이터 검색과 삽입이 가능하다.
• TreeMap은 정렬된 순서로 데이터를 저장해야 하는 경우 유용하다.
• LinkedHashMap은 입력된 순서를 유지해야 할 때 사용된다.
• 장점으로는 빠른 검색 속도와 유연성을 꼽을 수 있다.
• 단점으로는 메모리 사용량 증가와 멀티스레드 환경에서의 주의가 필요하다.
• Map을 사용할 때는 null 처리, 해시 충돌, 멀티스레드 환경에서의 고려 사항을 염두에 두어야 한다.

---

 

HashMap과 HashTable의 차이점

두 용어는 종종 혼용되지만, 자바에서 둘의 차이를 명확하게 구분하는 몇 가지 중요한 차이점이 있다.

• 해시 테이블(Hash Table)은 일반적인 자료구조의 개념이고, 해시 맵(HashMap)은 자바에서 제공하는 특정 구현체이다.
• 또는 아래와 같은 차이점들이 있다.

특징	Hash Table	HashMap
자료구조 개념	해시 테이블은 자료구조의 일반적인 개념이다.	HashMap은 자바에서 제공하는 구체적 구현체이다.
스레드 안전성	스레드 안전(Thread-safe)한 구현체가 많다.	스레드 안전하지 않음, 멀티스레드 환경에서 추가 처리가 필요하다.
null 허용 여부	키와 값 모두 null 허용하지 않음	null 키와 값 허용 (단, 키는 1개만 허용)
멀티스레드 환경에서의 사용	기본적으로 스레드 안전성을 보장한다.	멀티스레드 환경에서는 ConcurrentHashMap을 사용해야 함

---