해시 표 의 종합 응용 (충돌 생 성, 처리, 성공 과 실패 횟수 찾기)
Question1:
키워드 시퀀스 (7, 8, 30, 11, 18, 9, 14) 를 산열 목록 에 저장 합 니 다.산 목록 의 저장 공간 은 0 에서 시작 하 는 1 차원 배열 입 니 다. 산 열 함 수 는 다음 과 같 습 니 다. H (key) = (keyx 3) MOD 7, 처리 충돌 은 선형 탐지 재 산열 법 을 사용 하여 장 착 (적재) 인 자 를 0.7 로 요구한다.
(1) 구 조 된 산 목록 을 그 려 주세요.
(2) 각각 계산 등 확률 상황 에서 성공 과 성공 하지 못 한 평균 검색 길 이 를 찾 습 니 다.
Ans：
(1). 우선 하나의 개념 적재 인 자 를 명 확 히 한다. 적재 인 자 는 모든 관건 적 인 부분 이 해시 표를 채 운 후 포화 되 는 정 도 를 말한다. 이것 은 키워드 총수 / 해시 표 의 길이 와 같다.제목 에 따라 우 리 는 해시 표 의 길 이 를 L = 7 / 0.7 = 10 으로 확정 할 수 있다.따라서 이 문제 가 구축 해 야 할 해시 표 는 0 ~ 9 로 표 시 된 1 차원 배열 이다.해시 함수 에 따라 다음 과 같은 해시 함수 값 표를 얻 을 수 있 습 니 다.
H (Key) = (keyx 3) MOD 7, 예 를 들 어 key = 7 시, H (7) = (7x3)% 7 = 21% 7 = 0, 기타 키 워드 는 동일 합 니 다.
Key
7
8
30
11
18
9
14
H(Key)
0
3
6
5
5
6
0
(표 1)
선형 탐지 재 산열 법 으로 충돌 을 처리 하고 구 조 된 산열 표 는 다음 과 같다.
주소.
0
1
2
3
4
5
6
7
8
9
키워드
7
14
8
11
30
18
9
(표 2)
다음은 산 목록 의 구조 방식 에 대해 설명 하 겠 습 니 다. 표 1 의 키워드 7 과 14, 30 과 9, 11 과 18, 이 세 그룹의 관건 적 인 H (Key) 에 주의 하 십시오.값 이 같 습 니 다. 이 는 산 목록 을 구축 할 때 충돌 이 발생 합 니 다. 주소 가 같 기 때문에 일정한 충돌 처리 방법 으로 이 문 제 를 해결 해 야 합 니 다. 문제 에 따라 선형 탐지 재 산열 법 으로 충돌 을 처리 합 니 다. 다음은 산 목록 을 어떻게 구축 하 는 지 상세 하 게 소개 합 니 다.
첫 번 째 key 7 의 주 소 는 0 입 니 다. 따라서 산 목록 의 배열 아래 표 가 0 인 위치 에 놓 습 니 다. 이 위치 에는 키워드 가 없 기 때문에 충돌 없 이 직접 입력 할 수 있 습 니 다.
두 번 째 key 8 의 주 소 는 3 입 니 다. 따라서 산 목록 의 배열 아래 표 는 3 의 위치 입 니 다. 이 위치 에는 키워드 가 없 기 때문에 충돌 없 이 직접 입력 할 수 있 습 니 다.
세 번 째 key 30 의 주 소 는 6 입 니 다. 따라서 산 목록 의 배열 아래 표 는 6 의 위치 입 니 다. 이 위치 에는 키워드 가 없 기 때문에 충돌 없 이 직접 입력 할 수 있 습 니 다.
네 번 째 key 11 의 주 소 는 5 입 니 다. 따라서 산 목록 의 배열 아래 표 는 5 의 위치 입 니 다. 이 위치 에는 키워드 가 없 기 때문에 충돌 없 이 직접 입력 할 수 있 습 니 다.
다섯 번 째 key 18 의 주 소 는 5 입 니 다. 따라서 산 목록 의 배열 아래 표 는 5 의 위치 입 니 다. 그러나 이 위치 에 키워드 11 이 있 고 충돌 이 발생 했 습 니 다. 이때 우 리 는 선형 탐측 재 산열 법 에 따라 이 충돌 을 처리 하고 다음 위 치 를 탐지 합 니 다. 6 이 위치 에 키워드 30 이 존재 하면 걸음 길이 가 1 을 계속 증가 합 니 다. 따라서 현재 의 새로운 주 소 는 7, 위치 7 상 이 어야 합 니 다.키워드 가 없 으 면 넣 으 면 됩 니 다. 이 충돌 은 이미 해결 되 었 습 니 다.
여섯 번 째 key 9 의 주 소 는 6 입 니 다. 따라서 산 목록 의 배열 아래 표 는 6 의 위치 입 니 다. 그러나 이 위치 에 키워드 30 이 있 습 니 다. 충돌 이 발생 했 습 니 다. 다음 위 치 를 탐지 합 니 다. 7. 이 위치 에 키워드 18 이 존재 하면 걸음 길이 가 1 을 계속 증가 합 니 다. 따라서 현재 의 새로운 주 소 는 8 이 어야 합 니 다. 위치 8 에 키워드 가 없 으 면 넣 으 면 됩 니 다.
일곱 번 째 key 14 의 주 소 는 0 입 니 다. 따라서 산 목록 의 배열 아래 표 는 0 의 위치 입 니 다. 그러나 이 위치 에 키워드 7 이 있 습 니 다. 충돌 이 발생 했 습 니 다. 다음 위치 1, 위치 1 에 키워드 가 없 으 면 넣 으 면 됩 니 다.
이 단계 에 이 르 러 모든 키 워드 는 이미 입력 되 었 고 산열 표 는 이미 구조 가 완성 되 었 습 니 다. 표 2 와 같 습 니 다.
(2) 등 확률 로 검색 성공 평균 길이:
이 질문 은 첫 번 째 질문 의 구조 과정 에 따라 구 해 낼 수 있다.
키 7 은 한 번 에 표 에 채 워 졌 기 때문에 검색 횟수 는 1, 동 리 8, 30, 11 검색 횟수 는 모두 1 이 고 키 18 은 3 번 을 넣 었 으 며 탐측 위 치 는 각각 5, 6, 7 이 므 로 검색 횟수 는 3 이 며 키 9 도 3 번 이 며 키 14 는 두 번 의 탐 사 를 했 기 때문에 검색 횟수 는 2 이다. 횟수 표 3 참조.
Key
7
8
30
11
18
9
14
Count
1
1
1
1
3
3
2
(표 3)
그래서 ASLsuccess = (1 + 1 + 1 + 3 + 3 + 2) / 7 = 12 / 7.
등 확률 로 찾 을 수 없 는 평균 찾기 길이:
다음 토론 이 성공 하지 못 한 경 우 는 표 2 를 보고 성공 하지 못 한 횟수 를 계산 하여 키 워드 를 첫 번 째 주소 에서 키워드 가 비어 있 는 거 리 를 찾 으 면 됩 니 다. 그러나 해시 함수 주소 에 따라 MOD7 이 므 로 초기 에는 0 ~ 6 의 위치 에 만 있 을 수 있 습 니 다. 등 확률 적 인 상황 에서 0 ~ 6 위 치 를 찾 는 데 실패 한 검색 횟수 는 다음 과 같 습 니 다.
주소 0 을 보고 첫 번 째 키워드 가 비어 있 는 주소 2 까지 의 거 리 는 3 이 므 로 찾 지 못 한 횟수 는 3 입 니 다.
주소 1, 첫 번 째 관건 이 빈 주소 2 까지 의 거 리 는 2 이 므 로 찾 지 못 한 횟수 는 2 입 니 다.
주소 2, 첫 번 째 관건 이 빈 주소 2 까지 의 거 리 는 1 이 므 로 찾 지 못 한 횟수 는 1 입 니 다.
주소 3, 첫 번 째 관건 이 빈 주소 4 까지 의 거 리 는 2 이 므 로 찾 지 못 한 횟수 는 2 입 니 다.
주소 4, 첫 번 째 관건 이 빈 주소 4 까지 의 거 리 는 1 이 므 로 찾 지 못 한 횟수 는 1 입 니 다.
주소 5, 첫 번 째 관건 은 빈 주소 2 (주소 9 가 아 닙 니 다. 초기 에는 0 ~ 6 사이 일 수 있 으 므 로 순환 합 니 다) 의 거 리 는 5 이 므 로 찾 지 못 한 횟수 는 5 입 니 다.
주소 6, 첫 번 째 관건 은 빈 주소 2 (주소 9 가 아 닙 니 다. 초기 에는 0 ~ 6 사이 일 수 있 으 므 로 순환 합 니 다) 의 거 리 는 4 이 므 로 찾 을 수 없 는 횟수 는 4 입 니 다.
따라서 성공 하지 못 한 횟수 표를 찾 는 것 은 다음 과 같다.
Key
7
8
30
11
18
9
14
Count
3
2
1
2
1
5
4
(표 4)
그래서 ASLunsuccess = (3 + 2 + 1 + 2 + 1 + 5 + 4) / 7 = 18 / 7.
다음은 자신 이 쓴 해시 표 의 코드 (선형 탐지 배치 키워드 와 찾기) 입 니 다. 해시 표 의 생 성, 충돌 횟수, 성공 횟수 와 성공 하지 못 한 횟수 를 포함 합 니 다.
：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 50
typedef int Typedata;
typedef struct HashNode
{
Typedata *HT;//
Typedata *num;//
Typedata *broke;//
Typedata *NUfod;//
Typedata key;
}HashNode;
Typedata i,k;//
void InitHash(HashNode &T)//
{
T.HT=(Typedata *)malloc(MAXSIZE*sizeof(Typedata));
T.num=(Typedata *)malloc(MAXSIZE*sizeof(Typedata));
T.broke=(Typedata *)malloc(MAXSIZE*sizeof(Typedata));
T.NUfod=(Typedata *)malloc(MAXSIZE*sizeof(Typedata));
for(i=0;i<MAXSIZE;i++)
{
T.HT[i]=0;T.num[i]=0;T.broke[i]=0;
}
}
void CreateHash(HashNode T,Typedata k,Typedata m)
{
Typedata d,t;
for(i=0;i<k;i++)//
{
d=T.num[i]%m;t=1;
while(T.HT[d])
{
d=(d+1)%m;
t++;
}
T.HT[d]=T.num[i];
T.broke[d]=t;
}
Typedata j,count;
for(i=0;i<m;i++)//
{
count=1;
for(j=i;j<m;j++)
{
if(T.HT[j]!=0)
count++;
else
break;
if(T.HT[j]!=0&&j==m-1)
j=-1;
}
T.NUfod[i]=count;
}
}
void DisplayHash(HashNode T,Typedata m)
{
printf("
：");
for(i=0;i<m;i++)
printf("%-4d",i);
printf("
：");
for(i=0;i<m;i++)
printf("%-4d",T.HT[i]);
printf("
：");
for(i=0;i<m;i++)
printf("%-4d",T.broke[i]);
printf("
：");
for(i=0;i<m;i++)
printf("%-4d",T.NUfod[i]);
printf("
");
}
double EverageHash(HashNode T,Typedata m)//
{
Typedata sum=0;
double ave;
for(i=0;i<m;i++)
sum+=T.broke[i];
ave=(double)sum/k;
return ave;
}
double NUEverageHash(HashNode T,Typedata m)//
{
Typedata sum2=0;
double ave2;
for(i=0;i<m;i++)
sum2+=T.NUfod[i];
ave2=(double)sum2/m;
return ave2;
}
int main()
{
HashNode T;
char c='Y';
while(c=='Y')
{
InitHash(T);//
Typedata m;
printf(" ：");
scanf("%d",&k);
printf("
");
for(i=0;i<k;i++)
scanf("%d",&T.num[i]);
printf(" m=");
scanf("%d",&m);//
CreateHash(T,k,m);//
DisplayHash(T,m);//
printf(" ASL=%.2lf
",EverageHash(T,m));
printf(" NUASL=%.2lf
",NUEverageHash(T,m));
printf(" (Y/N) ");
getchar();//
c=getchar();
printf("
");
}
return 0;
}
//
// 23 35 12 56 123 39 342 90
// m=11
// ASL=3.50
// NUASL=4.27
// 19 14 23 1 68 20 84 27 55 11 10 79
// m=13
// ASL=2.50
// NUASL=7.00테스트 용례 의 대응 출력:
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
