[Java] 컬렉션 프레임워크의 HashSet과 HashMap, HashTable과 Hashing이란

자바의 컬렉션 프레임워크인 HashSet, Hash Map과 HashTable과 Hashing에 대한 개념을 작성한 글입니다.

 

HashSet

 HashSet은 자바 컬렉션 프레임워크(Collection Framework)에서 제공하는 Set 인터페이스를 구현한 클래스 중 하나입니다. Set의 특징대로 HashSet은 중복된 요소를 저장하지 않습니다. 또한 저장 순서를 유지하지 않으므로 저장 순서를 유지하고자 한다면 LinkedHashSet을 이용해야 합니다.

 

HashSet은 해시 테이블을 기반으로 하기 때문에 해시 함수에 의해 요소들이 저장되는 공간인 버킷(Bucket)으로 구성됩니다. 요소의 해시 코드를 계산하여 해당하는 버킷에 요소를 저장하고, 동일한 해시 코드를 가진 요소는 동일한 버킷에 저장됩니다. 따라서 HashSet에서 요소의 추가, 제거, 검색 연산은 요소의 해시 코드를 계산하여 해당하는 버킷에서만 수행하므로 상수 시간에 이루어집니다.

 

HashSet에 새로운 요소를 추가할 때는 add 메서드나 addAll 메서드를 사용하는데, 만일 HashSet에 이미 저장되어 있는 요소와 중복된 요소를 추가하고자 한다면 이 메서드들은 false를 반환함으로써 중복된 요소이기 때문에 추가에 실패했다는 것을 알립니다. 

 

그럼 중복인 요소는 어떻게 알 수 있을까요? HashSet의 add 메서드는 새로운 요소를 추가하기 전에 기존에 저장된 요소와 같은 것으인지 판별하기 위해 추가하려는 요소의 equals()와 hashCode()를 호출하기 때문에 equals()와 hashCode()를 목적에 맞게 오버라이딩 해야 합니다.

특징

1. 중복 허용 안 함: HashSet은 중복된 요소를 허용하지 않습니다. 따라서 동일한 요소를 여러 번 추가해도 내부적으로는 하나의 요소만 유지됩니다. 
2. 순서가 없음: HashSet은 요소들의 순서를 보장하지 않습니다. 즉, 요소가 추가된 순서대로 저장되지 않으며, 반복문을 통해 요소를 순회할 때 예상한 순서대로 요소가 반환되지 않을 수 있습니다.
3. 빠른 검색, 추가, 제거 연산: HashSet은 내부적으로 해시 함수를 사용하여 요소를 저장하므로, 검색, 추가, 제거 연산이 평균적으로 상수 시간(O(1))에 이루어집니다. (하지만 해시 충돌이 일났을 땐 O(n)의 
4. 동기화 지원하지 않음: HashSet은 스레드 안전하지 않습니다. 따라서 멀티스레드 환경에서 사용할 때는 동기화 처리가 필요합니다. 동기화를 지원하는 HashSet의 대안으로는 ConcurrentHashMap을 사용할 수 있습니다.
5. null 요소 허용: HashSet은 null 값을 요소로 허용합니다. 따라서 null을 추가할 수 있고, null을 포함하는 HashSet을 생성할 수 있습니다.

예제 코드

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        // HashSet 객체 생성
        HashSet<String> wordSet = new HashSet<>();

        // 문자열 배열에 단어 추가
        String[] words = {"apple", "banana", "orange", "apple", "grape", "banana", "kiwi"};

        // HashSet에 단어 추가
        for (String word : words) {
            wordSet.add(word);
        }

        // 중복된 단어가 제거된 HashSet 출력
        System.out.println("유일한 단어 목록:");
        for (String word : wordSet) {
            System.out.println(word);
        }
    }
}

위 예제 코드의 출력 결과로는 

 

유일한 단어 목록:
banana
grape
kiwi
orange
apple

HashMap

HashMap은 자바 컬렉션 프레임워크(Collection Framework)에서 제공하는 Map 인터페이스를 구현한 클래스 중 하나입니다. HashMap은 키(key)와 값(value)으로 이루어진 데이터를 저장하는 자료구조로, 특정 키를 사용하여 값을 검색하거나 저장할 수 있습니다. HashMap은 해시 테이블(Hash Table)을 기반으로 구현되어 있어서 매우 빠른 검색, 삽입, 삭제 연산을 제공합니다.

 

사실 앞서 소개한 HashSet도 내부적으로 HashMap으로 구현되어 있습니다.

특징

