[자료구조] 해시 [Hash]와 해시 테이블 [Hash Table]

해시 [Hash]

 

해시 함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. 그 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어어 널리 사용된다. 해시 함수는 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 데이터베이스 검색이나 테이블 검색의 속도를 가속할 수 있다.

 

저장된 키와 값을 이루는것을 테이블이라고 하는데 이중에 키에 해당하는 값을 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하기가 용이하게 만드는 작업이라고 할 수 있습니다. (사전을 생각해보면 적당한 비유가 될 것 같습니다.)

 

즉 , 해시를 이용하면, 즉시 저장하고자 하는 위치나 찾고자 하는 위치를 쉽게 찾을 수 있게 됩니다. 

(기존에 선형구조를 가지는 자료구조라면 탐색 시간이 O(n)이라는 시간이 소요되겠지만 테이블 자료구조의 탐색이 O(1)이기 떄문에

빠른 검색 및 삽입이 가능합니다.)

 

이런 구조를 Map , 또는 Dictionary라고도 합니다.(용어)

한 마디로, 공간과 시간을 교환하여 더 빠르게 사용할 수가 있습니다.

 

예를 들어서 "해시"라는 단어에 해시 함수를 적용해서 100이라는 색인이 생성되면,  리스트에 100번째 index에 해당 값을 저장하는 것 입니다.

 

[이미지 출처 : http://faculty.cs.niu.edu/]

 

해시 함수의 종류

 

이름	설명	특징
나눗셈	키 값이 정수 일때 이를 적당한 값으로 나누어 그 나머지를 사용하는 방식입니다.	단순합니다.
중간 제곱	키 값의 제곱에서 중간 자릿수를 선택하여 사용하는 방식입니다.	아주 작은 적재율 일때는 좋은 성능을 보이나, 많은 충돌이 발생할 수 있습니다.
폴딩 기법	키 전체를 균등한 크기로 나누고 , 이를 모두 더하거나 XOR 방식으로 사용하는 방식입니다.	계산하기에 용이하지만, 불규칙적인 결과를 가져올 수 있습니다.
기수 변환	어떠한 진법으로 표현된 키를 다른 진법으로 표현되었다고 가정하고 키를 변환하여 사용하는 방식입니다.	계산 방법이 비교적 복잡합니다.
자릿수 선택	키의 특정 위치에서 중복의 비율이 높거나, 공통으로 들어가는 값이 있다면, 이를 제외하고 나머지를 가지고 해시 값을 사용하는 방식입니다.	모든 키 값들이 미리 알려진 상태에서만 사용이 가능합니다.

 

그럼 배열을 사용하여 코드를 작성해보겠습니다.

struct User
{
    int ID;
    int Age;
    char Name[10];
};
 
void main()
{
    User userArray[1000];
 
    User user;
     
    cout << "ID와 나이 , 이름을 입력해주세요." << endl;
 
    cin >> user.ID >> user.Age >> user.Name;
 
    userArray[user.ID] = user;
 
    cout << "ID = " << userArray[user.ID].ID << " 나이 = " << 
        userArray[user.ID].ID << " 이름 = " << userArray[user.ID].Name << endl;
    
 
}

 

[결과]

유저의 ID를 고유 키값으로 사용하였고, 해당하는 키 값으로 바로 유저의 정보에 접근할 수 있었습니다. 

다만, 이럴 경우 고유 식별 ID에 따라서 배열의 크기가 늘어나게 됩니다.

(실제로 고유의 값을 가지는 ID의 경우 이렇게 짧을 수가 없겠지요..)

그럼 임의의 값으로 나눈 해시 값을 가지는 구조로 코드를 작성해보겠습니다.

 

int MakeHashKey(int _id)
{
    return _id * 0.01f;
}
 
struct User
{
    int ID;
    int Age;
 
    User(int _id , int _age )
        : ID(_id) , Age(_age) {}
 
    void ShowUserData()
    {
        cout << "유저의 ID = " << ID << " 유저의 나이 = " << Age << endl;
    }
 
};
 
User* MakeUserData(int _id, int _age)
{
    return new User(_id, _age);
}
 
struct Data
{
    int key;
    User* value;
 
    Data() 
    : key(0) , value(nullptr) {};
    Data(int _key , User* const _value)
        : key(_key) , value(_value){}
};
 
class HashTable
{
 
private :
 
    Data data[100];
 
public :
        
    HashTable() {};
 
    User* Find(int _key)
    {
        if (_key <= 0)
        {
            return nullptr;
        }
        else if (data[MakeHashKey(_key)].value == nullptr)
        {
            cout << "데이터 없음." << endl;
            return nullptr;
        }
        else
            return data[MakeHashKey(_key)].value;
    }
 
    void Add(int _key, User* const _value)
    {
        int hashValue = MakeHashKey(_key);
        
        Data newData;
        newData.key = _key;
        newData.value = _value;
 
        this->data[hashValue] = newData;
    }
 
    void Remove(int _key)
    {    
        int hashValue = MakeHashKey(_key);
 
        if (data[hashValue].value != nullptr)
        {
            this->data[hashValue].key = NULL;
            delete(data[hashValue].value);
            data[hashValue].value = nullptr;
        }
    }
 
};
 
void main()
{    
    HashTable hashTable;
 
    int id = 0;
    int age = 0;
 
    for (int i = 0; i < 1 ;i++)
    {
        cout << "아이디와 나이를 입력하세요." << endl;
 
        cin >> id >> age;
 
        hashTable.Add(id, MakeUserData(id, age));
    }
    
    cout << "검색할 아이디를 입력하세요." << endl;
 
    cin >> id;
 
    if (hashTable.Find(id) != nullptr)
        hashTable.Find(id)->ShowUserData();
 
    cout << "삭제할 아이디를 입력하세요." << endl;
    
    cin >> id;
 
    hashTable.Remove(id);
 
    cout << "검색할 아이디를 입력하세요." << endl;
 
    cin >> id;
 
    if (hashTable.Find(id) != nullptr)
        hashTable.Find(id)->ShowUserData();

 

[결과]

 

위에 구조로 그나마 해시를 사용하는 해시 테이블을 만들어본것 같습니다.

(작성하는 코드는 다 직접 작성하고 있으니 틀리면 말씀해주시길 ..)