-
Notifications
You must be signed in to change notification settings - Fork 0
/
09 해싱과 해시함수.cpp
143 lines (101 loc) · 4.52 KB
/
09 해싱과 해시함수.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
using namespace std;
/*
ㅇ해싱(hashing)
-각각의 데이터를 (가급적) 고유한 숫자 값으로 표현하고, 이를 이용하여 특정 데이터 존재 여부를 확인하거나 또는 원본 데이터를 추출하는 작업을 할 수 있다.
//음.. 즉 주어진 데이터로부터 고유한 숫자 값을 생성해서 반환하는게 해쉬함수인데
// key값을 해싱함수에 넣어 고유한 값을, 해시 테이블 참조에 사용하여 그에 맞는 해시 테이블의 인덱스의 값을 추출하거나 확인이 가능하다.
//아니면 그 키값을 받아서 해쉬함수에 넣어 고유의 값을 해쉬 테이블의 인덱스에 저장할 수 있다.
ㅇ해싱이 필요한 경우의 예
-요구사항 : 정수를 저장하고있는 컨테이너가 있고, 이 컨테이너에 특정 정수가 들어있는지를 빠르게 판단하고 싶을때.
-해결방법 : 적절한 크기의 bool타입 배열을 하나 만들고, 이 배열에서 입력 정수에 해당하는 인덱스의 원소 값을 true로 설정할 수 있다.
bool data[8] = {}; // false로 초기화
data[2] = true;
data[4] = true;
data[5] = true;
data[7] = true;
-> 데이터를 뽑아네 true면 있다는것
-문제점 : 정수 범위가 너무 크다면? 데이터가 실수 라면? 데이터가 숫자가 아니라면?
-> 입력되는 정수값을 특정 범위의 정수갑으로 변환하는 매핑함수를 만들어서 사용할 수 있다.
ex) hash(x) = x% n
---- 해시함수 --- 해시 값
bool data[7] = {}; // false로 초기화
data[2 % 7] = true;
data[4 % 7] = true;
data[5 % 7] = true;
data[7 % 7] = true;
data[9999 % 7] = true;
주어진 데이터배열 7개중에서 5개의 원소값이 true로 설정이 된다.
*/
#include<vector>
class hash_set
{
private:
int sz;
vector<int> data;
public :
hash_set (int n ) : sz(n) , data(sz , -1) { } // 모두변수 -1로 초기화 !
int hash(int key) { return key % sz; }
void insert(int value) { data[hash(value)] = value; }
bool find(int value) { return (data[hash(value)]) == value; }
void erase(int value) { data[hash(value)] = -1; }
void print() {
for (auto n : data)cout << n << " , ";
cout << endl;
}
};
int main() {
hash_set num_set(7);
num_set.insert(10); // 3번째 자리에 10이라는 값이 들어가게 됨
num_set.insert(15); // 첫번 자리에 15가 들어가게 됨
num_set.insert(20); // 6번 자리에 20이 들어가게 됨
num_set.insert(100); // 2번째 자리에 100값이 들어감
num_set.print();
int value = 10;
if (num_set.find(value)) cout << value << " found " << endl;
else cout << value << "not found " << endl;
num_set.insert(2); // 이러면 2번 칸에 100 대신 2가 들어가게 됨
value = 100;
if (num_set.find(value)) cout << value << " found " << endl;
else cout << value << "not found " << endl;
//100이 없다고 나오게 된다.
//실제로는 insert를 분명히 100을 하고 2를 하게 되면서 100과 2라는 값이 hash값이 같아서 충돌이 일어나, 찾지 못하는 결과가 일어남.
//이러한 충돌을 해결하는 방법은 다음강의에
}
/*
ㅇ해시함수
-주어진 데이터로부터 고유한 숫자 값을 생성해서 반환하는 함수
-보통 함수의 출력은 고정된 범위의 정수로 매핑 된다.
ex) h(k) = k%n 이라는 해시함수가 있으면
[0, n-1] 정수값으로 변경이 된다 .
ㅇ키
-해시함수의 입력으로, 입력데이터 자체이거나 또는 데이터를 구분하는 값이다.
ㅇ해시 값
-해시 함수의 출력으로, 보통 해시 테이블의 인덱스로 사용된다.
-해시 코드 또는 단순히 해시 라고도 부른다.
ㅇ해시테이블
-입력데이터가 저장되는 배열/벡터 같은 자료구조이다, 해시 맵이라고도 한다(입력 데이터가 키로, 벨류로 구성 된것), 해시 함수에 의해 계산된 인덱스에 데이터가 저장된다
입력 데이터 자체를 저장하면 hash set이라는 용어를 사용하기도 한다.(key가 저장이 됨)
ㅇ버킷(bucket)
-slot, cell이라고도 한다
-해시 테이블에서 하나의 데이터가 저장된 공간이다
ㅇ충돌(collision)
-해시 함수가 서로 다른키에 대해 같은 해시값을 반환함으로써, 다수의 키가 같은 해시 값을 갖게 되는 현상이다.
-chaining, open addressing등의 방법으로 해결이 가능하다.
ㅇ실수해시 함수
-주어진 실수를 조작하거나 또는 실수의 각 숫자를 조합하여 해시 값을 생성한다
-예로들어서 실수 x가 주어지면 이 값에 부터 1 사이의 임의의 실수 A를 곱하고 그 결과에서 소수점 아래부분을 s로 설정.
그러면 s라는 값은 0<=s<1 소수값이 된다.
그 후 이 s에 정수 m을 곱한 후, 소수 점 아래를 버림으로써 [0, m-1]사이의 정수를 얻을 수 있다.
ㅇ문자열 해시 함수
-문자열의 각 문자를 ASCII코드로 변환하고, 이 값을 조합하여 해시 값을 생성한다
예를들어 cat이라고 주어지면 c = 99, a = 97, t = 116 이므로
99*128^2 + 97 * 128^1 + 116 * 128^0 = 1634548를 얻을 수 있따.
이 값에다가 나머지 연산을 수행해서 해시테이블 인덱스로 변환할 수 있다.
ㅇ좋은 해시 함수의 조건
1. 빠르고 효율적인 연산
2. 해시 값이 균일하게 분포
-충돌 최소화
-해시 테이블 사용 효율이 높을 것
-사용할 키의 모든 정보를 이용
*/