Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

이중 연결 리스트를 활용한 해시 테이블 체이닝 구현 (C++)

해시 테이블(Hash Table)은 키-값 쌍(Key-Value Pair)을 저장하는 자료구조입니다. 해시 함수(Hash Function)를 사용해 키를 배열의 인덱스로 변환하고, 해당 위치에 데이터를 저장하거나 검색합니다.

이 문서에서는 이중 연결 리스트(Doubly Linked List)를 이용해 충돌(Collision)을 해결하는 체이닝(Chaining) 방식의 해시 테이블을 C++로 구현하는 방법을 설명합니다.

핵심 알고리즘

1. 삽입 (Insert)

해시 값을 계산해 버킷(Bucket) 위치를 찾습니다. 해당 버킷이 비어 있으면 새 노드를 헤드와 테일로 설정하고, 데이터가 이미 존재하면 이중 연결 리스트의 맨 뒤에 새 노드를 추가합니다.

Begin
  Function insert(key, value)
    hash_v = HashFunc(key)
    en = ht[hash_v]
    if (en == NULL)
      en = new HashTableEntry
      en->data = value
      en->key = key
      en->next = NULL
      en->prev = NULL
      ht[hash_v] = en
      top[hash_v] = en
    else
      while (en != NULL)
        en = en->next
      en = new HashTableEntry
      en->data = value
      en->key = key
      en->next = NULL
      en->prev = top[hash_v]
      top[hash_v]->next = en
      top[hash_v] = en
End

2. 삭제 (Delete)

키에 해당하는 해시 버킷을 찾아 순회하며 대상 노드를 찾습니다. 찾은 노드가 헤드이자 테일(유일 노드)인 경우 버킷을 비우고, 테일 노드인 경우 테일을 이전 노드로 이동시킨 뒤 연결을 끊고 메모리를 해제합니다.

Begin
  Function remove(key)
    hash_v = HashFunc(key)
    en = ht[hash_v]
    if (en == NULL || en->key != key) // 첫 노드 체크 로직 보완 필요
      Print "No Element found at key"
      return
    while (en != NULL)
      if (en->next == NULL) // 테일 노드 발견
        if (en->prev == NULL) // 유일한 노드
          ht[hash_v] = NULL
          top[hash_v] = NULL
          delete en
          break
        else
          top[hash_v] = en->prev
          top[hash_v]->next = NULL
          delete en
          en = top[hash_v]
      en = en->next
End

3. 검색 (Search)

해시 버킷에서 연결 리스트를 순회하며 키가 일치하는 노드를 찾습니다. 발견 시 값을 출력하고, 없으면 실패 메시지를 출력합니다.

Begin
  Function SearchKey(key)
    hash_v = HashFunc(key)
    flag = false
    en = ht[hash_v]
    if (en != NULL)
      while (en != NULL)
        if (en->key == key)
          flag = true
        if (flag)
          Print "Element found at key: " + en->data
        en = en->next
    if (!flag)
      Print "No Element found at key."
End

완전한 C++ 구현 예제

아래는 콘솔 메뉴를 통해 삽입, 검색, 삭제 기능을 테스트할 수 있는 전체 코드입니다.

#include <iostream>
const int TABLE_SIZE = 200;
using namespace std;

struct HashTableEntry {
    int data;
    int key;
    HashTableEntry *next;
    HashTableEntry *prev;
};

class HashMapTable {
    public:
    HashTableEntry **ht;  // 헤드 포인터 배열
    HashTableEntry **top; // 테일 포인터 배열

    HashMapTable() {
        ht = new HashTableEntry*[TABLE_SIZE];
        top = new HashTableEntry*[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++) {
            ht[i] = NULL;
            top[i] = NULL;
        }
    }

    int HashFunc(int key) {
        return key % TABLE_SIZE;
    }

    void insert(int k, int v) {
        int hash_v = HashFunc(k);
        HashTableEntry *en = ht[hash_v];
        
        if (en == NULL) {
            en = new HashTableEntry;
            en->data = v;
            en->key = k;
            en->next = NULL;
            en->prev = NULL;
            ht[hash_v] = en;
            top[hash_v] = en;
        } else {
            // 테일로 이동
            while (en->next != NULL) en = en->next; 
            
            HashTableEntry *newNode = new HashTableEntry;
            newNode->data = v;
            newNode->key = k;
            newNode->next = NULL;
            newNode->prev = en;
            en->next = newNode;
            top[hash_v] = newNode;
        }
    }

