6. Linked list, Hash table

 

6.1 Linked List

  Def) Linked List
    각 노드가 데이터와 다음 노드의 메모리 주소를 저장하는 자료구조.

 

  Note) 장단점
    장점1. 자료구조의 크기를 동적으로 조절 가능함.
    장점2. 삽입, 삭제할 때 메모리 주소만 바꾸면 되므로 O(1)의 시간복잡도로 가능.
    단점1. 임의 접근이 불가능함. 특정 요소에 접근하기 위해서는 O(n)의 시간복잡도로 가능.
    단점2. 각 노드가 다음 노드의 메모리 주소도 저장해야 하므로 배열에 비해 공간복잡도가 늘어날 수 있음.
    단점3. 연속된 메모리 공간이 아니므로, 캐시 효율성이 비교적 낮음.

 

  Note) 구현코드

<hide/>

#include <iostream>
using namespace std;

template <typename T>
class SNode 
{
public:
    SNode(T InData) 
        : Data(InData)
        , NextNode(nullptr)
    {
    }

    T Data;

    SNode* NextNode;

};

template <typename T>
class SSinglyLinkedList 
{
public:
    SSinglyLinkedList() 
        : HeadNode(nullptr)
    {
    }

    // 노드 추가 (리스트 끝에 추가)
    void PushBack(T InData) 
    {
        SNode<T>* NewNode = new SNode<T>(InData);

        if (nullptr == HeadNode)
        {
            HeadNode = NewNode;
            return;
        }

        SNode<T>* CurrentNode = HeadNode;
        while (CurrentNode->NextNode != nullptr) 
        {
            CurrentNode = CurrentNode->NextNode;
        }
        CurrentNode->NextNode = NewNode;
    }

    // 노드 삭제 (특정 값 가진 노드 삭제)
    void Erase(T InData) 
    {
        if (nullptr == HeadNode)
        {
            return;
        }

        // 헤드 노드가 삭제할 값인 경우
        if (InData == HeadNode->Data)
        {
            SNode<T>* DeletedNode = HeadNode;
            HeadNode = HeadNode->NextNode;
            delete DeletedNode;

            return;
        }

        // 중간 또는 마지막 노드 삭제
        SNode<T>* CurrentNode = HeadNode;
        while (CurrentNode->NextNode != nullptr && CurrentNode->NextNode->Data != InData) 
        {
            CurrentNode = CurrentNode->NextNode;
        }

        if (CurrentNode->NextNode == nullptr)
        {   
            return; // 값이 존재하지 않음
        }

        SNode<T>* DeletedNode = CurrentNode->NextNode;
        CurrentNode->NextNode = CurrentNode->NextNode->NextNode;
        delete DeletedNode;
    }

    // 리스트 출력
    void Print() const 
    {
        SNode<T>* CurrentNode = HeadNode;
        while (CurrentNode != nullptr) 
        {
            cout << CurrentNode->Data << " -> ";
            CurrentNode = CurrentNode->NextNode;
        }
        cout << "nullptr" << endl;
    }

    // 특정 값 탐색
    bool Search(T InData) const 
    {
        SNode<T>* CurrentNode = HeadNode;
        while (CurrentNode != nullptr) 
        {
            if (InData == CurrentNode->Data)
            {
                return true;
            }
            CurrentNode = CurrentNode->NextNode;
        }
        return false;
    }

    // 소멸자 (메모리 해제)
    ~SSinglyLinkedList() 
    {
        SNode<T>* CurrentNode = HeadNode;
        while (CurrentNode != nullptr) 
        {
            SNode<T>* DeletedNode = CurrentNode;
            CurrentNode = CurrentNode->NextNode;
            delete DeletedNode;
        }
    }

private:
    SNode<T>* HeadNode;

};

 

 

