- 정의
-> 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조
-> 평균적으로 상수시간에 insert, search, delete가 가능하다
-> 매우 빠른 답을 받아야할때 유용
-> 최소 값, 최대 값 찾는 것은 적합하지 않다. 값을 빨리 찾아올때만 유용하다 - 순서
자료를 가지고 key값 변경 -> index 계산 -> 각 index 위치에 value저장 (Hash Table) - 조건 ( 올바른 Hash 함수 조건 )
-> 입력원소가 hash table에 골고루 분포될수있게 key를 만들자
-> 계산을 간단히 하자 - 정수를 해싱하는 경우
Division method, multiplication method - 문자열을 해싱하는 경우
# 곱셈법 (Multiplication Method)
- hf(key) = (key * GRN mod 1) * SIZE
- GRN (황금비, Golden Ratio Number) = a:b = b:c (root 5 -1) / 2
- SIZE는 소수일 필요가 없으므로 보통 2의 제곱수로...
# 나눗셈법 (Division Method)
- hf(key) = key mod SIZE
- SIZE : table사이즈는 prime number를 사용
- GRN * 2^32 (int형 자료가 표현하는 가지수) = 2654435769..
# 나눗셈법 - 황금비
const int SIZE = 1 << 25;
const int MOD = SIZE - 1;
int hashTable[SIZE]
# 충돌해결
- Chaining
같은 주소로 해쉬되는 원소가 있더라도 하나으l linked list로 관리할 것. 값이 여러 개라면 같이 쓸 수 밖에 없다.
- Open addressing
충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결, 추가적인 공간이 필요하지 않다.
삭제한 이후 탐색에 대한 대비로 추가적인 작업 필요하다.
42 52 22 13
42 52 22 13
13 22 52 42
바이러스가 거꾸로도 나타나고 올바르게도 나타나는데,
입력자료를 분석하자
감염된 프로그램 개수 N ( 2 <= N <= 100 )
바이러스 코드 추정을 위한 최소 길이 K ( 4 < K < 1,000 )
각 프로그램에 대한 정보
- i번째 프로그램 길이를 나타내는 정수 Mi
- Mi 개의 프로그램 코드를 나타내는 양의 정수 (정수의 범위는 1이상)
바이러스 길이가 4라면,
예제
바이러스 길이가 4다.
각 프로그램 100개 * 길이 1000개( size = 1 << 12;)
한 프로그램에서 4개씩 묶음으로 확인
N^3K
20 31 23 10
성분이 같은걸 해쉬로 만들자
1) 전부 합계로 한다. 각 숫자가 모두 같은지 판단하는 방법. 네 숫자의 합
2) 각 숫자의 제곱. 만약 가중치/순서를 고려해야되면 (0제곱, 제곱, 세제곱, 네제곱)
전부 제곱을 하더라도 나쁘지않다. 제곱을 했을 때 서로 다른 요소들이 같은 값이 나오기란 매우 어렵다.
3) 슬라이딩 하면서 합을 하지 말고, 각 값에서 누적값을 더해서 빼자..
#include <cstdio>
const int SIZE = 1 << 12; // 10000000..
const int MOD = SIZE - 1; // 1111111, SIZE와 나눈 나머지니까 MOD로 & 연산 하기 위한 것
int N, K, M, mykey;
int A[1010], B[1010], sum[1010], bn;
// sum: 누적값
struct node {
int pos, same_cnt; // pos: 위치(A에 넣을때 어느위치에 넣을것인지), same_cnt: 이 키가 몇번나왔느냐
node* next;
node* alloc(int _pos, node* _next){ // 초기값 지정
pos=_pos, next = _next, same_cnt = 1;
return this;
}
} *Hash[SIZE], buf[1000]; // buffer는 1000개만 들어가면 되므로
int main(){
scanf() N, K
scanf() M
for (int i=1; i<=M; ){
scanf
sum
if ( i >= k)
int key = (sum[i] - sum[i-K] + MOD) & MOD;
Hash[key] = buf [bn++].alloc()
}
}