    void remove(int k) {
        int hash_v = HashFunc(k);
        HashTableEntry *en = ht[hash_v];
        
        if (en == NULL) {
            cout << "No Element found at key: " << k << endl;
            return;
        }

        while (en != NULL) {
            if (en->key == k) { // 키 매칭 시 삭제 처리
                if (en->prev == NULL && en->next == NULL) { // 유일한 노드
                    ht[hash_v] = NULL;
                    top[hash_v] = NULL;
                } else if (en->prev == NULL) { // 헤드 노드
                    ht[hash_v] = en->next;
                    en->next->prev = NULL;
                } else if (en->next == NULL) { // 테일 노드
                    top[hash_v] = en->prev;
                    en->prev->next = NULL;
                } else { // 중간 노드
                    en->prev->next = en->next;
                    en->next->prev = en->prev;
                }
                delete en;
                cout << "Element deleted at key: " << k << endl;
                return;
            }
            en = en->next;
        }
        cout << "No Element found at key: " << k << endl;
    }

    void SearchKey(int k) {
        int hash_v = HashFunc(k);
        HashTableEntry *en = ht[hash_v];
        bool found = false;
        
        while (en != NULL) {
            if (en->key == k) {
                cout << "Element found at key " << k << ": " << en->data << endl;
                found = true;
                break;
            }
            en = en->next;
        }
        if (!found)
            cout << "No Element found at key " << k << endl;
    }

    ~HashMapTable() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            HashTableEntry *en = ht[i];
            while (en != NULL) {
                HashTableEntry *temp = en;
                en = en->next;
                delete temp;
            }
        }
        delete[] ht;
        delete[] top;
    }
};

int main() {
    HashMapTable hash;
    int k, v, c;
    
    while (true) {
        cout << "\n1. Insert element" << endl;
        cout << "2. Search element" << endl;
        cout << "3. Delete element" << endl;
        cout << "4. Exit" << endl;
        cout << "Enter your choice: ";
        cin >> c;
        
        switch(c) {
            case 1:
                cout << "Enter value to insert: ";
                cin >> v;
                cout << "Enter key: ";
                cin >> k;
                hash.insert(k, v);
                break;
            case 2:
                cout << "Enter key to search: ";
                cin >> k;
                hash.SearchKey(k);
                break;
            case 3:
                cout << "Enter key to delete: ";
                cin >> k;
                hash.remove(k);
                break;
            case 4:
                return 0;
            default:
                cout << "Invalid option. Try again.\n";
        }
    }
}

실행 결과 예시

1. Insert element
2. Search element
3. Delete element
4. Exit
Enter your choice: 1
Enter value to insert: 10
Enter key: 1

Enter your choice: 1
Enter value to insert: 20
Enter key: 3

Enter your choice: 2
Enter key to search: 3
Element found at key 3: 20

Enter your choice: 3
Enter key to delete: 1
Element deleted at key: 1

Enter your choice: 4

구현 시 주의사항 및 개선점

  • 메모리 관리: 소멸자에서 모든 버킷의 연결 리스트를 순회하며 동적 할당된 노드를 해제해야 메모리 누수를 방지할 수 있습니다.
  • 삭제 로직: 원본 코드의 삭제 알고리즘은 테일 노드만 삭제 가능하고 중간 노드 삭제 시 연결이 끊기는 버그가 있었습니다. 위 예제 코드에서는 헤드, 테일, 중간 노드 모든 경우를 처리하도록 수정했습니다.
  • 해시 함수: 예제는 간단한 모듈로 연산(key % TABLE_SIZE)을 사용하지만, 실제로는 키 분포를 고르게 하는 더 정교한 해시 함수가 필요합니다.
  • 동적 크기 조절: 데이터 양이 늘어나면 부하 인자(Load Factor)를 기준으로 리사이징(Rehashing)을 수행하는 기능이 추가되어야 성능 저하를 막을 수 있습니다.