6.2 Hash Table

  Note) 지금까지의 자료구조에서는 상수 시간에 검색을 수행하진 못함.

    그러나, 병원에 가서 주민번호만 불러드려도 5천만명 중 나의 신상정보가

    굉장히 빠른 시간에 검색 됨을 알 수 있음. 이건 어떻게 한걸까?

 

  Note) 집집마다 우체통을 두는것 처럼, 공간 복잡도를 늘려보자.

    즉, 임의의 크기를 가진 입력(우편물)을

    고정된 크기를 가진 출력(주소) 변환시키는 작업을 Hashing 혹은 Hash 기법이라고 함.

    아무리 큰 고기도 잘게 썰어버리면, 우리가 원하는 모양으로 만들 수 있어서

    이런 이름을 채택하지 않았을까 하는 합리적 의심.

 

  Note) C++ STL 컨테이너와 Hash

set<TKey>	중복 키를 가질 수 없는 균형 이진 탐색 트리
multiset<TKey>	중복 키를 가질 수 있는 균형 이진 탐색 트리
unordered_set<TKey>	중복 키를 가질 수 없는 해시 테이블
unordered_multiset<TKey>	중복 키를 가질 수 있는 해시 테이블
map<TKey, TValue>	중복 키를 가질 수 없는 균형 이진 탐색 트리
multimap<TKey, TValue>	중복 키를 가질 수 있는 균형 이진 탐색 트리
unordered_map<TKey, TValue>	중복 키를 가질 수 없는 해시 테이블
unordered_multimap<TKey, TValue>	중복 키를 가질 수 있는 해시 테이블

 

  Note) map Vs. unordered_map

    인터페이스의 차이는 없음. 균형 이진 탐색 트리냐 해시 테이블이냐 차이.

    1. 기본적으로 unordered_map이 해시 테이블 기반이므로 O(1)의 검색 시간을 가짐.

    2. map은 균형 이진 탐색 트리 기반이므로, 삽입 삭제시 정렬 과정이 포함됨.

    3. 그러나, 키 값을 문자열로 지정하고 그 문자열의 길이를 늘려간다면

      해싱 때문에 unordered_map이 조금 더 느릴 수 있음.

      ex. 시간 문자열을 키 값으로 쓰는 경우.

 

  Note) 구현 방법 1: 입력 값의 최댓값만큼 배열 크기로 잡기

    가장 단순하면서도 무식한 방법.

    즉, 이 경우에 입력 값이 곧 배열의 색인이 됨.

    그러나 입력 값이 너무나도 크다면? 공간 복잡도도 선형적으로 늘어남.

    그래도 배열의 크기가 크면 클수록 해시 테이블을 구현하는데

    좀 더 쉬울 것이라는 걸 알 수 있음.

 

  Note) 구현 방법 2: "입력 값 % 배열 크기"로 색인 만들

    구현 방법 1의 단점을 보완할 수 있음.

    즉, 입력 값이 배열의 크기 내로 제한할 수 있음.

    그런데 동일한 색인을 갖는 입력 값들이 생기게 됨.

    궁여지책으로 배열의 크기를 늘린다 한들,

    겹치는 색인이 덜 생길 뿐 여전히 존재함.

  

  Note) 구현 방법 3: 배열의 크기를 입력 값의 최댓값 두 배 && 소수로 나머지 연산.

    배열의 크기를 키우면 겹치는 색인이 줄어든다는 사실과

    소수를 쓰면 약수가 1과 자기 자신 뿐이라, 나머지 연산시에 겹치는 색인이 줄어듦을

    이용해서 배열의 크기를 입력 값의 최대값 두배이자 그거보다 큰 소수로 잡고자 함.

 

  Note) 구현 방법 3도 결국 중복 색인 문제가 발생할 수 있음.

    중복 색인의 경우, 배열 기반으로 만드느냐 링크드 리스트로 만느냐에 따라 처리 방법이 다름.

    배열 기반으로 만들 예정이라 우리는 다음 색인에 데이터를 저장하고자 함.

    링크드 리스트 기반이라면 그냥 같은 색인에 꼬리를 물어서 저장하는 식.

    즉, 굳이 남의 해시값을 뺏지 않음. 다만 최악의 경우인 모두 같은 해시값을 가지면

    O(N)의 검색 시간이 걸림. 

 

6.2-1 Hash Set

  Note) 해시 셋 템플릿 코드

