해시는 key-value쌍으로 데이터를 저장하는 자료구조이다. 처음 들었을 때 파이썬의 딕셔너리와 같은 개념이지 않을까 생각했다. 비슷하지만 딕셔너리는 맨 처음 우리가 key:value 쌍으로 한번에 데이터를 저장하지만 해시는 key값을 넣으면 해시 함수를 통해 저장소의 적당한 위치에 value를 저장하는 자료구조이다.
임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어 주는 함수이다. 아래의 사진에서 원 안의 점들이 key 이며 해시 함수의 결과로 저장소의 해당되는 인덱스를 가르킨다. 해시에서 key를 해시한 결과를 저장소의 인덱스로 사용한다.
서로 다른 문자열을 해시한 결과가 동일한 경우 해시 충돌이 일어난다. H()를 해시함수라고 했을 때 H(Key1) = H(Key2)인 경우를 말한다. 해시 충돌이 일어나게 되면 Chaining 혹은 Open Addressing 등을 이용하여 해결한다.
Chaining 방법은 충돌을 허영하되 최소화 하는 방법으로 데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 형식이다. 충돌이 일어나면, 그 위치에 있던 데이터에 key값을 포인터로 뒤어서 연결한다. 이는 연결리스트와 비슷한 형태를 가지고 있으며, 해시 과정을 제외하곤 탐색, 삽입, 삭제 과정은 연결리스트와 유사한 방식으로 진행한다.
충돌이 적은 해시 함수를 만드는 방법에는 조건이 2개가 필요하다.
모든 데이터를 해시 테이블에 저장하는 방법으로, 포인터를 사용하지 않아 구현이 용이하며, 포인터 접근에 필요한 시간이 없기 때문에 큰 성능 향상을 보여준다.
Liner probing은 key값으로 인덱스를 계산 할 때, 만약 충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식이다. 만약 다음 인덱스에 데이터가 저장되어 있어 충돌이 다시 일어나게 되면 빈 인덱스가 나올 때 까지 이동하여 데이터를 저장한다.
Liner probing은 충돌이 일어날 경우 다음의 빈 인덱스 위치에 저장을 하므로, 특정 위치에 데이터들이 밀집하는 primary clustering 문제점이 있다. 이를 방지하기 위해 해시 함수를 2차식의 형태로 만든다.
Quadratic probing은 Liner probing와 달리 i가 1,2,4 이런식으로 증가하여 다음 인덱스를 찾는다.
Quadractic probing은 Liner probin의 문제점을 보완해 주지만 이 역시 secondary clustering 라는 문제점이 있다. secondary clustering은 처음 해시 값이 같을 경우, 그 이후의 해시값들도 모두 동일한 값으로 계산되어 충돌이 반복적으로 일어나는 것을 의미한다. 이를 해결하기 위해 해시 함수를 해시 함수 2개로 구현한 것이 double hashing이다.
프로그래머스 : 완주하지 못한 선수
백준 : 10816번, 1620번
#include <iostream> #include <string> #include <vector> using namespace std; class Node { public: string key; int value; bool finish; //완료자 명단 확인 Node* next; Node(string k, int v) { finish = false; this->key = k; this->value = v; this->next = NULL; } }; class HashLinkedlist { public: Node* head; Node* tail; HashLinkedlist() { head = tail = NULL; } bool empty() { return (head == NULL) & (tail == NULL); } void addValue(string key, int value) { Node* newnode = new Node(key, value); if (empty()) { head = tail = newnode; } else { tail->next = newnode; tail = newnode; } } }; class HashMap { public: vector<HashLinkedlist*> container; int storage_size; HashMap(int s) { this->storage_size = s; for (int i = 0; i < storage_size; i++) { //저장소 동적 할당 HashLinkedlist* newlist = new HashLinkedlist(); this->container.push_back(newlist); } } int hash(string key) { int hashvalue = -1; int tmp = 0; for (char c : key) { tmp += int(c); //해쉬 함수 : 문자열의 각각의 문자을 아스키 코드로 변환후 모두 더함. } hashvalue = tmp % storage_size; //그 다음 저장소의 갯수로 나눔. return hashvalue; } Node* findNodeByKey(string key, Node* container_cursor) { Node* now_cursor = container_cursor; while (now_cursor != NULL) { if (now_cursor->key == key) if (now_cursor->finish) { //동명이인 찾기 위한 코드, 만약 같은 이름이 나왓는데 완주를 햇으면 완주 안한 다른 사람을 찾음 now_cursor = now_cursor->next; } else { now_cursor->finish = true; return now_cursor; } else now_cursor = now_cursor->next; } return now_cursor; //키 값이 없을 경우 NULL를 리턴 } void putValue(string key) { int hashcode = this->hash(key); //key값을 해쉬함수를 이용하여 해쉬값으로 변환 this->container[hashcode]->addValue(key, hashcode); } }; string solution(vector<string> participant, vector<string> completion) { HashMap* hashmap = new HashMap(completion.size()); //완료자 사람 만큼 저장소 용량 확보 string answer = ""; for (int i = 0; i < completion.size(); i++) { hashmap->putValue(completion[i]); } for (int i = 0; i < participant.size(); i++) { int hashcode = hashmap->hash(participant[i]); //key값을 해쉬함수를 이용하여 해쉬값으로 변환 Node* cursor = hashmap->container[hashcode]->head; cursor = hashmap->findNodeByKey(participant[i], cursor); if (cursor == NULL) { answer = participant[i]; break; } } return answer; }
해시 자료구조는 처음 접해보는 자료구조라서 STL을 사용하지 않고 직접 구현해서 문제를 풀어보았다.
해시 충돌을 최소화 하기 위해 연결 리스트의 형식으로 구현 하였으며, 그에 필요한 Node
, Linkedlis
t을 이용하여 Hashmap
를 구현했다.
해시 함수는 들어오는 값이 사람 이름, 즉 문자 이므로 한글자마다 ASCII값으로 바꾼 다음 이를 총 갯수로 나누게 구현하였다.
Node
는 key, value 와 동명이인을 확인하는 변수를 저장하였다.
linkedlist
에서는 연결리스트가 비어있는지 확인하는 empty
와 head/tail에 노드를 추가하는 insert
을 구현하였다.
이를 가지고 Hashmap
에서는 주어진 key
값으로 해시값을 리턴하는 hash
와 key
를 가지고 value
를 찾은 findnodebykey
를 구현하였다.
먼저 완주를 한 선수들의 명단을 가지고 hashmap
에 저장을 하였다.
그 다음 참여자의 선수들에 대해서 각각 hash
을 통해서 key
에 해당되는 value
가 있는지 확인 하였다.
동명이인의 경우 Node
에 있는 변수를 통해 확인하였으며, 반복문을 수행하다가 저장이 안된 key
을 만나면 반복문을 종료하고 해당 key
를 answer
로 리턴하였다.
#include <iostream> #include <stdio.h> #include <cstdlib> #include <string> #include <vector> #include <cmath> using namespace std; class Node { public: int key; Node* next; int cnt = 1; Node(int k) { this->key = k; this->next = NULL; } }; class HashLinkedlist { public: Node* head; Node* tail; HashLinkedlist() { head = tail = NULL; } void addValueHead(int key) { Node* newnode = new Node(key); head = tail = newnode; } void addValueTail(int key) { Node* newnode = new Node(key); tail->next = newnode; tail = newnode; } }; class HashMap { public: HashLinkedlist* container; int storage_size; HashMap(int s) { container = new HashLinkedlist[s]; this->storage_size = s; } int hash(int key) { int hashvalue = abs(key) % storage_size; return hashvalue; } int findByKey(int key) { int count = 0; int hashcode = this->hash(key); Node* now_cursor = container[hashcode].head; if (now_cursor == NULL) { //키에 해당되는 곳이 비어있을 경우 0개 저장되어 있으므로 0 리턴 return count; } else { while (now_cursor != NULL) { if (key == now_cursor->key) { count = now_cursor->cnt; } now_cursor = now_cursor->next; } return count; } } void putValue(int key) { int hashcode = this->hash(key); Node* now_cursor = container[hashcode].head; if (now_cursor == NULL) { //키에 해당되는 곳이 비어있을 경우 0개 저장되어 있으므로 0 리턴 container[hashcode].addValueHead(key); } else { while (now_cursor != NULL) { if (key == now_cursor->key) { now_cursor->cnt++; return; } now_cursor = now_cursor->next; } container[hashcode].addValueTail(key); } } }; int main() { int my_card, card_key, find_card; scanf("%d", &my_card); HashMap H(my_card); for (int i = 0; i < my_card; i++) { scanf("%d", &card_key); H.putValue(card_key); } scanf("%d", &find_card); vector<int>card_list; for (int i = 0; i < find_card; i++) { scanf("%d", &card_key); card_list.push_back(card_key); } for (int i = 0; i < find_card; i++) { printf("%d ", H.findByKey(card_list[i])); } }
백준 문제 역시 해시를 직접 구현해서 풀었다.
위의 프로그래머스 문제와 다른점은 동명이인을 확인하는 변수 대신 해당 숫자가 몇번 들어왔는지 확인하는 변수 cnt
을 사용하였다.
또한 해시함수 역시 문자가 아니라서 숫자로 들어온 key
값에 절대값을 한 후에 총 숫자로 나누어 주었다.
그리고 해시함수로 key
값을 저장할때 만약 처음으로 저장이 새 노드를 만들어서 저장을 하지만 중복된 숫자가 들어온 경우는 cnt
값만 증가 시키고 다른 숫자지만 같은 해시값을 가지는 경우는 연결리스트로 뒤에 연결 해 주었다.
마지막으로 해당 숫자가 몇번 들어왓는지는 key
를 가지고 해시함수를 통해 저장소의 해당 인덱스로 가서 만약 해당 key
가 있다면 저장되어 있는 cnt
값을 출력하고 없다면 0을 출력하게 만들었다.
#include <iostream> #include <stdio.h> #include <string> #include <cctype> using namespace std; class Node { public: string key; int value; Node* next; Node(string k, int v) { this->key = k; this->value = v; this->next = NULL; } }; class HashLinkedlist { public: Node* head; Node* tail; HashLinkedlist() { head = tail = NULL; } bool empty() { return (head == NULL) & (tail == NULL); } void addValue(string key, int value) { Node* newnode = new Node(key, value); if (empty()) { head = tail = newnode; } else { tail->next = newnode; tail = newnode; } } }; class HashMap { public: HashLinkedlist* container; int storage_size; string* pkm_list; HashMap(int s) { container = new HashLinkedlist[s]; this->storage_size = s; pkm_list = new string[s + 1]; } int hash(string key) { int hashvalue = -1; int tmp = 0; for (char c : key) { tmp += (int)c; //해쉬 함수 : 문자열의 각각의 문자을 아스키 코드로 변환후 모두 더함. } hashvalue = tmp % storage_size; //그 다음 저장소의 갯수로 나눔. return hashvalue; } int findPKMNumberByKey(string key) { int hashcode = this->hash(key); Node* now_cursor = container[hashcode].head; while (now_cursor != NULL) { if (key == now_cursor->key) { return now_cursor->value; } now_cursor = now_cursor->next; } } string findPKMbyNum(int num) { return pkm_list[num]; } void putValue(string key, int num) { int hashcode = this->hash(key); //key값을 해쉬함수를 이용하여 해쉬값으로 변환 container[hashcode].addValue(key, num); pkm_list[num] = key; } }; int main() { int pkm_count, problem_count,pkm_number; string now_pkm; char* pkm = new char[20]; scanf("%d %d", &pkm_count, &problem_count); HashMap* hashmap = new HashMap(pkm_count); for (int i = 1; i < pkm_count+1; i++) { scanf("%s", pkm); hashmap->putValue(pkm,i); } char* test = new char[20]; for (int i = 0; i < problem_count; i++) { scanf("%s", test); if (isdigit(test[0]) == 0) { //문자인지 숫자인지 판별, 문자이면 0이 나옴 pkm_number = hashmap->findPKMNumberByKey(test); printf("%d\n", pkm_number); } else { ; now_pkm = hashmap->findPKMbyNum(stoi(test)); printf("%s\n", now_pkm.c_str()); } } }
문자열 관련 해시 문제라서 프로그래머스와 비슷하게 코딩을 하였다.
중복된 포켓몬이 없으므로 동명이인을 확인하는 변수는 삭제하였고, Hashmap
에서 포켓몬을 담는 string
배열을 하나 만들어 줬다.
stirng
배열은 포켓몬이 들어오면 순서대로 저장을 해주었다.
key
를 입력하면 해당 key
에 해당되는 인덱스에 포켓몬이 몇번째로 들어왓는지 저장하였고, 출력할 때는 key
값으로 해시 함수를 통해 해당 인덱스에 저장된 포켓몬 번호를 리턴했다.
만약 포켓몬이 아닌 포켓몬 번호로 들어온 경우 Hashmap
에 만들어 놓은 string
배열에서 해당 번호(인덱스)에 있는 포켓몬을 리턴했다.