Sample Data Structures Questions Chapter 12 Searching 8. Suppose that I have the

Question

Sample Data Structures Questions
Chapter 12
Searching

8. Suppose that I have the following record_type definition for a record in a hash table:

The hash table uses open addressing with linear probing. The table size is a global constant called CAPACITY. Locations of the table that have NEVER been used will contain the key -1. Locations of the table that were once used but are now vacant will contain the key -2. All valid keys will be non-negative, and the hash function is:

Complete the implementation of the following function. There is no need to check the precondition, but your code must be as efficient as possible.

Explanation / Answer

// hash table

struct record_type

{

int key;

//... other stuff may also appear here ...

};

size_t hash(int key)

{

return (key % CAPACITY);

}

bool key_occurs(const record_type data[], int search_key)

{

// get hash to add to hashmap

int hash = hash(search_key);

// iterate over map and search for hash

while (record_type[hash] != NULL && record_type[hash]->key != search_key)

{

hash = HashFunc(hash + 1);

}

if (record_type[hash] == NULL)

return false;

else

// return true if found

return true;

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.