<hide/>

// Hash.h

#pragma once

#include <iostream>

using namespace std;

enum
{
    INPUT_SIZE = 8,
    BUCKET_SIZE = 17, // INPUT_SIZE * 2보다 더 큰 소수.
};

class HashSet
{
public:
    HashSet()
        : iarrBuckets{}
    {
        for (size_t i = 0; i < BUCKET_SIZE; ++i) { iarrBuckets[i] = INT_MIN; }
    }

    int* Find(const int& _iValue)
    {
        int i, iStartIndex = _iValue % BUCKET_SIZE;
        if (iStartIndex < 0) { iStartIndex += BUCKET_SIZE; } // 인덱스가 항상 양의 값을 가지게 하기 위함.

        i = iStartIndex;
        do {
            if (_iValue == iarrBuckets[i]) { return &iarrBuckets[i]; }
            else if (INT_MIN == iarrBuckets[i]) { return nullptr; }

            i = (i + 1) % BUCKET_SIZE;
        } while (i != iStartIndex);

        return nullptr;
    }

    bool Insert(const int& _iValue)
    {
        int i, iStartIndex = _iValue % BUCKET_SIZE;
        if (iStartIndex < 0) { iStartIndex += BUCKET_SIZE; } // 인덱스가 항상 양의 값을 가지게 하기 위함.

        i = iStartIndex;
        do {
            if (_iValue == iarrBuckets[i] || INT_MIN == iarrBuckets[i])
            {
                iarrBuckets[i] = _iValue;
                return true;
            }

            i = (i + 1) % BUCKET_SIZE;
        } while (i != iStartIndex);

        return false;
    }

    bool Erase(const int& _iValue)
    {
        int i, iStartIndex = _iValue % BUCKET_SIZE;
        if (iStartIndex < 0) { iStartIndex += BUCKET_SIZE; } // 인덱스가 항상 양의 값을 가지게 하기 위함.

        i = iStartIndex;
        do {
            if (_iValue == iarrBuckets[i])
            {
                iarrBuckets[i] = INT_MIN;
                return true;
            }
            else if (INT_MIN == iarrBuckets[i]) { return false; }

            i = (i + 1) % BUCKET_SIZE;
        } while (i != iStartIndex);

        return false;
    }

    void Print(void)
    {
        for (size_t i = 0; i < BUCKET_SIZE; ++i)
        {
            if (INT_MIN == iarrBuckets[i]) { cout << '[' << i << "]: INT_MIN" << endl; }
            else { cout << '[' << i << "]: " << iarrBuckets[i] << endl; }
        }
        cout << endl;
    }

public:
    int     iarrBuckets[BUCKET_SIZE];

};

<hide/>

// main.cpp

#include <iostream>

#include "LinkedList.h"
#include "Hash.h"

using namespace std;

int main(void)
{
    HashSet hashSet;

    hashSet.Insert(777);
    hashSet.Insert(123);
    hashSet.Insert(899);

    hashSet.Print();

    *(hashSet.Find(123)) = 321;

    hashSet.Print();

    hashSet.Erase(899);

    hashSet.Print();

    return 0;
}

 

 

 

6.2-2 Hash Function

  Def) 해시 함수(Hash Function)

    임의의 크기를 가진 데이터를 고정 크기를 가진 데이터로 대응 되게끔 하는 함수.

    해시 함수를 통해 나온 고정 크기의 데이터를 해시 값이라고 함.

 

  Note) "정수 값 % BUCKET_SIZE"은 해시 함수일까?

    정수 값이 임의의 크기를 가지진 않았으므로 해시 함수는 아님.

 

  Note) 해시 함수의 성질

    1. 함수이므로, 입력 값이 같으면 출력 값도 언제나 같음.

    2. 입력 값이 다른데 출력 값이 같을 수도 있음.

      이런 경우를 해시 충돌(Hash Collision)이라 함. 

      해시 충돌은 최대한 없을수록 좋음. 

      이 덕분에, 출력 값으로부터 입력 값을 찾을 수 있다는 보장이 없음.

 

  Note) 즉, 해시 값은 임의의 크기를 가진 데이터를 대표하는 값.

    ex. 주민 번호는 그 사람을 대표함. 즉, 주민 번호는 해시 값이라고도 할 수 있음.

 

  Note) 이전 예제에서는 정수 값이 입력으로 들어왔음.

    그렇기에 엄밀한 의미에서 해시 함수를 실습했다곤 할 수 없음.

    따라서 임의 크기를 가진 데이터인 문자열을 입력으로 받아보자.

    그럼 이를 해시 값으로 변환해 줄 해시 함수가 필요해짐.

    문자열의 각 요소를 합쳐서(ASCII Code) 해시 값을 만들고

    해시 값을 통해서 배열의 색인을 만들어 내는 식으로 구현 해 보자.

 

  Note) 해시 함수와 해시 셋

