현재 정보화 시대에는 정보량이 급증하고 있다는 것, 다들 아시나요? 우리가 인터넷으로 하는 것, 심지어 일상생활에 사용되는 모든 정보가 컴퓨터에 저장이 되는 시대입니다. 시간이 지날수록 저장해야 할 정보가 늘어나게 되고, 우리는 그 정보를 더욱 효율적으로 저장하고 사용하는 것이 필요하게 됩니다. 따라서 이번 포스팅에서는 데이터를 저장하는데 효율이 좋은 해시테이블과 캐싱에 대해 알아보고 각각의 특징에 대해 알아보도록 하겠습니다.

 

 

 

 

목차

 

1. 해시 테이블과 캐시
2. 해시 체이닝 vs LRU 캐시
3. 코드 구현
4. 분석

 

 

 

#1 해시 테이블과 캐싱

 

해시 테이블

 

<그림 1> 해시 테이블

 

 해시 테이블이란 해시 함수를 이용하여 key : value를 저장하는 자료구조입니다. 해시 함수로 key 값을 변환한 후, 변환한 값의 배열 인덱스에 value 값을 저장하는 원리입니다. 해시 테이블은 삽입, 삭제, 조회의 시간복잡도가 O(1)로, 굉장히 속도가 빠르기 때문에 성능이 좋아요. 그래서 해시 테이블이 자주 사용되는 자료구조입니다. 그러나 최악의 경우 시간복잡도가 O(n)까지 증가할 수 있기 때문에, 몇 가지 중요한 점들을 고려해야 합니다.

 

  • 적절한 해시 함수 선택
  • 적절한 해시 테이블 크기 선택
  • 충돌 방지

 

 적절하게 분배하는 해시 함수와 해시 테이블 크기를 선택하는 것이 중요합니다. 또한 최악의 상황으로 만드는 충돌은 똑같은 key 배열의 인덱스에 중복되는 데이터가 저장될 때 발생합니다. 이 경우에는 충돌 방지를 위해 두 가지 기법 중 하나를 선택해야 합니다.

  • Closed Addressing (Chaining)
  • Open Addressing

 

<그림 2> 해시 체이닝(Hash Chaining)

 

 체이닝(Chaining) 기법이란 충돌이 발생한 경우에 연결리스트로 데이터를 연결하는 방법을 의미합니다. 따라서 하나의 해시 key에 여러 value가 저장될 수 있습니다. 당연히 배열 하나에 하나의 값만 들어가는 것이 아니니 효율이 좋겠죠? 또한 동적으로 크기를 조정할 필요가 없어서 구현도 간단해요. 다른 하나인 개방 주소법은 충돌 시 다른 버켓에 데이터를 넣는 방식을 의미합니다. 해시 함수를 이용해 인덱스를 건너뛰어 저장시켜 충돌을 예방합니다. 그러나 개방 주소법(Open Addressing)은 체이닝(Chaining) 보다 상대적으로 구현이 복잡하고 많은 저장공간을 필요로 할 수 있기 때문에 체이닝(Chaining)이 보편적으로 사용됩니다.

 

 그렇다면 체이닝(Chaining)만을 사용해야 하는가?라고 물으신다면, 아니에요. 해시 테이블의 크기가 작으면 개방 주소법(Open Addressing)이 더 효율적일 수 있고, 체이닝(Chaining)은 하나의 해시 key에 너무 많은 value가 저장된다면 최악의 경우, 시간복잡도가 O(n)이 되면서 효율이 떨어질 수 있습니다. 그렇기 때문에, 상황에 맞게 적절하게 두 기법 중 하나를 선택해서 사용해야 합니다.

 

 

 

캐시

<그림 3> 캐시 메모리

 

 캐시(Cache)란 삽입, 탐색, 또는 연산과 같은 작업을 통해 최근에 접근한 데이터를 저장하여 이후에도 빠르게 접근할 수 있도록 사용하는 방법입니다. 이전에 들어왔던 요청과 동일한 요청이 들어온다면, 굳이 다시 계산을 할 필요 없이 응답을 해도 된다는 뜻이에요. <그림 3>는 웹에서 이루어지는 캐시 구조입니다. 웹에서 html을 불러올 때, 캐시 메모리에 미리 저장해 놓고, 불러오는 방식이죠.

 

 

 

