POJ -- 3394 [Containers] 해시 판정 중

데이터 구조 자, '데이터 간 관계 + 데이터 저장 방식' 도.
어떤 데이터 구 조 를 선택 하 느 냐 는 어떤 문 제 를 해결 해 야 하 느 냐 에 달 려 있다.
모든 데이터 구 조 는 장점 이 있다. 이 장점 은 '본 데이터 구 조 는 XX 작업 을 할 때 빠르다' 는 것 이다. 어떤 데이터 구 조 를 선택 하 느 냐 에 따라 해결 해 야 할 문제 가 데이터 구조 에서 어떤 조작 을 해 야 하 는 지 에 따라 결정 된다.
해시 표 는 바로 이 이 치 를 나타 내 는 좋 은 예 이다.
해시 표 는 이러한 다른 데이터 구조 가 잘 하지 못 하 는 조작 을 제공 합 니 다.
"이상 적 인 상황 에서 상수 시간 으로 지정 한 값 의 데 이 터 를 찾 을 수 있 습 니 다."
 
일반 데이터 구조, 예 를 들 어 선형 표, 나무, 그림 등 은 결점 안의 데이터 와 데이터 가 저장 하 는 위치 간 의 관 계 는 무 작위 이기 때문에 '이미 알 고 있 는 데이터 의 위 치 를 찾 으 려 면' 비교 '방식 으로 만 할 수 있다. 예 를 들 어 정렬 되 지 않 은 선형 표 에 대해 처음부터 끝까지' = '여 부 를 비교 해 야 한다.2 점 찾기 에 대해 서 는 ">"< "또는"= = "을 비교 해 야 합 니 다.이렇게 시간 복잡 도 는 n 또는 logn 입 니 다.
한편, 해시 표 는 '저장 위치 와 데이터 값 사이 에 맵 관 계 를 구축한다' 는 수단 을 통 해 이 작업 의 시간 복잡 도 를 O (1) 로 낮 춘 다.
이 설명 은 '저장 위치 와 데이터 값 사이 에 매 핑 관 계 를 구축한다' 는 매 핑 관 계 는 바로 해시 함수 입 니 다.
데 이 터 를 해시 표 에 저장 할 때 해시 함 수 를 이용 하여 이 데이터 에 저장 위 치 를 설정 합 니 다.지정 한 값 데 이 터 를 찾 을 때 도 해시 함수 에 따라 대상 색인 을 얻 을 수 있 습 니 다.
 
실제 작업 을 할 때 수치 역 과 색인 역 의 크기 가 다 르 기 때문에 간단하게 선형 매 핑 을 할 수 없고 비교적 복잡 한 해시 함 수 를 만들어 야 한다. 이것 은 해시 가 직면 한 주요 문제 이다.좋 은 해시 함 수 는 무 작위 데이터 가 얻 을 만 한 해시 결 과 를 가능 한 한 분산 시 키 고 충돌 을 줄 여야 합 니 다.
 
= = = = = = = = = = = = = = = = = = = = = 분할 선 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
이런 문제 가 있 습 니 다. 한 번 이상 나타 난 데이터 가 있 습 니까?어 리 석 은 방법 은 처음부터 끝까지 하나씩 비교 할 수 있 고 복잡성 은 O (N * N) 이다.똑똑 한 방법 은 데이터 가 분산 되 지 않 으 면 기 호 를 하 는 방법 으로 한 비트 배열 (bool 로 실현 가능) 로 각 비트 가 대표 하 는 데이터 가 나 타 났 는 지 기록 할 수 있 습 니 다. 이미 나 타 났 던 데 이 터 를 읽 으 면 한 번 이상 나타 나 고 bool 대신 int 로 모든 데이터 가 나 타 났 는 횟수 를 기록 할 수 있 습 니 다.한 번 옮 겨 다 니 면 가장 많은 데 이 터 를 얻 을 수 있 고 복잡 도 는 O (N) 이다.그러나 데이터 가 분산 되면 이런 선형 매 핑 은 사용 되 지 않 습 니 다. 메모리 가 심각하게 낭비 되 기 때문에 데이터 가 너무 과장 되면 큰 BUFFER 의 신청 을 초래 할 수 있 습 니 다. 그러나 이런 매 핑 기록 사상 은 바람 직 합 니 다. 이 때 는 큰 데이터 필드 에서 작은 주소 필드 에 매 핑 하 는 도구 로 보조 해 야 합 니 다. 자 연 스 럽 게 '해시' 입 니 다.
 
POJ 3349 는 해시 라 는 특징 을 이용 한 전형 적 인 응용 이다.제목 자 체 는 액세스 와 상 관 없 이 데이터 가 한 번 이상 나 왔 는 지 찾 아야 한다.상기 '태그' + '맵' 방법 을 취 할 수 있 습 니 다.
 
CODE:

/*hash  */
/*
1.     ,  (  %   ) key.
2.      ,  (  %   ) key.
3.        ,  v[i]<<(i*3)    ,           key.(by hust07p43)
4.                  ,     100w    。
          110w       ，         10w   hash        6k  ，      。(by  killertom)
5.               key. (by archerstarlee)
6. (a[0] + a[2] + a[4])&(a[1] + a[3] + a[5]),        .    &     '|'   '^'.    !    '^'     719ms. (       hash  )

                hash  ,     hash       .
     getchar gets           . G++ GCC   .
             Hash  .
*/
/*AC  ：2344ms*/
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <cstdlib>
#define MAXN 100000
#define MOD 99991
using namespace std;
struct Node
{
	int val[7];
};
struct Node Hash[MAXN][20];//hash 
int len[MAXN];//  hash    
int N;
bool ok;
int hash(Node u)//hash  
{
	int i,sum=0;
	for(i=1;i<=6;i++)
		sum+=u.val[i];
	return sum%MOD;
}
void Rotate(Node &u)//  
{
	int i,t=u.val[1];
	for(i=1;i<=5;i++)
		u.val[i]=u.val[i+1];
	u.val[6]=t;
}
void Reverse(Node &u)//  
{
	Node v;
	int i,j;
	for(i=1,j=6;i<=6;i++,j--)
		v.val[i]=u.val[j];
	u=v;
}
bool Equal(Node u,Node v)//      
{
	int i;
	for(i=1;i<=6;i++)
	{
		if(u.val[i]!=v.val[i])
			return false;
	}
	return true;
}
void Judge(Node u,Node v)
{
	int i;
	for(i=1;i<=6;i++)
	{
		Rotate(u);
		if(Equal(u,v)) {ok=false;return;}
	}
	Reverse(u);
	for(i=1;i<=6;i++)
	{
		Rotate(u);
		if(Equal(u,v)) {ok=false;return;}
	}
}
void Init()
{
	int i,j;
	Node u;
	ok=true;
	memset(len,0,sizeof(len));
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=6;j++)
			scanf("%d",&u.val[j]);
		if(!ok) continue;
		int pos=hash(u);
		for(j=0;j<len[pos];j++)
		{
			Judge(u,Hash[pos][j]);
			if(!ok) break;
		}
		Hash[pos][len[pos]++]=u;
	}
}
void Solve()
{
	if(ok) printf("No two snowflakes are alike.
");
	else printf("Twin snowflakes found.
");
}
int main()
{
	while(scanf("%d",&N)!=EOF)
	{
		Init();
		Solve();
	}
	return 0;
}