해시맵( HashMap )과 집합( Set ) 구현

1. 해시맵(HashMap)이란?

해시맵(HashMap)은 키-값 쌍을 저장하는 자료 구조입니다. 각 키는 해시 함수를 통해 계산된 해시 값에 따라 특정 위치에 저장됩니다. 해시맵의 핵심 아이디어는 데이터의 접근 속도를 빠르게 하기 위해 특정 인덱스를 통해 요소에 접근하는 것입니다. 이 구조는 매우 빠른 검색, 삽입, 삭제 속도를 제공하며, 일반적으로 시간 복잡도가 평균적으로 O(1)입니다.

해시맵의 구조

해시맵은 내부적으로 배열과 연결 리스트의 조합으로 이루어져 있습니다. 해시 함수를 사용하여 키에 대한 해시 값을 계산하고, 해당 값을 배열의 인덱스로 사용합니다. 충돌을 방지하기 위해 체이닝(Chaining)이나 개방 주소법(Open Addressing) 등의 충돌 해결 기법을 사용합니다.

2. 집합(Set)이란?

집합(Set)은 중복되지 않는 원소들의 모임을 의미합니다. 수학적인 개념과 유사하게, 집합 자료 구조에서는 중복을 허용하지 않으며, 순서는 중요하지 않습니다. 해시맵과 비슷한 구조를 활용하여 원소들의 빠른 삽입과 삭제를 가능하게 합니다.

집합의 구조

집합은 내부적으로 해시맵과 유사하게 동작합니다. 일반적으로 집합은 해시맵의 키 부분만을 사용하여 데이터를 관리합니다. 이로 인해 중복된 원소를 자동으로 제거하며, 빠른 삽입과 검색이 가능합니다.

3. Java로 해시맵 구현하기

Java에서는 HashMap 클래스가 이미 제공되고 있지만, 학습 목적으로 간단한 해시맵을 직접 구현해 보겠습니다. 해시맵 구현의 기본 원리는 해시 함수, 배열, 그리고 충돌 해결 기법입니다.

import java.util.LinkedList;

class HashMap<K, V> {
    private class Entry<K, V> {
        K key;
        V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int SIZE = 16;
    private LinkedList<Entry<K, V>>[] buckets;

    public HashMap() {
        buckets = new LinkedList[SIZE];
        for (int i = 0; i < SIZE; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    private int getBucketIndex(K key) {
        return Math.abs(key.hashCode() % SIZE);
    }

    public void put(K key, V value) {
        int index = getBucketIndex(key);
        LinkedList<Entry<K, V>> bucket = buckets[index];

        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }

        bucket.add(new Entry<>(key, value));
    }

    public V get(K key) {
        int index = getBucketIndex(key);
        LinkedList<Entry<K, V>> bucket = buckets[index];

        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }

        return null;
    }

    public void remove(K key) {
        int index = getBucketIndex(key);
        LinkedList<Entry<K, V>> bucket = buckets[index];

        bucket.removeIf(entry -> entry.key.equals(key));
    }
}

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("One", 1);
        map.put("Two", 2);
        System.out.println(map.get("One"));  // 출력: 1
        map.remove("One");
        System.out.println(map.get("One"));  // 출력: null
    }
}

4. C로 해시맵 구현하기

C 언어에서는 해시맵을 구현하기 위해 배열과 연결 리스트를 직접 사용합니다. 아래는 간단한 해시맵 구현 예제입니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 16

typedef struct Entry {
    char* key;
    int value;
    struct Entry* next;
} Entry;

Entry* buckets[SIZE];

unsigned int hash(const char* key) {
    unsigned int hash = 0;
    while (*key) {
        hash = (hash << 5) + *key++;
    }
    return hash % SIZE;
}

void put(const char* key, int value) {
    unsigned int index = hash(key);
    Entry* newEntry = (Entry*)malloc(sizeof(Entry));
    newEntry->key = strdup(key);
    newEntry->value = value;
    newEntry->next = buckets[index];
    buckets[index] = newEntry;
}

int get(const char* key) {
    unsigned int index = hash(key);
    Entry* entry = buckets[index];
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            return entry->value;
        }
        entry = entry->next;
    }
    return -1; // 값이 없을 경우
}

