Problem 1 Consider a hash table forwhich collisions are handled by chainingusing

Question

Problem 1

Consider a hash table forwhich collisions are handled by chainingusing single-linked lists. The keys are integers. The table size is 10. The hash function is h(key) = key % 10. Determine the contents of the hash table AFTER the following sequence of integers have been inserted: 12,44,13,67,23,90,11,25,21, and45. Listthe table index followed by the chain of keys with the newest key listed first. That is,

0 : 90

1: 11, 21

etc

Problem 2

Consider a hash table for which collisions are handled by open addressing based on quadratic probing. The hash function is h(key) = key%23. For each integer key in the sequence 12,44,13,67,23,90,11,25,21, and 45, list the key and the set of table indices tested until insertion is successful. That is:

12 : 12

44 : 21

13 : 13

67 : 21, 22

etc

Note the format of this listing is DIFFERENT from the one in problem 1

Explanation / Answer

#include #include #include #include #define SIZE 20 struct DataItem { int data; int key; }; struct DataItem* hashArray[SIZE]; struct DataItem* dummyItem; struct DataItem* item; int hashCode(int key) { return key % SIZE; } struct DataItem *search(int key) { //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray[hashIndex] != NULL) { if(hashArray[hashIndex]->key == key) return hashArray[hashIndex]; //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; } void insert(int key,int data) { struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem)); item->data = data; item->key = key; //get the hash int hashIndex = hashCode(key); //move in array until an empty or deleted cell while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) { //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } hashArray[hashIndex] = item; } struct DataItem* delete(struct DataItem* item) { int key = item->key; //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray[hashIndex] != NULL) { if(hashArray[hashIndex]->key == key) { struct DataItem* temp = hashArray[hashIndex]; //assign a dummy item at deleted position hashArray[hashIndex] = dummyItem; return temp; } //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; } void display() { int i = 0; for(i = 0; ikey,hashArray[i]->data); else printf(" ~~ "); } printf(" "); } int main() { dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem)); dummyItem->data = -1; dummyItem->key = -1; insert(1, 20); insert(2, 70); insert(42, 80); insert(4, 25); insert(12, 44); insert(14, 32); insert(17, 11); insert(13, 78); insert(37, 97); display(); item = search(37); if(item != NULL) { printf("Element found: %d ", item->data); } else { printf("Element not found "); } delete(item); item = search(37); if(item != NULL) { printf("Element found: %d ", item->data); } else { printf("Element not found "); } }

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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