1. 해시함수란

해시 함수는 임의이 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수입니다. 암호 알고리즘에는 키가 사용되지만, 해시 함수는 키를 사용하지 않으므로 같은 입력에 대해서는 항상 같은 출력이 나오게 됩니다. 이러한 해시함수를 사용하는 목적은 메시지의 오류나 변조를 탐지할 수 있는 무결성을 제공하기 위해 사용됩니다.

눈사태 효과

눈사태 효과란 입력값의 아주 작은 변화로도 결과 값이 전혀 다르게 도출되는 효과!

---

2. 해시함수 코드

• 길이가 10 이하인 문자열을 key로, int를 value로 가지는 해시 테이블
• 함수 djb2는 문자열의 hash 함수 중 간략하면서도 무작위 분포를 만드는데 뛰어나다고 알려져 있습니다. magic number 5381과 33을 활용하여 hash key를 생성합니다.
• Chaining을 linked list로 구현했습니다.
• Single linked list이기 때문에 작업을 위해 이전 노드를 사용하고 있습니다.
• 노드에 원본 문자열을 복사하는 이유는 충돌 때문입니다. 해시값이 같다면 원본 문자열을 비교합니다.

#include <cstring>
#include <iostream>

using namespace std;



size_t djb2(const char* str) {
	size_t hash = 5381;
	for (; *str; ++str) {
		hash = ((hash << 5) + hash) + *str; // hash * 33 + c
	}
	return hash;
}

constexpr size_t MAX_N = 10000;
constexpr size_t MAX_LEN = 10;


struct Node {
	char str[MAX_LEN + 1];
	int data;
	Node* next;
};

int node_count = 0;
Node nodes[MAX_N];


Node* new_node(const char str[MAX_LEN + 1], int data) {
	strcpy(nodes[node_count].str, str);
	nodes[node_count].data = data;
	nodes[node_count].next = nullptr;
	return &nodes[node_count++];
}


class HashMap {
	static constexpr size_t TABLE_SIZE = 1 << 12; // 해시테이블 크기 2^12
	static constexpr size_t DIV = TABLE_SIZE - 1; // 2^12-1

	Node hash_table[TABLE_SIZE];
public:
	HashMap() = default;

	void init() {
		memset(hash_table, 0, sizeof(hash_table)); // 해시 테이블 초기화
		node_count = 0; // 해시 테이블의 node개수 초기화
	}


	void insert(const char str[MAX_LEN + 1], int data) {
		Node* prev_node = get_prev_node(str); // f(key)의 전 노드를 가져옵니다.
		if (prev_node->next == nullptr) { // 중복이 아닐 경우 맨 마지막에 노드 추가
			prev_node->next = new_node(str, data);
		}
		else { // 중복인 경우 str위치의 data의 값을 변경한다. 
			prev_node->next->data = data;
		}
	}

	void remove(const char str[MAX_LEN + 1]) {
		Node* prev_node = get_prev_node(str); // f(key)의 전 노드를 가져옵니다.
		if (prev_node->next != nullptr) { // 노드 뒤에 노드가 없으면
			prev_node->next = prev_node->next->next; // 다음 노드로 연결
		}
	}

	Node* get(const char str[MAX_LEN + 1]) {
		return get_prev_node(str)->next; // f(key)노드를 반환
	}

private:
	Node* get_prev_node(const char str[MAX_LEN + 1]) {
		Node* prev_ptr = &hash_table[djb2(str) & DIV]; // djb2(str) & DIV 모듈러 연산을 통해 hash_table의 크기를 넘지 못하게 한다.
		while (prev_ptr->next != nullptr && strcmp(prev_ptr->next->str, str) != 0) {
			prev_ptr = prev_ptr->next;
		}
		return prev_ptr; // f(key)의 전 노드 반환
	}
};


int main() {
	HashMap hash_map{};
	hash_map.init();
	hash_map.insert("1", 99);
	hash_map.insert("2", 88);
	hash_map.insert("3", 77);
	hash_map.insert("4", 66);
	hash_map.remove("2");
	cout << hash_map.get("4")->data;

	return 0;
}

---

해시함수 예시 문제

문제 15829

#include<iostream>
using namespace std;
const int M = 1234567891;
int L;
int H(string a) {
    long long hash = 0, r = 1;
    for (int i = 0; i < L; i++) {
        hash = (hash + (a[i] - 'a' + 1) * r) % M;
        r = (r * 31) % M;
    }
    return hash;
}
int main() {
    string str;
    cin >> L;
    cin >> str;
    cout << H(str);
}

위 코드는 해시 함수를 최대한 해시 충돌이 일어나지 않게 소수 31과 서로소이며 큰수 1234567891을 이용해 r = r*31로 r이 엄청나게 커지는 것을 대비하여 꾸준히 %M MOD연산을 하여 큰 수로 가는 것을 막습니다.

(a*b) mod n == (a mod n)*(b mod n)
모듈러 연산 성질을 이용하였습니다.

---

3. 해시함수를 활용한 헤더파일

Map

map은 연관 컨테이너로 원소를 key와 value의 쌍으로 저장한다. 연관 컨테이너는 균형 이진 트리를 이용하여 O(logN)의 시간 복잡도로 원하는 원소를 빠르게 찾을 수 있다.

1. map 헤더파일

#include <map>

2. map 선언

map<int, string> temp;

3. 원소 추가하기

#include <iostream>
#include <map>
using namespace std;
 
int main(){
    map<int, string> temp;
 
    temp.insert({1, "hello"});
    temp.insert(make_pair(2, "world"));
    temp[3] = "map";
 
    cout << temp[1] << '\n';
    cout << temp[2] << '\n';
    cout << temp[3] << '\n';
    
    cout << temp.size() << '\n';
    return 0;

세가지 방법이 있다

• 1. {} 이용
• 2. make_pair 이용
• 3. temp[key]=value 이용

4. map의 iterator 이용 예시

#include <iostream>
#include <map>
using namespace std;
 
int main(){
    map<int, string> temp;
 
    temp.insert({1, "hello"});
    temp.insert(make_pair(2, "world"));
    temp[3] = "map";
 
    map<int, string>::iterator iter;
    
    for(iter = temp.begin(); iter!=temp.end();iter++){
    	cout << iter->first << ',' << iter->second << '\n';
    }
    
    iter = temp.find(2);
    cout << iter->first << ',' << iter->second << '\n';
    
    
    return 0;
}

---

Set

set은 map과 거의 유사하지만 key(key = value)값만 존재한다

1. set 헤더파일

#include <set>

2. set 선언

set<int> temp;