8000 0x15 hash · hyperminji/basic-algo-lecture@6fa2e70 · GitHub
[go: up one dir, main page]
Skip to content

Commit 6fa2e70

Browse files
encrypted-defencrypted-def
committed
0x15 hash
1 parent 791cab6 commit 6fa2e70

9 files changed

+459
-0
lines changed

‎0x15/1620.cpp

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
// http://boj.kr/6c00940e0dab4c4e994d524d38e5582c
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
unordered_map<string, int> s2i;
6+
string i2s[100005];
7+
8+
int main(void){
9+
ios::sync_with_stdio(0);
10+
cin.tie(0);
11+
int n, m;
12+
cin >> n >> m;
13+
for(int i = 1; i <= n; i++){
14+
cin >> i2s[i];
15+
s2i[i2s[i]] = i;
16+
}
17+
while(m--){
18+
string query;
19+
cin >> query;
20+
if(isdigit(query[0]))
21+
cout << i2s[stoi(query)] << '\n';
22+
else
23+
cout << s2i[query] << '\n';
24+
}
25+
}

‎0x15/7785.cpp

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
// http://boj.kr/b88f0e4817f94b0fa6080d56952fd1fe
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
unordered_set<string> s;
6+
7+
int main(void){
8+
ios::sync_with_stdio(0);
9+
cin.tie(0);
10+
11+
int n;
12+
cin >> n;
13+
while(n--){
14+
string name, log;
15+
cin >> name >> log;
16+
if(log == "enter") s.insert(name);
17+
else s.erase(name);
18+
}
19+
vector<string> ans(s.begin(), s.end());
20+
sort(ans.begin(), ans.end(), greater<string>());
21+
for(auto x : ans) cout << x << '\n';
22+
}

‎0x15/hash_chaining_test.cpp

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
#include <bits/stdc++.h>
2+
using namespace std;
3+
4+
const int M = 1000003;
5+
const int a = 1000;
6+
7+
const int MX = 500005; // 최대 삽입 횟수
8+
int head[M];
9+
int pre[MX];
10+
int nxt[MX];
11+
string key[MX];
12+
int val[MX];
13+
int unused = 0;
14+
15+
int my_hash(string& s){
16+
int h = 0;
17+
for(auto x : s)
18+
h = (h * a + x) % M;
19+
return h;
20+
}
21+
22+
// key[idx] == k인 idx를 반환, 만약 k가 존재하지 않을 경우 -1을 반환
23+
// key에 대응되는 value를 반환하는게 아니라 인덱스를 반환함에 주의
24+
int find(string k){
25+
26+
}
27+
28+
void insert(string k, int v){
29+
30+
}
31+
32+
void erase(string k){
33+
34+
}
35+
36+
void test(){
37+
insert("orange", 724); // ("orange", 724)
38+
insert("melon", 20); // ("orange", 724), ("melon", 20)
39+
assert(val[find("melon")] == 20);
40+
insert("banana", 52); // ("orange", 724), ("melon", 20), ("banana", 52)
41+
insert("cherry", 27); // ("orange", 724), ("melon", 20), ("banana", 52), ("cherry", 27)
42+
insert("orange", 100); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
43+
assert(val[find("banana")] == 52);
44+
assert(val[find("orange")] == 100);
45+
erase("wrong_fruit"); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
46+
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
47+
assert(find("orange") == -1);
48+
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
49+
insert("orange", 15); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15)
50+
assert(val[find("orange")] == 15);
51+
insert("apple", 36); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36)
52+
insert("lemon", 6); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36), ("lemon", 6)
53+
insert("orange", 701); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 701), ("apple", 36), ("lemon", 6)
54+
assert(val[find("cherry")] == 27);
55+
erase("xxxxxxx");
56+
assert(find("xxxxxxx") == -1);
57+
assert(val[find("apple")] == 36);
58+
assert(val[find("melon")] == 20);
59+
assert(val[find("banana")] == 52);
60+
assert(val[find("cherry")] == 27);
61+
assert(val[find("orange")] == 701);
62+
assert(val[find("lemon")] == 6);
63+
cout << "good!\n";
64+
}
65+
66+
67+
int main(){
68+
fill(head, head+M, -1);
69+
fill(pre, pre+MX, -1);
70+
fill(nxt, nxt+MX, -1);
71+
test();
72+
}

