hash table data[CAPACITY]. The hash table uses open addressing with linear probi

Question

hash table data[CAPACITY]. 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. All valid keys will be non-negative, and the hash function is:

int hash(int key)

{

return (key % CAPACITY);

}

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

Implement the following functions.

const int CAPACITY = 10;

void initTable(int data[]); //Locations of the table that have NEVER been used will contain the key -1

void printTheTable(int data[]);

int hash(int key);

void hash_Insert(int data[], int key);

bool check_key(int data[], int search_key);

Explanation / Answer

const int CAPACITY = 10;

void initTable(int data[])

{
int i = 0;
for(i = 0;i<CAPACITY;i++){
data[i] = -1;
}
}

int hash(int key){
return (key%CAPACITY);   
}

void hash_insert(int data[],int key){

int new_key = hash(key);

if(data[new_key] == -1){
data[new_key] = key;
return;
}
else{
int j = 1;
while(data[new_key] != -1 && j<=CAPACITY){
new_key = hash(key+1);
j++;
}
if(j > CAPACITY){
cout<<"Hash table is full";
return;
}
data[new_key] = key;
}

}

bool check_key(int data[], int search_key){
int new_key = hash(key);
while(data[new_key] == search_key && j<=CAPACITY){
new_key = hash(key+1);
j++;
}
if(j > CAPACITY){
cout<<"no entry found";
return;
}
return true;
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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