<hide/>

// Hash.h

#pragma once

#include <iostream>
#include <string>

using namespace std;

enum
{
    INPUT_SIZE = 8,
    BUCKET_SIZE = 17, // INPUT_SIZE * 2보다 더 큰 소수.
};

class HashSet
{
public:
    HashSet()
        : mBuckets{}
    {
        for (size_t i = 0; i < BUCKET_SIZE; ++i) { mBuckets[i] = ""; }
    }

    size_t HashFunction(string _strValue)
    {
        size_t uHashValue = 0u;
        for (size_t i = 0; i < _strValue.size(); ++i)
        {
            uHashValue += (size_t)(_strValue[i]);
        }

        return uHashValue;
    }

    string* Find(const string& _strValue)
    {
        int i, iStartIndex = HashFunction(_strValue) % BUCKET_SIZE;
        if (iStartIndex < 0) { iStartIndex += BUCKET_SIZE; } 

        i = iStartIndex;
        do {
            if (0 == strcmp(_strValue.c_str(), mBuckets[i].c_str())) 
            { 
                return &mBuckets[i]; 
            }
            else if ("" == mBuckets[i]) { return nullptr; }

            i = (i + 1) % BUCKET_SIZE;
        } while (i != iStartIndex);

        return nullptr;
    }

    bool Insert(const string& _strValue)
    {
        int i, iStartIndex = HashFunction(_strValue) % BUCKET_SIZE;
        if (iStartIndex < 0) { iStartIndex += BUCKET_SIZE; } 

        i = iStartIndex;
        do {
            if (0 == strcmp(_strValue.c_str(), mBuckets[i].c_str()) || "" == mBuckets[i])
            {
                mBuckets[i] = _strValue;
                return true;
            }

            i = (i + 1) % BUCKET_SIZE;
        } while (i != iStartIndex);

        return false;
    }

    bool Erase(const string& _strValue)
    {
        int i, iStartIndex = HashFunction(_strValue) % BUCKET_SIZE;
        if (iStartIndex < 0) { iStartIndex += BUCKET_SIZE; } 

        i = iStartIndex;
        do {
            if (0 == strcmp(_strValue.c_str(), mBuckets[i].c_str()))
            {
                mBuckets[i] = "";
                return true;
            }

            i = (i + 1) % BUCKET_SIZE;
        } while (i != iStartIndex);

        return false;
    }

    void Print(void)
    {
        for (size_t i = 0; i < BUCKET_SIZE; ++i)
        {
            if ("" == mBuckets[i]) { cout << '[' << i << "]: " << endl; }
            else { cout << '[' << i << "]: " << mBuckets[i] << endl; }
        }
        cout << endl;
    }

public:
    string     mBuckets[BUCKET_SIZE];

};

 

  Note) 그러나, 이런 식으로 만들면 O(1)이 아님.

    해시 함수에서 문자열의 길이만큼 반복문을 돌기 때문.

    즉, O(문자열길이) 만큼의 시간 복잡도를 잡아먹음.

 

  Note) 위 문제를 해결하기 위해서는?

    이미 어떤 문자열이 들어올지 알고있는 경우라면,

    모든 문자열에 해당하는 해시 값을 미리 구해둠.

    ex. 게임 내 모든 몬스터는 무한하지 않기에 이게 가능.

 

 