#2 해시 체이닝 vs LRU 캐싱

 

 LRU 캐싱이란 Least Recently Used 캐싱으로, 가장 최근에 사용했던 것을 남기는 캐싱 기술입니다. 가장 오래전에 사용되었던 데이터는 우선적으로 삭제하고, 최근에 사용했던 데이터는 저장해 놓는 구조예요. 떠오르시는 자료구조가 있으신가요? Doubly Linked List 가 떠오르시지 않나요? 물론 여러 자료구조로도 구현할 수 있지만, Doubly Linked List가 일반적으로 널리 사용됩니다. 또한 LRU 캐싱은 해시 테이블과는 다르게 삽입, 삭제, 조회의 시간복잡도가 항상 O(1)로 매우 빠르기 때문에 권장되는 전략입니다. 그렇다면 해시 체이닝(Chaining)과 LRU 캐싱의 특징을 비교해 보겠습니다.

 

해시 체이닝과 캐싱을 같이 사용할 수 있는가?

 두 방법을 동시에 사용하는 것은 성능을 최적화할 수 있는 아주 좋은 방법이에요. 하지만 일부의 경우에서는 필요하지 않을 수 있습니다. 바로 두 방법을 동시에 사용하였을 때의 성능이 한 가지 방법을 사용한 것과 동일할 때입니다. 또한 두 가지 방법을 사용하면 코드의 복잡성이 증가하기 때문에, 간결함과 일관성이 떨어질 수 있습니다.

 

 그렇다면 해시 체이닝(Chaining)과 캐싱은 어느 때에 사용하는 것이 적합할까요?

 

 

  • 해시 체이닝(Chaining)

 

해시 체이닝은 충돌을 방지하고자 하는 목적이기 때문에 충돌이 자주 발생하는 경우에 사용하거나, 삽입, 삭제 등의 작업이 빈번할 때 연결리스트의 장점을 통해 효율을 올릴 수 있을 때 사용할 수 있습니다.

 

 

  • LRU 캐싱(Caching)

 

캐싱은 데이터에 접근할 때 필요한 비용(cost)이 높고 자주 사용될 때 사용할 수 있습니다. 따라서 상황에 따라 체이닝(Chaining) 보다 더 우수한 성능을 보일 수 있습니다.

 

위의 두 기능을 코드로 직접 구현하여 차이점을 더욱 파헤쳐 보겠습니다.

 

 

 

 

#3 코드 구현

 

해시 체이닝(Chaining)과 캐싱(Caching)을 C++를 이용해 구현했습니다.

 

해시 체이닝(Hash Chaining)

typedef int Data;
const int HASH_SIZE = 10;
#define HASH(key) ((key) % HASH_SIZE) //해시 함수

 

해시 함수는 key값을 10으로 나누었을 때의 나머지를 도출하도록 지정했습니다. 따라서 해시 테이블의 인덱스가 총 0~9까지로 10개가 존재하게 됩니다.

 

struct Customer {
    int id;
    string name;
    int age;
    Customer(int _id = 0, string _name =" ", int _age = 0) {
        id = _id; name = _name; age = _age;
    } //생성자

    void Print() {
        cout << "ID = " << id << ", Name = " << name
            << ", Age = " << age << endl;
    }

    int Key() { return id; }
};

 

예를 들기 위해, 고객의 ID와 이름, 나이를 담는 구조체 Customer를 선언했습니다. 여기서 Key() 함수는 id를 반환합니다.

 

class Node {
public:
    Customer data;
    Node* next;
    Node(Customer c, Node* n = nullptr) {
        data = c; next = n;
    }
    friend class CustomerHash;
};

class CustomerHash {
    Node* CustomerId[HASH_SIZE];
public:
    CustomerHash() {
        for (int i = 0; i < HASH_SIZE; i++) {
            CustomerId[i] = nullptr;
        }
    } //각 인덱스에 NULL 지정

    void Insert(Customer c) {
        int index = HASH(c.Key());
        CustomerId[index] =
            new Node(c, CustomerId[index]);
    } //연결리스트의 맨 앞에 삽입

    void Search(int key) {
        int index = HASH(key);
        Node* p = CustomerId[index];
        for (; p != nullptr; p = p->next) {
            if (p->data.Key() == key) {
                p->data.Print();
                return;
            }
        }
        cout << "Search Failed." << endl;
    } //Key 탐색

    void InsertCustomer(int id, string name, int age) {
        Insert(Customer(id, name, age));
    }
};

 

 Insert() 함수를 살펴보겠습니다. index라는 정수형 타입에 c.Key(), 즉 고객의 ID를 해시 함수를 통해 변환합니다. 변환하면 0~9까지의 정수가 발생하고, 이 정수 인덱스가 가리키는 노드로 삽입합니다. 이와 같은 방식으로 해시함수를 통해 변환된 Key가 충돌이 되는 대신, 연결리스트의 맨 앞으로 노드를 삽입합니다.

 

 단, Key가 같으면 체이닝(Chaining)에서도 충돌이 발생하므로, Key는 주식별자여야 합니다. 주민등록번호나 ID 같은 것만 가능하다고 생각하시면 편해요.

 

 

