해시(Hash) 자료구조(C언어,STL, Java, Python 예시코드 포함)

해시(Hash)

 

 

 해시 자료구조(Hash Data Structure)는 데이터 검색, 삽입, 삭제 작업을 빠르게 수행할 수 있는 매우 효율적인 자료구조입니다. 많은 프로그램과 애플리케이션에서 사용되며, 특히 키-값(key-value) 쌍 데이터를 저장하고 빠르게 접근해야 하는 경우에 유용합니다. 또한 값 추가, 삭제, 조회의 시간복잡도가 O(1)이라서 코딩테스트 문제에도 많이 활용되고 있습니다.

---

1. 해시의 개념

해시는 키(key)와 값(value)의 쌍으로 데이터를 저장합니다. 각 키는 고유하며, 해시 함수(hash function)를 사용하여 특정 키가 저장될 위치를 결정합니다. 이 과정은 다음과 같습니다:

1. 키를 입력값으로 해시 함수를 호출됩니다.
2. 해시 함수는 키를 고유한 해시 값(hash value)으로 변환합니다.
3. 이 해시 값을 기반으로 데이터가 저장될 인덱스(버킷)를 결정합니다.

이 방식으로 데이터를 저장하면, 키를 이용해 데이터를 빠르게 검색할 수 있습니다.

---

 

2. 해시의 원리

해시 자료구조의 주요 원리는 해시 함수와 충돌 처리입니다.

반응형

해시 함수 (Hash Function)

해시 함수는 입력 데이터를 고정된 크기의 해시 값으로 변환합니다. 해시 함수는 다음과 같은 특성을 가져야 합니다:

• 결정적: 같은 입력값은 항상 같은 해시 값을 반환해야 합니다.
• 균등 분포: 해시 값이 가능한 한 균등하게 분포되어야 합니다.
• 빠른 계산: 해시 값 계산 속도가 빨라야 합니다.

충돌 처리 (Collision Handling)

서로 다른 키가 같은 해시 값을 가질 수 있는 경우를 충돌(collision)이라고 합니다. 충돌된 경우 체이닝 또는 오픈 주소법으로 충돌을 해결합니다.

1. 체이닝(Chaining): 같은 해시 값에 여러 개의 키-값 쌍을 연결 리스트로 저장합니다.
2. 오픈 주소법(Open Addressing): 충돌 시 다른 빈 슬롯(배열의 다음 인덱스)을 찾아 데이터를 저장합니다.

---

 

3. 예시코드

C 언어에서의 해시 구현 예제

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

#define TABLE_SIZE 10

typedef struct Node {
    char* key;
    char* value;
    struct Node* next;
} Node;

Node* hashTable[TABLE_SIZE];

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

void insert(const char* key, const char* value) {
    unsigned int index = hashFunction(key);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->value = strdup(value);
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

char* search(const char* key) {
    unsigned int index = hashFunction(key);
    Node* node = hashTable[index];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return NULL;
}

int main() {
    insert("name", "Alice");
    insert("age", "25");

    printf("name: %s\n", search("name"));
    printf("age: %s\n", search("age"));

    return 0;
}

---

 

C언어 STL 해시 구현 예제

#include <stdio.h>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, string> hashTable;

    // 데이터 삽입
    hashTable["name"] = "Alice";
    hashTable["age"] = "25";

    // 데이터 검색
    printf("name: %s\n", hashTable["name"].c_str());
    printf("age: %s\n", hashTable["age"].c_str());

    return 0;
}

 

 

Java에서의 해시 구현 예제

import java.util.HashMap;

public class HashExample {
    public static void main(String[] args) {
        HashMap<String, String> hashMap = new HashMap<>();

        // 데이터 삽입
        hashMap.put("name", "Alice");
        hashMap.put("age", "25");

        // 데이터 검색
        System.out.println("name: " + hashMap.get("name"));
        System.out.println("age: " + hashMap.get("age"));
    }
}

---

 

Python에서의 해시 구현 예제

# Python의 dictionary 사용
hash_table = {}

# 데이터 삽입
hash_table["name"] = "Alice"
hash_table["age"] = "25"

# 데이터 검색
print(f"name: {hash_table['name']}")
print(f"age: {hash_table['age']}")

---

 

 

4. 해시 자료구조의 장단점

장점

1. 빠른 데이터 접근: 평균적으로 O(1)의 시간 복잡도로 데이터에 접근할 수 있습니다.
2. 다양한 응용: 캐싱, 데이터베이스 색인, 세션 관리 등 다양한 분야에서 활용됩니다.

단점

1. 충돌 문제: 충돌이 발생하면 성능이 저하될 수 있습니다.
2. 메모리 사용: 해시 테이블은 사전에 충분한 메모리를 할당해야 하므로 메모리 낭비가 발생할 수 있습니다.
3. 정렬 불가: 데이터가 정렬되지 않은 상태로 저장되므로, 순차적인 접근이 어렵습니다.

---