‎0x15/hash_chaining_test_ans.cpp

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
#include <bits/stdc++.h>
2+
using namespace std;
3+
4+
const int M = 1000003;
5+
const int a = 1000;
6+
const int MX = 500005; // 최대 삽입 횟수
7+
int head[M];
8+
int pre[MX];
9+
int nxt[MX];
10+
string key[MX];
11+
int val[MX];
12+
int unused = 0;
13+
14+
int my_hash(string& s){
15+
int h = 0;
16+
for(auto x : s)
17+
h = (h * a + x) % M;
18+
return h;
19+
}
20+
21+
// key[idx] == k인 idx를 반환, 만약 k가 존재하지 않을 경우 -1을 반환
22+
// 키에 대응되는 값을 반환하는게 아니라 인덱스를 반환함에 주의
23+
int find(string k){
24+
int h = my_hash(k);
25+
int idx = head[h];
26+
while(idx != -1){
27+
if(key[idx] == k) return idx;
28+
idx = nxt[idx];
29+
}
30+
return -1;
31+
}
32+
33+
void insert(string k, int v){
34+
int idx = find(k);
35+
if(idx != -1){
36+
val[idx] = v;
37+
return;
38+
}
39+
int h = my_hash(k);
40+
key[unused] = k;
41+
val[unused] = v;
42+
if(head[h] != -1){
43+
nxt[unused] = head[h];
44+
pre[head[h]] = unused;
45+
}
46+
head[h] = unused;
47+
unused++;
48+
}
49+
50+
void erase(string k){
51+
int idx = find(k);
52+
if(idx == -1) return;
53+
if(pre[idx] != -1) nxt[pre[idx]] = nxt[idx];
54+
if(nxt[idx] != -1) pre[nxt[idx]] = pre[idx];
55+
int h = my_hash(k);
56+
if(head[h] == idx) head[h] = nxt[idx];
57+
}
58+
59+
void test(){
60+
insert("orange", 724); // ("orange", 724)
61+
insert("melon", 20); // ("orange", 724), ("melon", 20)
62+
assert(val[find("melon")] == 20);
63+
insert("banana", 52); // ("orange", 724), ("melon", 20), ("banana", 52)
64+
insert("cherry", 27); // ("orange", 724), ("melon", 20), ("banana", 52), ("cherry", 27)
65+
insert("orange", 100); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
66+
assert(val[find("banana")] == 52);
67+
assert(val[find("orange")] == 100);
68+
erase("wrong_fruit"); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
69+
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
70+
assert(find("orange") == -1);
71+
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
72+
insert("orange", 15); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15)
73+
assert(val[find("orange")] == 15);
74+
insert("apple", 36); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36)
75+
insert("lemon", 6); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36), ("lemon", 6)
76+
insert("orange", 701); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 701), ("apple", 36), ("lemon", 6)
77+
assert(val[find("cherry")] == 27);
78+
erase("xxxxxxx");
79+
assert(find("xxxxxxx") == -1);
80+
assert(val[find("apple")] == 36);
81+
assert(val[find("melon")] == 20);
82+
assert(val[find("banana")] == 52);
83+
assert(val[find("cherry")] == 27);
84+
assert(val[find("orange")] == 701);
85+
assert(val[find("lemon")] == 6);
86+
cout << "good!\n";
87+
}
88+
89+
int main(){
90+
fill(head, head+M, -1);
91+
fill(pre, pre+MX, -1);
92+
fill(nxt, nxt+MX, -1);
93+
test();
94+
}