캐싱(Caching)

class Node {
public:
    Customer data;
    Node* next; Node* prev;
    Node(Customer c, Node* n = nullptr, Node* p = nullptr) {
        data = c; next = n; prev = p;
    } //생성자
    friend class CustomerHash;
};

 

캐싱의 구조체는 Customer로 똑같이 선언했고, 체이닝(Chaining)과의 다른 점은 prev 포인터가 필요합니다.

 

class LRUcache {
    unordered_map<int, Node*> CustomerId; //Key는 int, Value는 Node*
    Node* head; Node* tail;
    int cacheSize;

    void InsertFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    } //맨 앞에 노드 생성

    void RemoveNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    } //노드 제거

 

위는 private 영역 부분이에요. 여기에 LRUcache 클래스, 안에 CustomerId라는 해시맵을 생성했습니다. 해시맵이랑 캐시는 같이 다루기 편해요. 여기서 C++에서 해시맵을 더욱 빠르게 탐색할 수 있는 unordered_map 라이브러리를 사용하면 코드는 더욱 간결해집니다.

 

public:
    LRUcache(int _cachesize) {
        cacheSize = _cachesize;
        head = new Node(Customer(), nullptr, nullptr);
        tail = new Node(Customer(), nullptr, nullptr);
        head->next = tail; tail->prev = head;
    }

    ~LRUcache() { //소멸자
        Node* p = head;
        for(; p != nullptr; p = p->next) {
            Node* temp = p;
            p = p->next;
            delete temp;
        }
    }

    void Insert(Customer c) {
        if (CustomerId.find(c.Key()) != CustomerId.end()) { //회원ID가 존재하는 경우
            RemoveNode(CustomerId[c.Key()]); //노드에서 해당 회원ID의 노드를 제거 for 맨 앞에 회원ID 넣기
        }
        else if (CustomerId.size() >= cacheSize) { //캐시가 가득 찬 경우
            Node* nodeToDelete = tail->prev; // 가장 오래된 항목
            RemoveNode(nodeToDelete); //리스트에서 가장 오래된 항목의 노드 제거
            CustomerId.erase(nodeToDelete->data.Key()); //해시 테이블에서 가장 오래된 항목의 노드를 제거
            delete nodeToDelete;
        }

        Node* node = new Node(c);
        InsertFront(node); //리스트에 새로운 노드 추가맵
        CustomerId[c.Key()] = node; //해시 맵에 회원ID가 키, 노드가 값인 노드 추가
    }

    void Search(int key) {
        if (CustomerId.find(key) != CustomerId.end()) {
            Node* node = CustomerId[key];
            RemoveNode(node); //노드를 앞으로 옮기기 위해 지움.
            InsertFront(node);
            return node->data.Print();
        }
        cout << "Search Failed." << endl;
    }

 

 public 영역입니다. 여기서 봐야 할 곳은 Insert()입니다. unordered_map의 함수인 find(), end(), size(), erase()를 사용했어요. 회원ID가 이미 존재한다면, 해당 회원ID의 노드를 제거하고 다시 맨 앞에 삽입합니다. Search()도 마찬가지로 탐색한 회원ID의 노드를 제거하고 다시 맨 앞에 삽입하면 됩니다. 이렇게 최신에 접근했던 데이터를 갱신하는 거예요.

 

 캐시 메모리가 가득 찬 경우에는 가장 오래된 항목을 제거하고, 그다음에 맨 앞에 노드를 삽입하면 다시 데이터를 갱신할 수 있습니다.

 

 

 

#4 분석

 

 LRU 캐싱은 최근에 사용했던 데이터를 빠르게 접근하는 방식이므로 성능 최적화에 큰 효과가 있습니다. LRU 캐싱은 해시 체이닝(Chaining)과는 다르게 해시 테이블과 연결리스트를 동시에 구현하기 때문에 최악의 상황을 고려할 필요 없이 시간복잡도가 항상 O(1)입니다. 따라서 LRU 캐싱을 사용하는 경우 데이터를 조회하는데 더욱 성능을 끌어올릴 수 있습니다. 하지만, 메모리 공간이 부족하거나 데이터가 빈번하게 수정되는 경우와 같이 예외의 상황에서는 해시 체이닝(Chaining)의 사용도 고려해야 합니다.

 

 

 

 

 

 

이미지 출처

https://terms.naver.com/entry.naver?cid=42344&docId=816995&categoryId=42344

https://en.wikipedia.org/wiki/Hash_table

'Programming' 카테고리의 다른 글

웹 로그인 성능 및 보안 개선 프로젝트  (0) 2024.07.01

티스토리툴바