C-별도의 연결 해시 테이블 만들기-문제
이해할 수있는 변수와 물건을 넣는 데 시간을 투자했습니다. 깨끗하고 깔끔하게 보이도록 노력했습니다. 그래서 쉽게 디버깅 할 수 있습니다. 하지만 내 문제를 찾을 수없는 것 같습니다 ... 터미널에서 아무것도 출력하지 않습니다. 내 실수를 식별하도록 도와주세요!
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct list_node *node_ptr;
struct list_node
{
node_ptr next;
char *key;
char *value;
};
typedef node_ptr LIST;
typedef node_ptr position;
struct hash_table
{
LIST *list_ptr_arr;
unsigned int table_size;
};
typedef struct hash_table *HASHTABLE;
unsigned long long int
hash(const char *key, unsigned int hash_size)
{
unsigned long long int hash;
for(int i = 0; key[i]; i++)
{
hash = (hash<<32)+key[i];
}
return (hash%hash_size);
}
unsigned int
next_prime(int number)
{
int j;
for(int i = number; ; i++)
{
for(j = 2; j<i; j++)
{
if(i%j == 0){break;}
}
if(i==j){return j;}
}
}
HASHTABLE
initialize(unsigned int table_size)
{
HASHTABLE H;
H = (HASHTABLE) malloc(sizeof(struct hash_table));
if(H==NULL){printf("Out of Space!"); return 0;}
H->table_size = next_prime(table_size);
H->list_ptr_arr = (position*) malloc(sizeof(LIST)*table_size);
if(H->list_ptr_arr==NULL){printf("Out of Space!"); return 0;}
H->list_ptr_arr = (LIST*) malloc(sizeof(struct list_node)*table_size);
for(unsigned int i = 0; i<table_size; i++)
{
if(H->list_ptr_arr[i]==NULL){printf("Out of Space!"); return 0;}
H->list_ptr_arr[i]=NULL;
}
return H;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr entry = H->list_ptr_arr[slot];
node_ptr prev;
while(entry!=NULL)
{
if(strcmp(entry->key, key)==0)
{
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
return;
}
prev = entry;
entry = prev->next;
}
entry = (position) malloc(sizeof(struct list_node));
entry->value = malloc(strlen(value)+1);
entry->key = malloc(strlen(key)+1);
strncpy(entry->key,key,strlen(key));
strncpy(entry->value,value,strlen(value));
entry->next = NULL;
prev->next = entry;
}
void
dump(HASHTABLE H)
{
for(unsigned int i = 0; i<H->table_size; i++)
{
position entry = H->list_ptr_arr[i];
if(H->list_ptr_arr[i]==NULL){continue;}
printf("slot[%d]: ", i);
for(;;)
{
printf("%s|%s -> ", entry->key, entry->value);
if(entry->next == NULL)
{
printf("NULL");
break;
}
entry = entry->next;
}
printf("\n");
}
}
int main()
{
HASHTABLE H = initialize(10);
insert("name1", "David", H);
insert("name2", "Lara", H);
insert("name3", "Slavka", H);
insert("name4", "Ivo", H);
insert("name5", "Radka", H);
insert("name6", "Kvetka", H);
dump(H);
return 0;
}
그것을 수정하고 약간의 것을 변경하려고 시도했지만 아무것도 도움이되지 않았습니다 ...
미리 감사드립니다!
답변
코드를 깨는 몇 가지 아름다움 문제와 적어도 두 가지 오류가 있습니다. 나는 사소한 것들에 대해 다루지 않을 것입니다. 그것은 대부분 문체이지만 당신 initialize()과 insert()기능은 작동하지 않습니다.
에서 initialize()당신을 위해 메모리를 할당 H->list_ptr_array두 번. 그것은 정당한 이유없이 첫 번째 할당에서 메모리를 누출하지만 물론 코드가 충돌하지 않고 누출됩니다. 두 번째 할당에서는 잘못된 크기를 할당하고를 사용 sizeof(struct list_node) * tale_size하지만 구조체가 아닌 포인터 배열을 원합니다 (구조물이 포인터를 보유하기 때문에 더 커질 것입니다). 다시 말하지만, 메모리 만 낭비하고 충돌하지 않습니다. 그래도 올바른 메모리를 사용하는 것이 더 나을 것입니다.
H->list_ptr_arr = malloc(table_size * sizeof *H->list_ptr_arr);
의 결과를 캐스트 할 필요가 없습니다 malloc(). 이것은 a void *이고 포인터 유형에 캐스트 할 필요가 없지만 스타일 문제입니다. 그 라인의 중요한 부분은 우리가 할당 한 변수에서 기본 데이터의 크기를 얻을 수 있다는 것입니다. 따라서 어떤 시점에서 유형을 변경하더라도 항상 올바른 크기를 얻을 수 있습니다. 나는 또한 sizeof(type)때때로 사용하는 경향이 있지만 sizeof *ptr더 나은 패턴이며 익숙해 질 가치가 있습니다.
어쨌든 잘못된 양의 메모리를 할당하더라도 충분히 할당하므로 프로그램이 충돌하지 않습니다. 그러나 그런 다음 테이블에서 할당 된 bin을 통해 실행할 때 NULL. 그것들은 전혀 초기화되지 않았기 때문에 만약 초기화 되었다면 NULL(그럴 수도 있습니다), 그것은 순전히 운에 의한 것입니다. 또는 오류의 신호라고 생각하면 불행합니다. 그러나 NULL여기서 할당 오류의 신호 를 고려한다면 , 그렇지 NULL않다는 결론을 내린 직후에 각 빈을 초기화하는 이유는 무엇입니까?
그대로, NULL배열에서 포인터 를 가져 오면 초기화가 중단 되고 할당 오류를 확인하지 않기 때문에 main()(테스트에 적합합니다) 프로그램이 충돌하는 이유 일 수 있습니다. 그것은 주요 문제가 아니며 우연히 NULL쓰레기통 중 하나에 들어간 경우에만 발생 하지만 발생할 수 있습니다. NULL쓰레기통을 통과 할 때 확인하지 마십시오 . 빈이 초기화되지 않았습니다. 각각을 NULL.
그것은에있는 insert()주요 문제의 거짓말. 귀하의 prev변수는 전에 초기화되지 while-loop, 당신은 루프를 입력하지 않은 경우, 그것은 하나 뒤에되지 않습니다. 초기화되지 않은 prev->next = entry시기를 설정 하면 prev문제가 발생하며 충돌 오류의 가능성이 높습니다. 특히 당신이 빈에 무언가를 삽입 처음이 점을 고려 entry할 것이다 NULL오류를 바로 처음 있도록했습니다. 초기화되지 않은 포인터를 역 참조 할 때 어떤 일이 발생하는지 정의되지 않았지만 좋은 의미는 거의 없습니다. 충돌은 최상의 시나리오입니다.
여기 논리를 이해합니다. prev목록을 따라 이동 entry하여 끝에 새 항목 을 삽입 할 수 있으며 저장소의 항목을 반복하기 전에 마지막 요소가 없습니다. 그러나 그렇다고 새 항목을 삽입하려는 위치에 대한 포인터를 초기화 할 수 없다는 의미는 아닙니다. 포인터에 대한 포인터를 사용하는 경우 테이블 배열의 항목으로 시작할 수 있습니다. 그것은 list_nodea list_node *가 아니므로 a 는을 (를)하지 않습니다 prev. 그러나 list_node **will은 잘 작동합니다. 다음과 같이 할 수 있습니다.
node_ptr new_entry(const char *key, const char *value)
{
node_ptr entry = malloc(sizeof *entry);
if (!entry) abort(); // Add error checking
entry->value = malloc(strlen(value) + 1);
entry->key = malloc(strlen(key) + 1);
strncpy(entry->key, key, strlen(key));
strncpy(entry->value, value, strlen(value));
entry->next = NULL;
return entry;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr entry = H->list_ptr_arr[slot];
// Make sure that we always have a prev, by pointing it
// to the location where we want to insert a new entry,
// which we want at the bin if nothing else
node_ptr *loc = &H->list_ptr_arr[slot];
while(entry != NULL)
{
if(strcmp(entry->key, key)==0)
{
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
return;
}
// make loc the entry's next
loc = &entry->next;
// and move entry forward (we don't need prev->next now)
entry = entry->next;
}
// now loc will hold the address we should put
// the entry in
*loc = new_entry(key, value);
}
물론 빈의 목록은 특정 순서로 정렬되거나 유지되지 않기 때문에 (언급하지 않은 제약이없는 한) 새 항목을 추가 할 필요가 없습니다. 앞에 추가 할 수도 있습니다. 그러면 loc다른 선형 검색을 위해 이러한 항목을 드래그 할 필요가 없습니다 . 다음과 같이 할 수 있습니다.
node_ptr find_in_bin(const char *key, node_ptr bin)
{
for (node_ptr entry = bin; entry; entry = entry->next) {
if(strcmp(entry->key, key)==0)
return entry;
}
return 0;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr *bin = &H->list_ptr_arr[slot];
node_ptr entry = find_in_bin(key, *bin);
if (entry) {
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
} else {
*bin = new_entry(key, value, *bin);
}
}
이런 식으로 초기화 및 삽입을 수정하면 코드가 작동해야한다고 생각합니다. 내가 통과 한 몇 가지 테스트에는 적용되지만 뭔가 놓칠 수 있습니다.
그런 오류는 아니지만 여전히 빠르게 언급 할 내용입니다. 이 next_prime()기능은 Eratosthenes의 체의 느린 버전처럼 보입니다. 괜찮습니다. (내가 놓친 것이 아니라면) 소수를 계산하지만 필요한 것은 아닙니다. 구글을 검색하면 꽤 큰 K에 대한 첫 번째 K 프라임 테이블을 찾을 수 있습니다. 코드에 쉽게 임베드 할 수 있습니다. 즉, 테이블에 프라임 크기를 절대적으로 원하는 경우입니다. 하지만 그럴 필요는 없습니다. 다른 크기의 테이블을 갖는 것은 잘못된 것이 아닙니다.
해싱을위한 모듈로 프라임에는 몇 가지 이점이 있지만 해시 테이블이 프라임 크기를 가질 필요는 없습니다. 큰 프라임 P와 크기 M의 해시 테이블이있는 경우 ((i % P) % M)을 수행하고 모듈로 P를 수행하는 이점과 테이블 크기 M을 갖는 편리함을 얻을 수 있습니다. 따라서 M이 2의 거듭 제곱이면 더 쉽고 마지막 모듈로 작업은 매우 빠른 비트 마스킹이 될 수 있습니다.
#define mask_k(n,k) (n & ((1 << k) - 1))
그리고 나중에 ...
int index = mask_k(i % P, k); // where table size is 1 << k
i % P힘은 당신의 해시 함수가 얼마나 좋은에 따라, 필요 하나 없습니다. 난수에 가까운 해시 함수가있는 경우 입력 된 비트 i는 랜덤이고 k최하위 비트도 마찬가지로 % P개선되지 않습니다. 그러나 모듈로 소수를 수행하려면 큰 소수에 대해 수행하고 더 작은 테이블 크기로 마스킹 할 수 있으므로 소수 인 테이블 크기를 사용할 필요가 없습니다. 어쨌든 프라임 테이블 크기를 원한다면 프라임 테이블을 사용하십시오. 테이블 크기를 조정할 때마다 새 소수를 계산해야하는 것은 느립니다.