[자료구조] 5. 해시(Hash) - HashMap

728x90

 

해시 특징

1. 해시 테이블(Hash Table)

Key(키)와 Value(데이터)가 매핑되는 데이터 구조이다.

Key(with 해시함수)를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있다.

따라서 배열 또는 연결 리스트(Linked List)와 비교했을 때, 저장 및 탐색 속도가 획기적으로 빨라진다. 

※ cf) 연결 리스트(Linked List)는 head부터 찾아나가야한다.

 

미리 해시 함수가 생성할 수 있는 주소에 대한 공간(Slot)을 할당한 후 Key에 따른 데이터 저장 및 탐색을 지원한다.

• Slot(슬롯): 해시 테이블에서 한 개의 데이터를 저장할 수 있는 공간을 뜻한다.

 

이미지 출처: https://www.javatpoint.com/hash-table

 

2. 해시 함수(Hash Function)

Key를 넣으면 해당 Key를 저장할 수 있는 주소를 리턴해준다.

※ cf) 원래는 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수를 의미한다. ex) 블록체인 기술에서도 쓰임.

• 해시(Hash) / 해시 값(Hash Value) / 해시 주소(Hash Address): 해싱 함수를 통해 리턴된 고정된 길이의 값을 뜻한다.

 

해시테이블의 장단점과 주요 용도

2-1. 장점

- 데이터 저장/읽기(검색) 속도가 빠르다.

- 키에 대한 데이터가 있는 지, 즉 중복 확인이 쉽다.

 

2-2. 단점

- 일반적으로 저장공간이 더 많이 필요하다.

- 여러 키에 해당하는 주소가 동일할 경우의 충돌을 피하기 위해서 별도 자료구조가 필요하다.

 

2-3. 주요 용도

- 검색이 많이 필요한 경우

- 저장, 삭제, 읽기가 빈번한 경우

- 캐시 구현 시(중복 확인이 쉽기 때문)

 

충돌(Collision) 해결을 위한 알고리즘

해시 테이블의 가장 큰 문제는 충돌(Collision)이다.

 

3-1. Chaining 기법

해시 테이블 저장공간 외의 공간을 활용하는 기법으로, 개방 해싱(Open Hashing) 기법 중 하나이다.

충돌 발생 시, Linked List 자료구조를 사용하여 데이터를 추가로 뒤에 연결시켜 저장하는 기법이다.

 

3-2. Linear Probing 기법

해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법으로, 폐쇄 해싱(Close Hashing) 기법 중 하나이다.

충돌 발생 시, 해당 Hash Address(또는 Hash Value / Hash) 후의 다음 빈 공간인 address에 저장하는 기법이다.

• 저장공간 활용도를 높이기 위한 기법이다.

 

HashMap 선언 및 메소드

HashMap은 JAVA Collection Framework에 속한 클래스이다.

이는 해시 테이블 구조를 활용하여 구현되었다.

 

시간복잡도

• 충돌이 없는 일반적인 경우: O(1)
• 충돌이 있는 최악의 경우: O(n) → cf) Chaining, Linear Probing 기법 둘 다 동일

- put()
- get(key)
- keySet()

 

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        
        // HashMap 선언
        HashMap<Integer, String> hM = new HashMap<>();
        HashMap<String, String> hM2 = new HashMap<>();

        // 값 추가
        hM.put(1, "banana");
        hM.put(2, "apple");
        hM.put(3, "tomato");
        
        hM2.put("apple", "a");
        hM2.put("banana", "b");

        // 값 읽기
        System.out.println(hM.get(1)); // banana
        System.out.println(hM2.get("banana")); // b
        
        // keySet()
        System.out.println(hM.keySet()); // [1, 2, 3]
        System.out.println(hM2.keySet()); // [banana, apple]
    }
}