본문 바로가기

삼성전자 알고리즘/자료구조 알고리즘

1. 해싱 [Hashing]

출처 : 위키피디아

Why ?

1.하나의 문자열을 보다 빨리 찾을 수 있도록 사용.

 

How?

1.인덱스에 직접 접근할 수 있는 짧은 길이의 값이나 키로 변환.

 

2.다양한 구현 기법 존재.

  2-1. 나눗셈 방법 (The division method) : h(k) = k mod m

    2-1-a. m = 2^p인 경우는 피하는 것이 좋다.

    2-1-b. m= 2^p - 1 인 경우도 피하는 것이 좋다.

    2-1-c. 2^p에 너무 가깝지 않은 소수를 선택하는 것이 좋다.

       ex) 키의 수가 2,000 일 때 해쉬 테이블의 크기를 m = 701로 잡으면 좋다. (amortized analysis에 의해 3으로 나누는 것이 효율적이라 고 밝혀짐. 

출처 : Tacademy_10강 컴퓨터 알고리즘 기초 10강 해쉬 알고리즘(1) | T아카데미 https://youtu.be/9YfCORwU9Uc 

 

3. 해쉬 함수와 key

  3-1. 해쉬함수에서는 key값을 자연수로 가정

  3-2. 만약 key가 자연수가 아닌 character나 string의 형태라면 자연수 형태로 변형하여 사용.

 

Plus

1.메모리를 많이 차지하는 단점 존재.

 

2.해싱 충돌을 해결해야 함. (Chained Hash Table)

 

3. 좋은 해쉬 함수 :

  3-1. 좋은 해쉬 함수는 simple uniform hashing을 만족하는 해쉬 함수이다.

    3-1-a. 각각의 key는 중복 없이 m개의 slot으로 동일한 확률로 해쉬 되며 (simple)

    3-1-b. 각각의 key는 다른 key값의 해쉬값과 관계없이 해쉬 된다. (Uniformly)

  3-2. 즉 좋은 해쉬 함수는 모든 값이 골고루 나오는 것이다. :

         (m개의 slot이 있으면 중복 없이 확률적으로 m개의 slot에 골고루 나누어지는 것)

 

Problem

1.BOJ 1920 문제 : https://www.acmicpc.net/problem/1920

 

1920번: 수 찾기

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

www.acmicpc.net

1-1.문제 풀이 : 

//해시 구현 참조 : http://bitly.kr/8r2jAs
#include<iostream>
#define MAX_HASH 4294967    // int 범위를 1000으로 나눈 값

using namespace std;

typedef struct Node
{
    int id;
    Node* hashNext;
}Node;

Node* hashTable[MAX_HASH]; //int 범위를 1000으로 나눈 값을 크기로 갖는 해시테이블 생성.
//해쉬함수
int HASH_KEY(int data){
    int key;
    if(data <0){
        key = data / 1000;
        key *= -1;
    }else{
        key = data / 1000;
        key *= 2;
    }
    return key;
}
//linkedList로 연결
void  AddHashData(int key, Node* node)
{
    int hash_key = HASH_KEY(key);
    if (hashTable[hash_key] == NULL)
    {
        hashTable[hash_key] = node;
    }
    else
    {
        node->hashNext = hashTable[hash_key];
        hashTable[hash_key] = node;
    }
}
int FindHashData(int id)
{
    int hash_key = HASH_KEY(id);
    if (hashTable[hash_key] == NULL)
        return 0;   //못찾으면 0
    
    if (hashTable[hash_key]->id == id)
    {
        //        return hashTable[hash_key];
        return 1;   //찾으면 1
    }
    else
    {
        Node* node = hashTable[hash_key];
        while (node->hashNext)
        {
            if (node->hashNext->id == id)
            {
                //                return node->hashNext;
                return 1;
                
            }
            node = node->hashNext; //찾을 떄까지 검색
        }
    }
    return  0;
}


int main()
{
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int nInput;
        cin >> nInput;
        Node* node = new Node();
        node->id = nInput;
        node->hashNext = NULL;
        AddHashData(node->id, node);
    }
    int M;
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        int mInput;
        scanf("%d",&mInput); //시간 초과 때문에 scanf / printf 사용
        printf("%d \n",FindHashData(mInput));
    }
    return 0;   
}

2. C++ STL 사용법 :

//출처 : http://bitly.kr/486OiE
//https://stackoverflow.com/questions/3578083/what-is-the-best-way-to-use-a-hashmap-in-c
#include <map>
#include <iostream>
#include <cassert>

using namespace std;
int main(){
    map<int, int> hash_map;
    hash_map[100] = 10;
    if(hash_map.find(10) != hash_map.end()){
        cout<<"map contains key!!"<<endl;
    }
    if(hash_map.find(100) != hash_map.end()){
        cout<<"map contains key!!"<<endl;
    }
    cout<<hash_map[100]<<endl;
    map<int, int>::iterator i = hash_map.find(100);
    assert(i!=hash_map.end());
    cout<<"Key: "<<i->first<<" Value: "<<i->second<<endl;
    
    return 0;
}

 

준비하면서 계속 업데이트 하겠음. 19.05.06 수정됨.