6.2-3 Hash Table

  Def) 해시 테이블(Hash Table)

    어떤 Key에 해당하는 어떤 Value를 쌍으로 저장하는 자료구조.

    해당 키 위치의 값을 꺼내 온다는 의미.

    이런 형태를 보통 해시 테이블. 엄밀히는 해시 맵이라고 부름.

    C#에서의 Dictionary가이 자료구조에 해당함.

 

  Def) 키(Key)

    데이터의 인덱스. 꼭 정수가 아니어도 상관 없음. 문자열, 구조체, ...

 

  Def) 값(Value)

    실제 저장되는 데이터.

 

  Note) 해시 테이블 템플릿 코드

<hide/>

// Hash.h

#pragma once

#include <iostream>
#include <string>

using namespace std;

enum
{
    ...
};

class HashSet
{
...
};

class HashTable
{
public:
    HashTable()
    {
        for (size_t i = 0u; i < BUCKET_SIZE; ++i)
        {
            mstrArrayOfKey[i] = "";
            miArrayOfValue[i] = INT_MIN;
        }
    }

    size_t HashFunction(string _strValue)
    {
        size_t uHashValue = 0u;
        for (size_t i = 0; i < _strValue.size(); ++i)
        {
            uHashValue += (size_t)(_strValue[i]);
        }

        return uHashValue;
    }

    int* Find(const string& _strValue)
    {
        int i, iStartIndex = HashFunction(_strValue) % BUCKET_SIZE;
        if (iStartIndex < 0) { iStartIndex += BUCKET_SIZE; }

        i = iStartIndex;
        do {
            if (0 == strcmp(_strValue.c_str(), mstrArrayOfKey[i].c_str()))
            {
                return &miArrayOfValue[i];
            }
            else if ("" == mstrArrayOfKey[i]) { return nullptr; }

            i = (i + 1) % BUCKET_SIZE;
        } while (i != iStartIndex);

        return nullptr;
    }

    bool Insert(const string& _strValue, const int& _iValue)
    {
        int i, iStartIndex = HashFunction(_strValue) % BUCKET_SIZE;
        if (iStartIndex < 0) { iStartIndex += BUCKET_SIZE; }

        i = iStartIndex;
        do {
            if (0 == strcmp(_strValue.c_str(), mstrArrayOfKey[i].c_str()) || "" == mstrArrayOfKey[i])
            {
                mstrArrayOfKey[i] = _strValue;
                miArrayOfValue[i] = _iValue;
                return true;
            }

            i = (i + 1) % BUCKET_SIZE;
        } while (i != iStartIndex);

        return false;
    }

    bool Erase(const string& _strValue)
    {
        int i, iStartIndex = HashFunction(_strValue) % BUCKET_SIZE;
        if (iStartIndex < 0) { iStartIndex += BUCKET_SIZE; }

        i = iStartIndex;
        do {
            if (0 == strcmp(_strValue.c_str(), mstrArrayOfKey[i].c_str()))
            {
                mstrArrayOfKey[i] = "";
                miArrayOfValue[i] = INT_MIN;
                return true;
            }

            i = (i + 1) % BUCKET_SIZE;
        } while (i != iStartIndex);

        return false;
    }

    void Print(void)
    {
        for (size_t i = 0; i < BUCKET_SIZE; ++i)
        {
            if ("" == mstrArrayOfKey[i]) { cout << '[' << i << "]: " << endl; }
            else { cout << '[' << i << "]: " << mstrArrayOfKey[i] << '(' << miArrayOfValue[i] << ')' << endl; }
        }
        cout << endl;
    }

public:
    string mstrArrayOfKey[BUCKET_SIZE];
    int miArrayOfValue[BUCKET_SIZE];

};

<hide/>

// main.cpp

#include <iostream>

#include "LinkedList.h"
#include "Hash.h"

using namespace std;