void removeKey(const char* key) {
    unsigned int index = hash(key);
    Entry* entry = buckets[index];
    Entry* prev = NULL;
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            if (prev == NULL) {
                buckets[index] = entry->next;
            } else {
                prev->next = entry->next;
            }
            free(entry->key);
            free(entry);
            return;
        }
        prev = entry;
        entry = entry->next;
    }
}

int main() {
    put("One", 1);
    put("Two", 2);
    printf("%d\n", get("One"));  // 출력: 1
    removeKey("One");
    printf("%d\n", get("One"));  // 출력: -1
    return 0;
}

5. 집합(Set) 구현

집합 자료 구조는 해시맵과 유사한 방식으로 구현할 수 있습니다. 실제로 Java의 HashSet은 내부적으로 HashMap을 사용하여 중복되지 않는 값을 관리합니다. 여기서는 집합을 해시맵을 사용하여 구현하는 간단한 예제를 보여줍니다.

Java로 집합 구현하기

import java.util.LinkedList;

class HashSet<K> {
    private final int SIZE = 16;
    private LinkedList<K>[] buckets;

    public HashSet() {
        buckets = new LinkedList[SIZE];
        for (int i = 0; i < SIZE; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    private int getBucketIndex(K key) {
        return Math.abs(key.hashCode() % SIZE);
    }

    public void add(K key) {
        int index = getBucketIndex(key);
        LinkedList<K> bucket = buckets[index];

        if (!bucket.contains(key)) {
            bucket.add(key);
        }
    }

    public boolean contains(K key) {
        int index = getBucketIndex(key);
        LinkedList<K> bucket = buckets[index];
        return bucket.contains(key);
    }

    public void remove(K key) {
        int index = getBucketIndex(key);
        LinkedList<K> bucket = buckets[index];
        bucket.remove(key);
    }
}

public class MainSet {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("One");
        set.add("Two");
        System.out.println(set.contains("One"));  // 출력: true
        set.remove("One");
        System.out.println(set.contains("One"));  // 출력: false
    }
}

C로 집합 구현하기

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int elements[MAX_SIZE];
    int size;
} Set;

void initSet(Set *set) {
    set->size = 0;
}

bool contains(Set *set, int element) {
    for (int i = 0; i < set->size; i++) {
        if (set->elements[i] == element) {
            return true;
        }
    }
    return false;
}

void add(Set *set, int element) {
    if (!contains(set, element) && set->size < MAX_SIZE) {
        set->elements[set->size++] = element;
    }
}

void removeElement(Set *set, int element) {
    for (int i = 0; i < set->size; i++) {
        if (set->elements[i] == element) {
            set->elements[i] = set->elements[set->size - 1];
            set->size--;
            return;
        }
    }
}

void printSet(Set *set) {
    printf("{ ");
    for (int i = 0; i < set->size; i++) {
        printf("%d ", set->elements[i]);
    }
    printf("}\n");
}

int main() {
    Set mySet;
    initSet(&mySet);

    add(&mySet, 10);
    add(&mySet, 20);
    add(&mySet, 30);
    printSet(&mySet);  // 출력: { 10 20 30 }

    add(&mySet, 20);  // 이미 존재하므로 추가되지 않음
    printSet(&mySet);  // 출력: { 10 20 30 }

    removeElement(&mySet, 20);
    printSet(&mySet);  // 출력: { 10 30 }

    return 0;
}

6. 결론

해시맵과 집합은 매우 유용한 자료 구조로, 효율적인 데이터 검색, 삽입, 삭제를 가능하게 합니다. Java와 C로 직접 구현해 보면서 해시 함수, 충돌 해결 기법, 그리고 배열과 연결 리스트를 사용하는 방법을 익힐 수 있었습니다. 이러한 자료 구조들은 실무에서 자주 사용되며, 그 원리를 이해하는 것은 매우 중요합니다.

해시맵은 키-값 쌍을 관리하는 데 유용하고, 집합은 중복을 허용하지 않는 데이터 집합을 관리하는 데 적합합니다. 직접 구현한 예제를 통해 이들의 기본 동작 원리와 사용 방법을 이해할 수 있었길 바랍니다.