‎0x15/hash_open_addressing_test.cpp

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
#include <bits/stdc++.h>
2+
using namespace std;
3+
4+
const int M = 1000003;
5+
const int a = 1000;
6+
const int EMPTY = -1;
7+
const int OCCUPY = 0;
8+
const int DUMMY = 1;
9+
int status[M]; // EMPTY / OCCUPY / DUMMY
10+
string key[M];
11+
int val[M];
12+
13+
int my_hash(string& s){
14+
int h = 0;
15+
for(auto x : s)
16+
h = (h * a + x) % M;
17+
return h;
18+
}
19+
20+
// key[idx] == k인 idx를 반환, 만약 k가 존재하지 않을 경우 -1을 반환
21+
// key에 대응되는 value를 반환하는게 아니라 인덱스를 반환함에 주의
22+
int find(string k){
23+
24+
}
25+
26+
void insert(string k, int v){
27+
28+
}
29+
30+
void erase(string k){
31+
32+
}
33+
34+
void test(){
35+
insert("orange", 724); // ("orange", 724)
36+
insert("melon", 20); // ("orange", 724), ("melon", 20)
37+
assert(val[find("melon")] == 20);
38+
insert("banana", 52); // ("orange", 724), ("melon", 20), ("banana", 52)
39+
insert("cherry", 27); // ("orange", 724), ("melon", 20), ("banana", 52), ("cherry", 27)
40+
insert("orange", 100); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
41+
assert(val[find("banana")] == 52);
42+
assert(val[find("orange")] == 100);
43+
erase("wrong_fruit"); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
44+
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
45+
assert(find("orange") == -1);
46+
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
47+
insert("orange", 15); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15)
48+
assert(val[find("orange")] == 15);
49+
insert("apple", 36); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36)
50+
insert("lemon", 6); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36), ("lemon", 6)
51+
insert("orange", 701); // ("melon", 20), ("banana", 52), ("ch F438 erry", 27), ("orange", 701), ("apple", 36), ("lemon", 6)
52+
assert(val[find("cherry")] == 27);
53+
erase("xxxxxxx");
54+
assert(find("xxxxxxx") == -1);
55+
assert(val[find("apple")] == 36);
56+
assert(val[find("melon")] == 20);
57+
assert(val[find("banana")] == 52);
58+
assert(val[find("cherry")] == 27);
59+
assert(val[find("orange")] == 701);
60+
assert(val[find("lemon")] == 6);
61+
cout << "good!\n";
62+
}
63+
64+
int main(){
65+
fill(status, status+M, EMPTY);
66+
test();
67+
}

‎0x15/hash_open_addressing_test_ans.cpp

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
#include <bits/stdc++.h>
2+
using namespace std;
3+
4+
const int M = 1000003;
5+
const int a = 1000;
6+
const int EMPTY = -1;
7+
const int OCCUPY = 0;
8+
const int DUMMY = 1;
9+
int status[M]; // EMPTY / OCCUPY / DUMMY
10+
string key[M];
11+
int val[M];
12+
13+
int my_hash(string& s){
14+
int h = 0;
15+
for(auto x : s)
16+
h = (h * a + x) % M;
17+
return h;
18+
}
19+
20+
// key[idx] == k인 idx를 반환, 만약 k가 존재하지 않을 경우 -1을 반환
21+
// key에 대응되는 value를 반환하는게 아니라 인덱스를 반환함에 주의
22+
int find(string k){
23+
int idx = my_hash(k);
24+
while(status[idx] != EMPTY){
25+
if(status[idx] == OCCUPY && key[idx] == k) return idx;
26+
idx = (idx+1) % M;
27+
}
28+
return -1;
29+
}
30+
31+
void insert(string k, int v){
32+
int idx = find(k);
33+
if(idx != -1){
34+
val[idx] = v;
35+
return;
36+
}
37+
idx = my_hash(k);
38+
while(status[idx] == OCCUPY)
39+
idx = (idx+1) % M;
40+
key[idx] = k;
41+
val[idx] = v;
42+
status[idx] = OCCUPY;
43+
}
44+
45+
void erase(string k){
46+
int idx = find(k);
47+
if(idx != -1) status[idx] = DUMMY;
48+
}
49+
50+
void test(){
51+
insert("orange", 724); // ("orange", 724)
52+
insert("melon", 20); // ("orange", 724), ("melon", 20)
53+
assert(val[find("melon")] == 20);
54+
insert("banana", 52); // ("orange", 724), ("melon", 20), ("banana", 52)
55+
insert("cherry", 27); // ("orange", 724), ("melon", 20), ("banana", 52), ("cherry", 27)
56+
insert("orange", 100); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
57+
assert(val[find("banana")] == 52);
58+
assert(val[find("orange")] == 100);
59+
erase("wrong_fruit"); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
60+
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
61+
assert(find("orange") == -1);
62+
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
63+
insert("orange", 15); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15)
64+
assert(val[find("orange")] == 15);
65+
insert("apple", 36); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36)
66+
insert("lemon", 6); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36), ("lemon", 6)
67+
insert("orange", 701); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 701), ("apple", 36), ("lemon", 6)
68+
assert(val[find("cherry")] == 27);
69+
erase("xxxxxxx");
70+
assert(find("xxxxxxx") == -1);
71+
assert(val[find("apple")] == 36);
72+
assert(val[find("melon")] == 20);
73+
assert(val[find("banana")] == 52);
74+
assert(val[find("cherry")] == 27);
75+
assert(val[find("orange")] == 701);
76+
assert(val[find("lemon")] == 6);
77+
cout << "good!\n";
78+
}
79+
80+
int main(){
81+
fill(status, status+M, EMPTY);
82+
test();
83+
}

0 commit comments

Comments
 (0)
0