int main(void)
{
    HashTable hashTable;

    hashTable.Insert("Park", 100);
    hashTable.Insert("Kim", 70);
    hashTable.Insert("Lee", 20);

    hashTable.Print();

    *(hashTable.Find("Kim")) = 50;

    hashTable.Print();

    hashTable.Erase("Lee");

    hashTable.Print();

    return 0;
}

 

  Note) 위 해시 테이블 예제는 두 가지 충돌이 발생 가능.

    1. 해시 충돌: 키가 다르지만 같은 해시 값이 나올 수 있음.

    2. 색인 충돌: 해시 값이 다르지만 같은 색인이 나올 수 있음.

 

  Note) 사실 해시 충돌 문제는 해결 안해도 되긴함.

    색인 충돌 문제의 해법으로 같이 해결되기 때문.

    해시 충돌을 막는 방법은 훌륭한 해시 함수를 작성하는 것.

 

  Note) 훌륭한 해시 함수의 성질

    1. 임의의 입력 값에도 고정된 크기의 해시 값으로 변환.

      여기서 임의의란 자료형 혹은 데이터의 크기에 상관 없단 뜻.

    2. 해시 충돌이 거의 없어야 함. 이것이 좋고 나쁨의 척도.

      이는 해시 함수 테스트 표를 참고하면 선택 가능.

 

  Ex) 65599 해시 함수를 이용한 해시 테이블

<hide/>

// Hash.h

#pragma once

#include <iostream>
#include <string>

using namespace std;

enum
{
    ...
};

class HashSet
{
...
};

class HashTable
{
public:
    HashTable()
    {
        ...
    }

    size_t HashFunction(string _strValue)
    {
        size_t i;
        size_t hash_id = 0;
        size_t length = _strValue.size();

        hash_id = 0;
        for (i = 0; i < length; ++i) {
            hash_id = 65599 * hash_id + _strValue[i];
        }

        return hash_id ^ (hash_id >> 16);
    }

    ...

public:
    ...

};

 

Note) 장단점

  장점1. 탐색, 삽입, 삭제이 O(1) 시간복잡도에 가능.
  단점1. 해시 함수에 따라 해시 충돌이 발생 할 수 있음.
  단점2. 이진탐색트리에 비해 공간 복잡도가 더 높을 수 있음.
  단점3. 입력된 키의 순서 유지가 불가능함.
  결론. 빠른 탐색이 필요한 경우, 키-값 쌍을 저장해야하는 경우에 사용 될 수 있음.

 

Note) 구현코드

<hide/>

#include <iostream>
#include <vector>
#include <list>
#include <functional>

template<typename T>
class SHashTable 
{
private:
    std::vector<std::list<T>> Data;
    size_t Capacity;
    std::function<size_t(const T&)> HashFunction;

public:
    SHashTable(size_t InCapacity, std::function<size_t(const T&)> InHashFunction)
        : Capacity(InCapacity)
        , HashFunction(InHashFunction)
    {
        Data.resize(Capacity);
    }

    void Insert(const T& InKey) 
    {
        size_t HashValue = HashFunction(InKey) % Capacity;
        auto& cell = Data[HashValue];
        for (const auto& element : cell)
        {
            if (InKey == element)
            {
                return; // 이미 존재하는 경우 삽입하지 않음
            }
        }
        cell.push_back(InKey);
    }

    bool Contain(const T& InKey) const 
    {
        size_t HashValue = HashFunction(InKey) % Capacity;
        const auto& cell = Data[HashValue];
        for (const auto& element : cell) 
        {
            if (InKey == element)
            {
                return true;
            }
        }
        return false;
    }

    void Remove(const T& InKey) 
    {
        size_t HashValue = HashFunction(InKey) % Capacity;
        auto& cell = Data[HashValue];
        cell.remove(InKey);
    }

    void Display() const 
    {
        for (size_t i = 0u; i < Capacity; ++i) 
        {
            std::cout << "Bucket " << i << ": ";
            for (const auto& element : Data[i]) 
            {
                std::cout << element << " -> ";
            }
            std::cout << "nullptr" << std::endl;
        }
    }
};

// 예제 해시 함수
int customHashFunction(const int& key) 
{
    return key * 3 + 7;
}