1. 키-값 쌍 저장: HashMap은 키와 값의 쌍으로 이루어진 데이터를 저장합니다. 각 키는 고유해야 하며, 중복된 키는 허용되지 않습니다. 값은 중복되어도 상관없습니다.
2. 해시 테이블 기반: HashMap은 내부적으로 해시 테이블을 사용하여 데이터를 저장합니다. 이는 매우 빠른 검색, 삽입, 삭제 연산을 가능하게 합니다. 평균적으로 이러한 연산들은 상수 시간(O(1))에 이루어집니다.
3. 동기화 지원하지 않음: HashMap은 스레드 안전하지 않습니다. 따라서 멀티스레드 환경에서 사용할 때는 동기화 처리가 필요합니다. 동기화를 지원하는 HashMap의 대안으로는 ConcurrentHashMap을 사용할 수 있습니다.
4. null 허용: HashMap은 키와 값으로 null을 허용합니다. 따라서 null을 키나 값으로 사용할 수 있습니다.
5. 순서가 없음: HashMap은 내부적으로 해시 테이블을 사용하기 때문에 저장된 요소들의 순서를 보장하지 않습니다. 따라서 저장된 순서대로 요소를 접근할 수 없습니다.

예제 코드

import java.util.HashMap;

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

        // 키-값 쌍 추가
        hashMap.put("apple", 100);
        hashMap.put("banana", 200);
        hashMap.put("orange", 150);

        // 값 검색
        int value = hashMap.get("banana");
        System.out.println("banana의 값: " + value);

        // 키가 존재하는지 확인
        boolean containsKey = hashMap.containsKey("apple");
        System.out.println("apple이 존재하는가? " + containsKey);

        // 키-값 쌍 제거
        hashMap.remove("orange");

        // 모든 키-값 쌍 출력
        System.out.println("HashMap의 모든 요소:");
        for (String key : hashMap.keySet()) {
            System.out.println("키: " + key + ", 값: " + hashMap.get(key));
        }
    }
}

 

로드 팩터와 리해싱

로드 팩터와 리해싱은 해시맵과 해시셋의 성능과 동적 크기 조정에 관하여 매우 중요한 개념입니다.

 

로드 팩터 (Load Factor)

로드 팩터 = (현재 요소 개수) / (해시 테이블 크기)

 

로드 팩터가 1에 가까울수록 해시 테이블이 많이 채워져 있고, 충돌이 발생할 가능성이 높아집니다. 따라서 로드 팩터가 너무 높으면 해시 테이블의 성능이 저하될 수 있습니다.

 

로드 팩터는 해시맵이 얼마나 채워져 있는지를 나타내는 지표입니다. 보통 로드 팩터는 0.75로 설정됩니다.

 

리해싱

리해싱은 해시맵이 로드 팩터를 기준으로 자동으로 크기를 조정하는 과정을 말합니다. 해시맵이 로드 팩터의 임계값을 초과하면(예: 0.75), 해시맵은 내부적으로 크기를 두 배로 확장합니다. 이 과정에서 모든 요소는 새로운 크기의 배열에 다시 해싱됩니다. 이렇게 하면 해시 충돌이 줄어들고 성능이 유지됩니다. 반대로 해시맵이 로드 팩터의 하한값 미만으로 요소를 제거하면, 해시맵은 크기를 축소할 수도 있습니다.

 

 

자바에서는 해시맵과 해시셋의 생성자에서 로드 팩터 값을 지정할 수 있습니다.

 

해싱과 해시함수

해싱(Hashing)이란 해시 함수(hash function)를 이용해서 데이터를 해시 테이블(hash table)에 저장하고 검색하는 기법을 말합니다. 해시 함수는 데이터가 저장되어 있는 곳을 알려 주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있습니다.

 

해싱을 구현한 컬렉션 클래스로는 HashSet, HashMap, Hashtable 등이 있습니다.

 

해싱에서 사용하는 자료구조는 배열이랑 링크드 리스트의 조합으로 되어 있습니다. 저장할 데이터의 키를 해시 함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결되어 있는 링크드 리스트에 저장하면 됩니다.

 

하지만 링크드 리스트는 검색에 불리한 자료구조이기 때문에 링크드 리스트의 크기가 커질수록 검색 속도가 떨어지게 됩니다. 반면에 배열은 배열의 크기가 커져도 원하는 요소가 몇 번째에 있는지만 알면 아래의 공식에 의해 빠르게 원하는 값을 찾을 수 있습니다.

 

배열의 인덱스가 n인 요소의 주소 = 배열의 시작 주소 + type의 size * n

 

즉, 하나의 배열 요소에 긴 링크드 리스트가 저장되어 있는 형태보단 많은 서랍에 하나의 데이터만 저장되어 있는 형태가 더 빠른 검색결과를 얻을 수 있습니다. 

 

하나의 링크드 리스트에 최소한의 데이터만 저장되려면, 저장될 데이터의 크기를 고려해서 HashMap의 크기를 적절하게 지정해주어야 하고, 해시함수가 서로 다른 키에 대해 중복된 해시코드의 반환을 최소화해야 합니다. 그래야 HashMap에서 빠른 검색시간을 얻을 수 있다. 따라 해싱을 구현하는 과정에서 제일 중요한 것은 해시 함수의 알고리즘입니다.

 

자바에서는 Object 클래스에 정의된 hashCode()를 사용합니다. Object 클래스에서 정의된 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어내기 때문에 모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일한 훌륭한 방법이 됩니다.