데이터 구조 와 알고리즘 학습 의 길: 간단 한 해시 표 실현 (체인 주소 법 충돌 해결)

1. 해시 시 계 는 무엇 입 니까?
  산 목록 (Hash table, 해시 표 라 고도 함) 은 키 코드 값 (Key - Value) 에 따라 직접 접근 하 는 데이터 구조 입 니 다.
 
    즉, 키 코드 값 을 표 의 한 위치 에 비 추어 기록 에 접근 함으로써 검색 속 도 를 빠르게 하 는 것 이다.이 매 핑 함 수 는 해시 함수 라 고 하 는데 기록 을 저장 하 는 배열 을 산 목록 이 라 고 합 니 다.
    주어진 표 M, 함수 f (key) 가 존재 합 니 다. 주어진 키워드 값 key 를 함수 에 대 입 한 후 이 키 워드 를 포함 하 는 표 에 기 록 된 주 소 를 얻 을 수 있다 면 표 M 을 해시 (Hash) 표 라 고 부 르 고 함수 f (key) 를 해시 (Hash) 함수 라 고 부 르 기 때문에 우 리 는 알 수 있 습 니 다.
    해시 표 의 장점 은 찾기 효율 이 높 지만 공간 이 소모 된다 는 것 이다.
    사상 은 개인 적 으로 공간 이 시간 을 바 꾸 는 것 이 라 고 생각 합 니 다.
2. 해시 함수 의 구조 방법:
    1. 직접 주소 지정 법: 키워드 나 키 워드 를 가 져 오 는 선형 함수 값 은 해시 주소 입 니 다.
    2. 디지털 분석 법: 키 워드 는 r 를 기반 으로 하 는 수 (예 를 들 어 10 을 기반 으로 하 는 10 진수) 라 고 가정 하고 해시 표 에 나타 날 수 있 는 키 워드 는 모두 사전에 알 고 있 으 며 키워드 의 몇 개의 숫자 로 해시 주 소 를 구성 할 수 있다.
    3. 제곱 취 중 법: 키 워드 를 제곱 한 후의 중간 몇 자 리 는 해시 주소 입 니 다.
    4. 피 보 나치 (Fibonacci) 산열 법
    5. 접 는 법: 키 워드 를 자릿수 가 같은 몇 부분 (마지막 부분의 자릿수 는 다 를 수 있 음) 으로 나 눈 다음 에 이 몇 부분의 중첩 과 (자리 옮 김) 을 해시 주소 로 하 는데 이 방법 을 접 는 법 이 라 고 한다.
    6. 나머지 를 제외 하 는 방법: 키 워드 를 취 하 는 것 은 해시 표 의 길이 m 보다 크 지 않 은 수의 p 에 의 해 제 거 된 후 얻 은 나머지 는 해시 주소 입 니 다. 즉, H (key) = key MOD p, (p < = m) 입 니 다. 이것 은 가장 간단 하고 가장 자주 사용 하 는 구조 해시 함수 의 방법 입 니 다. 키 워드 를 직접 모델 링 (MOD) 할 수 있 을 뿐만 아니 라 접 기, 제곱 에서 중간 연산 을 한 후에 도 모델 링 을 할 수 있 습 니 다.
    7. 난수 법: 랜 덤 함 수 를 선택 하고 키워드 의 랜 덤 함수 값 을 해시 주소 로 합 니 다. 즉, H (key) = random (key) 입 니 다. 그 중에서 random 은 랜 덤 함수 입 니 다. 보통 키워드 길이 가 다 를 때 이 방법 으로 해시 함 수 를 구성 합 니 다.
3. 해시 표 의 결함:
해시 표 는 항상 충돌 이 발생 할 수 밖 에 없다 (특히 데이터 양 이 많 을 때). 이 럴 때 충돌 을 해결 하 는 방법 이 필요 하 다. 다음은 자주 사용 하 는 충돌 해결 방법 이다.
1. 개방 주소 법
2. 재 해시 법
3. 체인 주소 법
4. 공공 유출 구역 구축
4. 코드 구현:
필자 가 이번에 보 낸 코드 는 주로 한 무더기 의 숫자 를 해시 표 로 만 든 다음 에 숫자 를 찾 는 것 이다. 여 기 는 체인 주소 법 으로 충돌 을 해결 하 는 동시에 체인 주소 법 도 설명 하 자.
만약 에 해시 함수 처 리 를 통 해 요소 A, B, C, D 가 해시 표 에서 의 위 치 는 같다 고 가정 하면 A, B, C, D 네 가지 요소 가 충돌 했다. 이때 우 리 는 먼저 온 A 를 해시 표 에 넣 은 다음 에 A (하나의 구조 체 요소, 안에 지침 이 존재 한다) 를B 를 가리 키 고, B 는 C 를 가리 키 고, C 는 D 를 가리킨다. 뒤에 충돌 원소 가 있어 도 이렇게 연결된다. 다시 말 하면 우 리 는 하나의 체인 테이블 로 이 비슷 한 원소 들 을 저장 했다.

#include 
#include 

#define TRUE 1
#define FALSE 0

#define HASH_SIZE 12

typedef struct Hash_Table{
	int data;
	Hash_Table* next;
}*Hash_TablePtr;

int Hash(int key);
int Search(Hash_TablePtr hash, int key);

int main(){
	Hash_Table hash[HASH_SIZE];

	int i, search;
	int temp[HASH_SIZE] = { 9, 31, 26, 19, 1, 13, 2, 11, 27, 16, 5, 21 };

	for (i = 0; i < HASH_SIZE; i++){
		hash[i].data = -1;
		hash[i].next = NULL;
	}

	for (i = 0; i < HASH_SIZE; i++){
		int x, y;

		x = temp[i];
		y = Hash(x);

		Hash_TablePtr pre;

		if (hash[y].data == -1)
			hash[y].data = x;
		else{
			Hash_TablePtr chain_adress = (Hash_TablePtr)malloc(sizeof(Hash_Table));
			chain_adress->data = x;
			chain_adress->next = NULL;

			pre = &hash[y];

			while (pre->next != NULL)
				pre = pre->next;

			pre->next = chain_adress;
		}
	}

	printf("       ：");
	scanf("%d", &search);
	if (Search(hash, search))
		printf("   
");
	else
		printf("   
");
}

int Hash(int key){
	return key % 11;
}

int Search(Hash_TablePtr hash, int key){
	int adress = Hash(key);

	if (hash[adress].data == -1)
		return FALSE;
	else if (hash[adress].data == key)
		return TRUE;
	else{
		Hash_TablePtr temp = &hash[adress];
		while (temp != NULL){
			temp = temp->next;

			if (temp == NULL)
				return FALSE;
			else if (temp->data == key)
				return TRUE;
		}

		return FALSE;
	}
}