[바미] 자료구조 - 해시맵(HashMap)

해시맵(HashMap)?

키-값(Key-Value) 쌍을 저장하는 자료구조입니다. 빠른 검색, 삽입, 삭제를 가능하게 하며, 데이터의 중복을 허용하지 않는 특징이 있죠.

해시맵은 해시 함수(Hash Function)를 사용하여 키를 해시 코드(Hash Code)로 변환하고, 이를 배열 인덱스로 사용하여 값을 저장합니다.

---

해시맵의 주요 특징

키-값 쌍 저장

해시맵은 키와 값의 쌍으로 데이터를 저장합니다. 각 키는 고유하며, 키를 통해 해당 값을 빠르게 검색할 수 있습니다.

해시 함수

해시맵은 해시 함수를 사용하여 키를 해시 코드로 변환하고, 이 해시 코드를 배열의 인덱스로 사용하여 값을 저장합니다. 해시 함수는 입력 값(키)을 고정된 크기의 해시 코드로 변환하는 함수입니다.

빠른 검색

해시맵은 일반적으로 O(1)의 시간 복잡도로 검색, 삽입, 삭제가 가능합니다. 이는 해시 함수와 배열 인덱스를 사용하여 직접 접근하기 때문입니다.

체이닝

해시맵은 충돌(해시 코드가 동일한 경우)을 처리하기 위해 체이닝(Chaining) 기법을 사용할 수 있습니다. 체이닝은 동일한 해시 코드를 가지는 키-값 쌍들을 연결 리스트(Linked List)로 저장하는 방식입니다.

동적 크기 조정

해시맵은 내부적으로 배열의 크기를 동적으로 조정하여 해시 충돌을 줄이고 성능을 유지합니다. 일반적으로 배열이 일정 크기 이상으로 차면, 더 큰 배열로 재해시(Resize and Rehash)합니다.

---

해시맵의 주요 메서드

put(Key key, Value value)

해시맵에 키-값 쌍을 추가하며 키가 이미 존재하면 해당 키의 값을 업데이트 합니다.

get(Object key)

주어진 키에 대한 값을 반환하며 키가 존재하지 않으면 null을 반환합니다.

remove(Object key)

주어진 키에 대한 키-값 쌍을 제거하며 제거된 값을 반환하고, 키가 존재하지 않으면 null을 반환합니다.

size()

해시맵에 저장된 키-값 쌍의 수를 반환합니다.

isEmpty()

해시맵이 비어있는지 확인하고, 비어있으면 true, 그렇지 않으면 false를 반환합니다.

---

코드(Java)

이제 위에서 언급했던 메서드 중 몇 개만 만들어 간단하게 해시 맵(HashMap)을 구현하는 예제로 구현해보았습니다.

 

물론, 자바에서는

import java.util.HashMap;

으로 해시맵을 사용할 수 있지만 학습을 위해 만들어 보았습니다.

package example_6;

import java.util.LinkedList;

// 노드 클래스 정의
class HashNode<K, V> {
    K key; // 키
    V value; // 값

    // 다음 노드를 가리키는 참조 (체이닝)
    HashNode<K, V> next;

    // 노드 생성자
    public HashNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

// 해시 맵 클래스 정의
class HashMap<K, V> {
    private LinkedList<HashNode<K, V>>[] chainArray; // 체이닝을 위한 배열
    private int M = 11; // 기본 체인의 수 (소수 사용)
    private int size; // 해시 맵의 크기

    // 해시 맵 생성자
    public HashMap() {
        chainArray = new LinkedList[M];
        for (int i = 0; i < M; i++) {
            chainArray[i] = new LinkedList<>();
        }
        size = 0;
    }

    // 해시 함수
    private int hash(K key) {
        return Math.abs(key.hashCode() % M);
    }

