Hash Table, Hash Map

해싱이란?

https://www.fun-coding.org/DS&AL1-6.html

 

해싱은 데이터를 고정된 크기의 해시 값으로 변환하는 과정을 말한다. 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 이 때, 산술적인 연산을 hash function이라고 한다.

 

오늘은 Java의 클래스 중 해싱을 사용한 자료구조에 대해 다뤄보기로 한다.

 

HashTable, HashMap

 

HashTable

1. 정의: HashTable은 키와 값이 연관된 데이터를 저장하는데 사용되는 동기화된(synchronized) 컬렉션 클래스이다.
2. 특징:
   • 동기화: HashTable은 스레드 안전(thread-safe)이다. 여러 스레드가 동시에 HashTable을 사용할 수 있으며, 일관된 상태를 유지한다.
   • null 값을 허용하지 않음: HashTable은 키나 값으로 null을 허용하지 않는다.
   • 레거시 클래스: HashTable은 초기 자바 버전에서부터 제공되었으며, 현재는 HashMap에 의해 대체되는 추세이다.

HashTable의 시간복잡도는 평균적으로 

HashMap

1. 정의: HashMap은 키와 값이 연관된 데이터를 저장하는데 사용되는 비동기화(un-synchronized) 컬렉션 클래스이다.
2. 특징:
   • 비동기화: HashMap은 기본적으로 스레드 안전하지 않다. 여러 스레드가 동시에 액세스할 경우 외부 동기화가 필요하다.
   • null 값을 허용: HashMap은 하나의 null 키와 여러 null 값들을 허용한다.
   • 성능: HashTable에 비해 더 나은 성능을 제공하는데, 이는 HashMap이 동기화되지 않기 때문이다.

 

HashMap과 Hashtable 클래스의 차이점

 

1. Thread-safe 여부

• HashTable은 Thread-safe하고, HashMap은 Thread-safe하지 않다는 특징을 가지고 있기 때문에 멀티스레드 환경이 아니라면 Hashtable은 HashMap 보다 성능이 떨어진다는 단점을 가지고 있다.

2. Null 값 허용 여부

• HashTable은 key에 null을 허용하지 않지만, HashMap은 key에 null을 허용한다.

3. HashMap은 보조해시를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.

 

따라서, 우리는 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 해시테이블(HashTable)을 사용해야 하며, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시맵(HashMap)을 사용하면 된다.

 

 

HashTable의 시간복잡도

 

해시 테이블의 시간 복잡도는 일반적인 연산(삽입, 검색, 삭제)에 대해 평균적으로 O(1), 즉 상수 시간이 걸린다. 이는 해시 테이블이 키를 통해 직접적인 인덱스 접근을 제공하기 때문이다. 그러나 최악의 경우, 이 시간 복잡도는 O(n)이 될 수 있다. 여기서 n은 테이블에 저장된 요소의 수이다.

평균적인 경우 (Best and Average Case)

• 삽입 (Insertion): O(1)
• 검색 (Search): O(1)
• 삭제 (Deletion): O(1)

해시 테이블에서의 이러한 연산들은 대부분 해시 함수를 통해 해당 키에 대한 인덱스를 계산하고, 해당 인덱스에 직접 접근하여 연산을 수행한다. 이 과정은 일반적으로 상수 시간이 걸린다.

최악의 경우 (Worst Case)

• 삽입 (Insertion): O(n)
• 검색 (Search): O(n)
• 삭제 (Deletion): O(n)

최악의 경우는 모든 키가 같은 해시 값을 가질 때 발생한다. 이 경우, 해시 테이블의 모든 요소가 단일 연결 리스트나 버킷에 저장되어, 해시 테이블의 이점이 사라진다. 따라서 연산은 일반적인 리스트 탐색과 같은 성능을 보이게 되어, 시간 복잡도가 O(n)이 된다.

 

이외에도, 해쉬 함수의 성능이나 충돌 전략, 혹은 아래서 다룰 Load Factor 또한 HashTable의 성능에 영향을 끼친다. 

 

 

 

초기 용량과 로드 팩터

 

초기 용량 (Initial Capacity)

초기 용량은 해시 테이블이 생성될 때 내부적으로 할당되는 버킷(또는 슬롯)의 수이다. 이 값이 클수록 더 많은 데이터를 저장할 수 있지만, 메모리 사용량도 그만큼 늘어난다.

 

로드 팩터 (Load Factor)

로드 팩터는 해시 테이블의 용량이 얼마나 차면 크기를 재조정(resize)할 것인지를 결정하는 지표이다. 이 값은 0과 1 사이의 수로, 해시 테이블이 얼마나 가득 차 있을 때 크기 조정을 시작할지를 나타낸다.

 

버킷 하나에 여러 개의 값을 가지는 것, 즉 충돌을 피하기 위해서 설정한 것이다.

버킷의 75퍼가 찼다면 용량을 2배로 늘리는 과정이 일어나는데, 그 과정에서 원래 버킷의 값들을 새로운 버킷에 옮기는 과정이 일어난다. (자주 일어난다면 성능에 좋지 않다.)

한마디로 로드 팩터는 언제 용량을 재 설정을 해주어야 효율적인지에 대한 초기 설정 값이라고 생각하면 된다. (그래서 초기용량, 로드팩터를 처음에 잘 설정하는 것이 중요하다.)

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    final float loadFactor;

    public HashMap(int initialCapacity, float loadFactor) {

    }

    public HashMap(int initialCapacity) {
    }

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
}

 

 

HashMap 내부 코드를 보면 위와 같이 생성자를 통해서 초기 용량, 로드 팩터를 설정할 수도 있다.

 

HashTable의 초기 용량은 11, 로드 팩터는 0.75이다.

HashMap, HashSet의 초기 용량은 16, 로드팩터는 0.75 이다.