탐색2 : Hashing

'

용어 정의 

해시함수 : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 균일하게 매핑할수록 좋은 해시함수이다.

해시 : 해시 함수에 얻어지는 값

해시 테이블 : 해시 값을 인덱스로 하여 데이터를 저장하고 있는 자료구조

 

Hashing

• 정의 : 데이터를 담을 해시 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시함수에 의해 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 과정
• 장점 : 데이터 접근 속도가 빠르다.
• 단점 : 충돌(collision)발생 - 서로 다른 입격 값에 대해 동일한 해시 테이블 주소를 반환하는 경우
• 해결법
  • chaining : 충돌되는 데이터들을 해당 주소에 링크드 리스트로 연결
  • open addressing : 충돌 발생시 해당 주소에 고정 폭 만큼을 더한 주소 값에 데이터 저장
    • linear probing : 고정 폭의 값을 1로 설정하여 선형적으로 빈 주소를 탐색
    • double hashing : 제 2의 해시함수의 값을 고정 폭의 값으로 설정하여 해시테이블 내의 클러스터를 방지
• 예시코드

// double hashing

#include <iostream>
#include <vector>

using namespace std;
#define AVAILABLE 0
#define OCCUPIED 1

class Node {
public:
	int key;
	int value;
	bool state;
	Node(int k, int v) {
		key = k;
		value = v;
		state = OCCUPIED;
	}
};

class hashmap {
public:
	int cap;
	vector<Node*> bucketArr;

	hashmap() {
		cap = 353333;
		bucketArr.resize(cap, NULL);
	}

	int hashCode(int k) { // key ->integer
		return k;
	}

	int compFunc(int in) { //integer -> hashvalue
		int ret = in % cap;
		return ret;
	}

	int hashFunc(int k) { //key -> hash value
		return compFunc(hashCode(k));
	}

	int doubleHashFunc(int k) {
		return (17 - (hashCode(k) % 17));
	}

	int insert(int k, int v) { //key, value 저장하고 저장한 위치 반환

		int idx = hashFunc(k);
		int dHashVal = doubleHashFunc(k);

		while (1) {
			if (bucketArr[idx] == NULL) {
				bucketArr[idx] = new Node(k,v);
				break;
			}
			idx = (idx + dHashVal) % cap;
		}

		return idx;
	}

	int search(int k) { //double hashing's search : 해당 키값의 위치 반환
		int idx = hashFunc(k);
		int probnum = 1;
		int dhashVal = doubleHashFunc(k);

		for (int i = 0; i < cap; i++) {

			if (bucketArr[idx] == NULL) {
				idx = -1;
				break;
			}
			else if (bucketArr[idx]->state == AVAILABLE) {
				idx = (idx + dhashVal) % cap;
				probnum++;
			}
			else if (bucketArr[idx]->key == k) {
				break;
			}
			else {
				idx = (idx + dhashVal) % cap;
				probnum++;
			}
		}
		if (idx <= -1)
			cout << 0 << ' ' << probnum << endl;
		else
			cout << 1 << ' ' << probnum << endl;

		return idx;
	}

	void remove(int k) {
		int idx = search(k);
		if (idx == -1)
			return;
		else
			bucketArr[idx]->state = AVAILABLE;
		return;
	}
};


int main() {

	int testcase = 0;
	cin >> testcase;

	for (int i = 0; i < testcase; i++) {
		hashmap map;
		int size = 0;
		cin >> size;
		for (int a = 0; a < size; a++) {
			int k = 0;
			int v = 0;
			cin >> k;
			cin >> v;
			map.insert(k, v);
		}

		int num = 0;
		cin >> num;

		for (int b = 0; b < num; b++) {
			int search = 0;
			cin >> search;
			map.search(search);
		}
	}
	return 0;
}