    // 해시 맵에 키-값 쌍을 추가
    public void put(K key, V value) {
        int index = hash(key);
        LinkedList<HashNode<K, V>> chain = chainArray[index];

        // 키가 이미 존재하는지 확인
        for (HashNode<K, V> node : chain) {
            if (node.key.equals(key)) {
                node.value = value; // 값 업데이트
                return;
            }
        }

        // 키가 존재하지 않으면 새 노드를 체인에 추가
        HashNode<K, V> newNode = new HashNode<>(key, value);
        chain.add(newNode);
        size++;
    }

    // 해시 맵에서 값 검색
    public V get(K key) {
        int index = hash(key);
        LinkedList<HashNode<K, V>> chain = chainArray[index];

        // 체인에서 키를 검색
        for (HashNode<K, V> node : chain) {
            if (node.key.equals(key)) {
                return node.value; // 값 반환
            }
        }

        return null; // 키가 존재하지 않으면 null 반환
    }

    // 해시 맵에서 키-값 쌍 제거
    public V remove(K key) {
        int index = hash(key);
        LinkedList<HashNode<K, V>> chain = chainArray[index];

        // 체인에서 키를 검색
        for (HashNode<K, V> node : chain) {
            if (node.key.equals(key)) {
                V value = node.value;
                chain.remove(node);
                size--;
                return value; // 제거된 값 반환
            }
        }

        return null; // 키가 존재하지 않으면 null 반환
    }

    // 해시 맵의 크기 반환
    public int size() {
        return size;
    }

    // 해시 맵이 비어있는지 확인
    public boolean isEmpty() {
        return size == 0;
    }
}

// 메인 클래스
public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        // 해시 맵에 키-값 쌍 추가
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);

        // 해시 맵에서 값 검색
        System.out.println("Value for key 'one': " + map.get("one"));
        System.out.println("Value for key 'two': " + map.get("two"));
        System.out.println("Value for key 'three': " + map.get("three"));

        // 해시 맵에서 키-값 쌍 제거
        map.remove("two");
        System.out.println("Value for key 'two' after removal: " + map.get("two"));

        // 해시 맵의 크기 출력
        System.out.println("Size of map: " + map.size());

        // 해시 맵이 비어있는지 확인
        System.out.println("Is map empty? " + map.isEmpty());
    }
}

코드 설명

노드 클래스, 해시 맵 클래스, 메인 클래스로 나뉘어져 있는 구조입니다.

노드 클래스

class HashNode<K, V> {
    K key; // 키
    V value; // 값
    HashNode<K, V> next; // 다음 노드를 가리키는 참조 (체이닝)

    // 노드 생성자
    public HashNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

HashNode 클래스에서 해시 맵에서 사용하는 노드를 정의하였습니다.

각 노드는 키와 값 쌍을 가지며, 다음 노드를 가리키는 참조를 포함하고 있는데 이를 통해 체이닝을 구현하고 있죠.

---

해시 맵 클래스

class HashMap<K, V> {
    private LinkedList<HashNode<K, V>>[] chainArray; // 체이닝을 위한 배열
    private int M = 11; // 기본 체인의 수 (소수 사용)
    private int size; // 해시 맵의 크기

    // 해시 맵 생성자
    public HashMap() {
        chainArray = new LinkedList[M];
        for (int i = 0; i < M; i++) {
            chainArray[i] = new LinkedList<>();
        }
        size = 0;
    }

    // 해시 함수
    private int hash(K key) {
        return Math.abs(key.hashCode() % M);
    }

HashMap 클래스를 통해 해시 맵을 정의하였습니다. chainArray 변수는 체이닝을 위한 배열로, 각 요소를 LinkedList로 구성 시켰습니다.

M 변수는 기본 체인의 수로, 소수를 사용하여 충돌을 최소화해주고, size 변수는 해시 맵에 저장된 키-값 쌍의 수를 나타내었습니다.

키-값 쌍 추가 메소드

