IT 프로그래밍/알고리즘
[알고리즘] 해슁
기술1
2025. 6. 25. 15:14
Chaining
#include <iostream>
#include <list>
#include <vector>
using namespace std;
class HashTable {
int size;
vector<list<int>> table;
public:
HashTable(int m) : size(m), table(m) {}
int hash(int key) {
return key % size;
}
void insert(int key) {
int idx = hash(key);
table[idx].push_front(key); // 삽입은 맨 앞에
}
bool search(int key) {
int idx = hash(key);
for (int val : table[idx])
if (val == key) return true;
return false;
}
void remove(int key) {
int idx = hash(key);
table[idx].remove(key);
}
};
Open Addressing
class LinearProbingHash {
int size;
vector<int> table;
public:
LinearProbingHash(int m) : size(m), table(m, -1) {}
int hash(int key) {
return key % size;
}
void insert(int key) {
int idx = hash(key);
while (table[idx] != -1)
idx = (idx + 1) % size;
table[idx] = key;
}
bool search(int key) {
int idx = hash(key);
int start = idx;
while (table[idx] != -1) {
if (table[idx] == key) return true;
idx = (idx + 1) % size;
if (idx == start) break; // 무한루프 방지
}
return false;
}
void remove(int key) {
int idx = hash(key);
while (table[idx] != -1) {
if (table[idx] == key) {
table[idx] = -2; // 삭제된 자리 표시
return;
}
idx = (idx + 1) % size;
}
}
};Linear probing
Quadratic Probing
void insertQuadratic(vector<int>& table, int key, int m) {
int idx = key % m;
int i = 0;
while (table[(idx + i*i) % m] != -1) i++;
table[(idx + i*i) % m] = key;
}
Double Hashing
int h1(int k, int m) { return k % m; }
int h2(int k) { return 1 + (k % 11); } // m과 서로소
void insertDoubleHash(vector<int>& table, int key, int m) {
int i = 0;
while (true) {
int idx = (h1(key, m) + i * h2(key)) % m;
if (table[idx] == -1) {
table[idx] = key;
break;
}
i++;
}
}
Multiplication 해시 함수
int hashMultiplication(int k, int m) {
double A = 0.6180339887; // (sqrt(5) - 1)/2, Knuth 제안
double frac = fmod(k * A, 1.0); // 소수 부분만
return int(m * frac);
}
전체 코드
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <string>
#include <cmath>
using namespace std;
#define DELETED -2 // 삭제된 슬롯을 표시하기 위한 특별한 값
//----------------------------------
// Division 방식 해시 함수: key를 테이블 크기로 나눈 나머지
int hash_division(int key, int m) {
return key % m;
}
// Multiplication 방식 해시 함수: Knuth 제안 방식
int hash_multiplication(int key, int m) {
double A = 0.6180339887; // (sqrt(5) - 1) / 2
double frac = fmod(key * A, 1.0);
return int(m * frac);
}
// 문자열 해시 함수 (Java 스타일): 31진법을 사용한 누적 해싱
int hash_string_javaStyle(const string& s) {
int hash = 0;
for (char c : s)
hash = c + (31 * hash);
return hash;
}
//----------------------------------
// Chaining 방식 해시 테이블 클래스
class HashTable_Chain {
int size;
vector<list<int>> table;
public:
HashTable_Chain(int m) : size(m), table(m) {}
void insert(int key) {
int idx = hash_division(key, size);
table[idx].push_front(key); // 리스트 맨 앞에 삽입
}
bool search(int key) {
int idx = hash_division(key, size);
for (int val : table[idx])
if (val == key) return true;
return false;
}
void remove(int key) {
int idx = hash_division(key, size);
table[idx].remove(key); // 연결 리스트에서 제거
}
};
//----------------------------------
// Linear Probing 방식 해시 테이블 클래스
class HashTable_LinearProbing {
int size;
vector<int> table;
public:
HashTable_LinearProbing(int m) : size(m), table(m, -1) {}
int hash(int key) { return key % size; }
void insert(int key) {
int idx = hash(key);
while (table[idx] != -1 && table[idx] != DELETED)
idx = (idx + 1) % size;
table[idx] = key;
}
bool search(int key) {
int idx = hash(key);
int start = idx;
while (table[idx] != -1) {
if (table[idx] == key) return true;
idx = (idx + 1) % size;
if (idx == start) break;
}
return false;
}
void remove(int key) {
int idx = hash(key);
while (table[idx] != -1) {
if (table[idx] == key) {
table[idx] = DELETED;
return;
}
idx = (idx + 1) % size;
}
}
};
//----------------------------------
// Quadratic Probing 방식 해시 테이블 클래스
class HashTable_QuadraticProbing {
int size;
vector<int> table;
public:
HashTable_QuadraticProbing(int m) : size(m), table(m, -1) {}
void insert(int key) {
int i = 0;
int idx;
do {
idx = (key % size + i * i) % size;
if (table[idx] == -1 || table[idx] == DELETED) {
table[idx] = key;
return;
}
i++;
} while (i < size);
}
bool search(int key) {
int i = 0;
int idx;
do {
idx = (key % size + i * i) % size;
if (table[idx] == key) return true;
if (table[idx] == -1) return false;
i++;
} while (i < size);
return false;
}
};
//----------------------------------
// Double Hashing 방식 해시 테이블 클래스
class HashTable_DoubleHashing {
int size;
vector<int> table;
int h1(int key) { return key % size; }
int h2(int key) { return 1 + (key % (size - 2)); } // size와 서로소 필요
public:
HashTable_DoubleHashing(int m) : size(m), table(m, -1) {}
void insert(int key) {
int i = 0;
int idx;
while (i < size) {
idx = (h1(key) + i * h2(key)) % size;
if (table[idx] == -1 || table[idx] == DELETED) {
table[idx] = key;
return;
}
i++;
}
}
bool search(int key) {
int i = 0;
int idx;
while (i < size) {
idx = (h1(key) + i * h2(key)) % size;
if (table[idx] == key) return true;
if (table[idx] == -1) return false;
i++;
}
return false;
}
};
//----------------------------------
// 메인 함수: input.txt로부터 키 읽어오기
int main() {
ifstream inFile("input.txt");
if (!inFile) {
cerr << "파일을 열 수 없습니다." << endl;
return 1;
}
const int tableSize = 11; // 해시 테이블 크기
HashTable_Chain chain(tableSize);
HashTable_LinearProbing linear(tableSize);
HashTable_QuadraticProbing quad(tableSize);
HashTable_DoubleHashing dbl(tableSize);
int key;
cout << "파일로부터 키를 읽어와 삽입 중...\n";
while (inFile >> key) {
chain.insert(key);
linear.insert(key);
quad.insert(key);
dbl.insert(key);
}
// 예시: 검색 테스트
int target = 27;
cout << "\n--- 검색 결과 (key = " << target << ") ---\n";
cout << "[Chaining] " << (chain.search(target) ? "찾음" : "없음") << "\n";
cout << "[Linear Probing] " << (linear.search(target) ? "찾음" : "없음") << "\n";
cout << "[Quadratic Probing] " << (quad.search(target) ? "찾음" : "없음") << "\n";
cout << "[Double Hashing] " << (dbl.search(target) ? "찾음" : "없음") << "\n";
return 0;
}