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 수정됨.
'삼성전자 알고리즘 > 자료구조 알고리즘' 카테고리의 다른 글
5. 우선순위 큐 (0) | 2019.05.14 |
---|---|
4. 순열, 조합 (0) | 2019.05.12 |
3. 재귀함수를 비재귀함수로 변환 (0) | 2019.05.06 |
2. 링크드 리스트 [Linked List] (0) | 2019.04.14 |
0.SW 역량테스트 B형 파악하기 (0) | 2019.04.14 |