    // 해시 맵에 키-값 쌍을 추가
    public void put(K key, V value) {
        int index = hash(key);
        LinkedList<HashNode<K, V>> chain = chainArray[index];

        // 키가 이미 존재하는지 확인
        for (HashNode<K, V> node : chain) {
            if (node.key.equals(key)) {
                node.value = value; // 값 업데이트
                return;
            }
        }

        // 키가 존재하지 않으면 새 노드를 체인에 추가
        HashNode<K, V> newNode = new HashNode<>(key, value);
        chain.add(newNode);
        size++;
    }

해시 맵에 키-값 쌍을 추가하는 메서드 입니다.

hash 함수를 사용하여 키의 인덱스를 계산하고, 해당 체인에서 키가 이미 존재하는지 확인한 뒤, 키가 이미 존재하면 값을 업데이트하고, 존재하지 않으면 새 노드를 체인에 추가하는 형태로 동작합니다.

값 검색 메서드

// 해시 맵에서 값 검색
public V get(K key) {
    int index = hash(key);
    LinkedList<HashNode<K, V>> chain = chainArray[index];

    // 체인에서 키를 검색
    for (HashNode<K, V> node : chain) {
        if (node.key.equals(key)) {
            return node.value; // 값 반환
        }
    }

    return null; // 키가 존재하지 않으면 null 반환
}

해시 맵에서 키에 해당하는 값을 검색해주는 메서드입니다. 키의 인덱스를 계산하고, 해당 체인에서 키를 검색하여 값을 반환하고, 키가 존재하지 않으면 null을 반환하는 형태로 동작합니다.

키-값 쌍 제거

// 해시 맵에서 키-값 쌍 제거
public V remove(K key) {
    int index = hash(key);
    LinkedList<HashNode<K, V>> chain = chainArray[index];

    // 체인에서 키를 검색
    for (HashNode<K, V> node : chain) {
        if (node.key.equals(key)) {
            V value = node.value;
            chain.remove(node);
            size--;
            return value; // 제거된 값 반환
        }
    }

    return null; // 키가 존재하지 않으면 null 반환
}

해시 맵에서 키-값 쌍을 제거하는 메서드 입니다. 마찬가지로 키의 인덱스를 계산하고, 해당 체인에서 키를 검색하여 값을 반환하며, 키-값 쌍을 제거하고, 만약 키가 존재하지 않으면 null을 반환하는 형태로 동작합니다.

해시 맵 크기 반환 메서드

// 해시 맵의 크기 반환
public int size() {
    return size;
}

해시 맵에 저장된 키-값 쌍의 수를 반환하는 메서드입니다.

맵이 비었는 지 확인하는 메서드

// 해시 맵이 비어있는지 확인
public boolean isEmpty() {
    return size == 0;
}

해시 맵이 비어있는지 확인하는 메서드 입니다.

---

메인 클래스

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        // 해시 맵에 키-값 쌍 추가
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);

        // 해시 맵에서 값 검색
        System.out.println("Value for key 'one': " + map.get("one"));
        System.out.println("Value for key 'two': " + map.get("two"));
        System.out.println("Value for key 'three': " + map.get("three"));

        // 해시 맵에서 키-값 쌍 제거
        map.remove("two");
        System.out.println("Value for key 'two' after removal: " + map.get("two"));

        // 해시 맵의 크기 출력
        System.out.println("Size of map: " + map.size());

        // 해시 맵이 비어있는지 확인
        System.out.println("Is map empty? " + map.isEmpty());
    }
}

키 "one", "two", "three"에 대해 값을 추가하고 검색한 후, 키 "two"를 제거 후 해시 맵의 크기를 출력하고, 비어있는 지 확인하는 내용입니다.

 

아마 여기에서 반복문을 사용하여 HashMap을 생성하거나, 다른 타입으로 만들어 보시는 등의 시도를 하시면 해시맵을 이해하시는 데 더욱 도움이 되실 겁니다.