c - 使用哈希搜索来搜索链表

Question

我是初学者。我从来没有做过哈希搜索。但现在，我必须这样做。

我有一个链表，其中包含大约 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;
          }
    }
}

谢谢

Answer 1

您似乎错过了散列的基本概念，它在 hash table 中的常用方式数据结构。请仔细阅读。

基本上，在搜索链表时通常不使用散列；哈希用于在表(数组)中建立索引，以将内容快速映射到数组位置。

一些哈希表解决了与 separate chaining 的冲突，其中每个表槽都是所有已散列到同一位置的项目列表的头部。因此，当您搜索该列表时，您不是按散列搜索(记住，列表中的所有项都具有相同的散列值)，而是进行全面比较。