我是初学者。我从来没有做过哈希搜索。但现在,我必须这样做。
我有一个链表,其中包含大约 3500 个随机整数,最高可达 100 万 (1000000) 个值。我想使用散列搜索来搜索任何元素。
调试器在第一个 if(condition) 的函数 ht_set 中给出了段错误。 请告诉我如何解决? 这是我的代码:
typedef struct entry_s
{
int key;
int value;
struct entry_s *next1;
} entry_t;
typedef struct hashtable_s
{
int size;
entry_t **table;
}hashtable_t;
int ht_hash(hashtable_t *hashtable, int key)
{
int index;
index=key%hashtable->size;
return index;
}
entry_t *ht_newpair( int key, int value )
{
entry_t *newpair;
if((newpair = malloc( sizeof( entry_t)))== NULL || newpair->key == key || newpair->value==value)
return NULL;
newpair->next1 = NULL;
return newpair;
}
void ht_set( hashtable_t *hashtable, int key, int value )
{
int bin = 0;
entry_t *newpair = NULL;
entry_t *next1 = NULL;
entry_t *last = NULL;
bin = ht_hash(hashtable, key);
next1 = hashtable->table[bin];
while( next1 != NULL && key==next1->key)
{
last = next1;
next1 = next1->next1;
}
if( next1 != NULL || key==next1->key)
next1->value =value;
else
{
newpair = ht_newpair( key, value );
if( next1 == hashtable->table[ bin ] )
{
newpair->next1 = next1;
hashtable->table[ bin ] = newpair;
}
else if ( next1 == NULL )
last->next1 = newpair;
else
{
newpair->next1 = next1;
last->next1 = newpair;
}
}
}
谢谢
最佳答案
您似乎错过了散列的基本概念,它在 hash table 中的常用方式数据结构。请仔细阅读。
基本上,在搜索链表时通常不使用散列;哈希用于在表(数组)中建立索引,以将内容快速映射到数组位置。
一些哈希表解决了与 separate chaining 的冲突,其中每个表槽都是所有已散列到同一位置的项目列表的头部。因此,当您搜索该列表时,您不是按散列搜索(记住,列表中的所有项都具有相同的散列值),而是进行全面比较。
关于c - 使用哈希搜索来搜索链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22190649/