CODEWITHSUNDEEP
clinuxhashlinked-list
Meghan
Meghan

Reputation: 305

Searching a linked list using hash search

I am a beginner. I have never done hash search. But now, I just have to do it.

I have a linked list containing about 3500 random integers upto 10 lakh(1000000) value. I want to search any element using hash search.

debugger is giving seg fault in the function ht_set on first if(condition) . Please tell me how to resolve it? Here is my code : 

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;
          }
    }
}

Thanks

Upvotes: 0

Views: 902

Answers (1)

unwind
unwind

Reputation: 399803

You seem to be missing out on the basic idea of hashing, how it's commonly used in the hash table data structure. Please read up on it.

Basically, hashes are not typically used when searching a linked list; the hash is used to build an index into a table (an array), to get that quick mapping of the content onto an array location.

Some hash tables resolve collisions with separate chaining, in which each table slot is the head of a list of items that all have hashed to the same place. So, when you're searching that list, you're not searching by hash (remember, all items in the list have the same hash value) but doing full comparisons.

Upvotes: 2

Related Questions