해시(Hash_map) 자료구조

고명한·2021년 5월 11일
1

📒 해시 자료구조

📌해시(Hash-map)

✍해시(Hash-map)란?

해시는 key-value쌍으로 데이터를 저장하는 자료구조이다. 처음 들었을 때 파이썬의 딕셔너리와 같은 개념이지 않을까 생각했다. 비슷하지만 딕셔너리는 맨 처음 우리가 key:value 쌍으로 한번에 데이터를 저장하지만 해시는 key값을 넣으면 해시 함수를 통해 저장소의 적당한 위치에 value를 저장하는 자료구조이다.

✍해시 함수(Hash-function)

임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어 주는 함수이다. 아래의 사진에서 원 안의 점들이 key 이며 해시 함수의 결과로 저장소의 해당되는 인덱스를 가르킨다. 해시에서 key를 해시한 결과를 저장소의 인덱스로 사용한다.

✍해시 충돌(Hash-Collision)

서로 다른 문자열을 해시한 결과가 동일한 경우 해시 충돌이 일어난다. H()를 해시함수라고 했을 때 H(Key1) = H(Key2)인 경우를 말한다. 해시 충돌이 일어나게 되면 Chaining 혹은 Open Addressing 등을 이용하여 해결한다.

✍해시 충돌 최소화

👉 Chaining 방법

Chaining 방법은 충돌을 허영하되 최소화 하는 방법으로 데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 형식이다. 충돌이 일어나면, 그 위치에 있던 데이터에 key값을 포인터로 뒤어서 연결한다. 이는 연결리스트와 비슷한 형태를 가지고 있으며, 해시 과정을 제외하곤 탐색, 삽입, 삭제 과정은 연결리스트와 유사한 방식으로 진행한다.

Simple uniform hash

충돌이 적은 해시 함수를 만드는 방법에는 조건이 2개가 필요하다.

  • 계산된 해시값들은 0부터 배열의 크기-1 사이의 범위를 '동일한 확률'로 골고루 나타날 것
    ->이 조건을 만족하면 충돌이 일어날 확률이 적어진다.
  • 각각의 해시값들은 서로 연관성을 가지고 않고 독립적으로 생성될 것
    ->서로 연관성을 가지고 있다면 해시값들이 등장하는 패턴이나 순서가 존재 할 수 있으며, 이는 해시 충돌을 일으킬 확률이 있다.

Division method

  • 해시 함수를 만들때 대표적으로 사용하는 방법, Modular 연산 방법을 이용하여, 특정 key값을 어떤 수로 나눈 나머지를 해시값으로 사용한다.
  • 나누는 수에 따라서 테이블의 성능을 크게 좌우 하는데, 보통 키의 수의 3배, 그리고 2의 p승에 근접하는 수가 충돌을 일으킬 가능성이 적다고 알려져 있다.

👉 Open Addressing 방법

모든 데이터를 해시 테이블에 저장하는 방법으로, 포인터를 사용하지 않아 구현이 용이하며, 포인터 접근에 필요한 시간이 없기 때문에 큰 성능 향상을 보여준다.

Liner probing

Liner probing은 key값으로 인덱스를 계산 할 때, 만약 충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식이다. 만약 다음 인덱스에 데이터가 저장되어 있어 충돌이 다시 일어나게 되면 빈 인덱스가 나올 때 까지 이동하여 데이터를 저장한다.

Quadratic probing

Liner probing은 충돌이 일어날 경우 다음의 빈 인덱스 위치에 저장을 하므로, 특정 위치에 데이터들이 밀집하는 primary clustering 문제점이 있다. 이를 방지하기 위해 해시 함수를 2차식의 형태로 만든다.
Quadratic probing은 Liner probing와 달리 i가 1,2,4 이런식으로 증가하여 다음 인덱스를 찾는다.

Double hashing

Quadractic probing은 Liner probin의 문제점을 보완해 주지만 이 역시 secondary clustering 라는 문제점이 있다. secondary clustering은 처음 해시 값이 같을 경우, 그 이후의 해시값들도 모두 동일한 값으로 계산되어 충돌이 반복적으로 일어나는 것을 의미한다. 이를 해결하기 위해 해시 함수를 해시 함수 2개로 구현한 것이 double hashing이다.

✍해시 테이블 STL : unordered_map

  • unordered_map은 해시 테이블로 구현한 자료구조로 탐색 시간 복잡도는 O(1)이 걸린다.
  • #include <unordered_map>을 선언하여 unordered_map을 사용한다.
  • unordered_map은 중복된 데이터를 허용하지 않고, 데이터가 많을 시 월등히 좋은 성능을 보인다.
  • 하지만 유사한 데이터가 많은 key 경우 해시 충돌로 인해 성능이 떨어질 수도 있다.

👉unodrded_map 함수


👉unodrded_map의 탐색 방법

  • index로 접근할 수 없고 iterator로 접근해야 한다.
  • 시작 : begin(), 끝 : end()
  • key : iter->first, value : iter-> second로 접근 가능하다.
  • 반복문 사용시 auto 또는 pair을 사용한다.

📌문제

프로그래머스 : 완주하지 못한 선수
백준 : 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, Linkedlist을 이용하여 Hashmap를 구현했다.
해시 함수는 들어오는 값이 사람 이름, 즉 문자 이므로 한글자마다 ASCII값으로 바꾼 다음 이를 총 갯수로 나누게 구현하였다.
Node는 key, value 와 동명이인을 확인하는 변수를 저장하였다.
linkedlist에서는 연결리스트가 비어있는지 확인하는 empty와 head/tail에 노드를 추가하는 insert을 구현하였다.
이를 가지고 Hashmap에서는 주어진 key값으로 해시값을 리턴하는 hashkey를 가지고 value를 찾은 findnodebykey를 구현하였다.
먼저 완주를 한 선수들의 명단을 가지고 hashmap에 저장을 하였다.
그 다음 참여자의 선수들에 대해서 각각 hash을 통해서 key에 해당되는 value가 있는지 확인 하였다.
동명이인의 경우 Node에 있는 변수를 통해 확인하였으며, 반복문을 수행하다가 저장이 안된 key을 만나면 반복문을 종료하고 해당 keyanswer로 리턴하였다.

📄 10816번 : 숫자카드 2


#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을 출력하게 만들었다.

📄 1620번 : 나는야 포켓몬 마스터 이다솜


#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 배열에서 해당 번호(인덱스)에 있는 포켓몬을 리턴했다.

profile
빛으로 평가받는 날까지

0개의 댓글