[JAVA] - Hash, HashTable (≒ HashMap)

Hash

임의의 크기의 데이터(Key)를 고정된 크기의 데이터(Value)로 저장하는 구조이다.

Key의 Hash값을 사용하여 값을 저장하고, Key-Value 개수에 따라 동적으로 크기가 증가하는 associative array이다.

(associative : Key하나와 Value하나가 연관되어 있으며(1:1 구조), Key를 통해 연관되는 값을 얻을 수 있는 자료구조)

Key에 대한 Hash값을 구하는 과정을 해싱(Hashing)이라고 하며, 이때 사용하는 함수를 해시함수라고 한다.

Hash의 장점으로 Hash값 자체를 index로 사용하기 때문에 평균 시간복잡도가 O(1)로 매우 빠르다.

 

Hash Table (≒ Hash Map)

Map 인터페이스를 구현한 컬렉션으로 Key와 Value가 짝으로 구성된 Entry 객체를 저장하는 구조를 가지는 자료구조이다.

해시값을 인덱스 삼아 해시테이블에 저장하고, 특정 데이터의 저장위치를 Hash함수로 바로 알 수 있기 때문에 데이터의 검색, 추가, 삭제 속도가 빠르다.

Key는 중복 저장이 불가능하지만 Value는 중복 저장이 가능하다. Key값이 다르면 동일한 Value값을 중복적으로 저장이 가능하다는 뜻이다. 만약 기존에 저장된 Key로 값을 저장하게 되면 기존 값은 없어지고 새로운 값이 저장된다.

 

 

해시 테이블과 해시 맵은 Map 인터페이스를 구현하여 사용법이 거의 동일하지만 차이점이 존재한다.

해시 테이블 VS 해시 맵

해시 테이블은 Key값에 null을 사용할 수 없지만, 해시 맵은 Key값에 null을 사용할 수 있다.

해시 테이블은 Thread-safe 하여 멀티스레드 환경에서 성능이 좋고, 해시 맵은 Thread-safe 하지 않아 싱글 스레드 환경에서 성능이 좋다.

(Thread-safe : 클래스나 객체에 여러 스레드가  동시에 접근해도, 프로그램 실행에 문제가 없는 상태)

 

해시 충돌

서로 다른 키 값이 해시함수를 거쳐 동일한 해시 값으로 지정되어 있는 경우를 말한다.

 

Hash Table에 key1 데이터가 들어가있는 상황에서 key2의 해시값이 key1과 동일한 상황

 

해시 충돌은 개방 주소법과 분리 연결법을 사용하여 해결할 수 있다.

 

개방 주소법 (Open Address)

해시 값 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장하는 방식

hash와 value가 1대1 관계 유지, 비어 있는 공간 탐색 방법에 따라 분류 (선형 탐사법, 제곱 탐사법, 이중 해싱)

 

① 선형 탐사법 (Linear Probing) 

충돌 발생 지점 부터 이후의 빈 공간을 순차적으로 탐사하는 방법

반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 일차 군집화 문제가 발생한다.

 

 

② 제곱 탐사법 (Quadratic Probing)

충돌 발생 지점 부터 이후의 빈 공간을 n제곱 간격으로 탐사

일차 군집화 문제를 일부 보완하지만 이차 군집화 문제 발생 가능성이 있다.

 

 

 

③ 이중 해싱 : Double Hashing

해싱 함수를 이중으로 사용하는 방법으로 하나의 해시 함수에서 충돌이 발생하면 2차 해시 함수를 이용해 검색 이동 거리를 얻는 방식이다.

 - 해시 함수 1 : 최초 해시를 구할 때 사용

 - 해시 함수 2 : 충돌 발생 시, 탐사 이동 간격을 구할 때 사용

선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포된다.

 

 

 

분리 연결법 (Separate Chaining)

해시 테이블을 연결 리스트로 구성하는 방법

충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결한다.

 

 

 

기본 해시 맵 사용 방법

대부분 싱글 스레드 환경을 가지므로 해시 테이블 대신 해시맵으로 사용을 했다.

 

import java.util.HashMap;   // HashMap 클래스 import
import java.util.Map;       // Map 인터페이스 import

public class Main{
    public static void main(String[] args) {

// HashMap 생성
        HashMap<String, Integer> map = new HashMap<String, Integer>();

// HashMap에 데이터 추가
        map.put("임동현",27);
        map.put("미니언",7);

// HashMap에 포함된 key, value 값을 호출
        for (Map.Entry<String, Integer> item : map.entrySet()) {
            System.out.println("키값: " + item.getKey() + " / 해시값: " + item.getValue());
        }

// HashMap에 Key값 검색
        if(map.containsKey("임동현")){
            System.out.println("존재");
        } // 찾고자하는 Key값이 있으면 true값, 없으면 false 반환

    }
}