Question

Questions for Hashing and Skiplists

(a) The next two questions relate to the following hashing setup table size is 11 elements . hash keys are lower-case alphabetic strings . the hash function is h(k) code(last Letter (k)) mod 1 1 Where last Letter extracts the last letter from its input and code returns an integer representing the position of the letter in the alphabet (starting at zero). So, for example h(anna) returns 0, h(mob) returns 1 and h(noon) returns 2 . collisions are resolved through chaining Answer the following: i. Draw the hashtable described above after the insertion of the ele- ments: "lake" "fuss" "end" "tent" "sense" "cats" "mop" [6 marks] 11. Is h described above a very good hash function? Briefly justity vour answer [2 marks] (b) Briefly describe the difference between open address hashing and closed address hashing. [2 marks] (c) Given the following sequence of coin tosses, where H stands for head and T stands for tails: HTHTTHTTHTTTHHTHTTTTHTHTTHTTTHTHT. Build a skip list containing the following values: 18 7 80 5 27 14 Show the full state of the skip list after each insertion. Hint: explicitly state the meaning you attach to heads and tails at the start of your answer. [8 marks]

Answer 1

a)

i) Below is the C++ code I hope that i have provided sufficient comments for your better understanding

#include<bits/stdc++.h>
using namespace std;

struct hashtable
{
string s;
hashtable *next;
};

//declaration
char lastletter(string);
int code(char);
void placekey(hashtable*,int,string);

int main()
{
//initialize hash table by empty strings
hashtable a[11],*temp;
int i;

//initialize hash table
for(i=0;i<11;i++)
{
a[i].s="";
a[i].next=NULL;
}

int key;

//find key corresponding to string
key=code(lastletter("lake"))%11;
//place the key in hashtable
placekey(a,key,"lake");

key=code(lastletter("fuss"))%11;
//place the key in hashtable
placekey(a,key,"fuss");

key=code(lastletter("end"))%11;
//place the key in hashtable
placekey(a,key,"end");

key=code(lastletter("tent"))%11;
//place the key in hashtable
placekey(a,key,"tent");

key=code(lastletter("sense"))%11;
//place the key in hashtable
placekey(a,key,"sense");

key=code(lastletter("cats"))%11;
//place the key in hashtable
placekey(a,key,"cats");

key=code(lastletter("mop"))%11;
//place the key in hashtable
placekey(a,key,"mop");

//display the contents of table
for(i=0;i<11;i++)
{
cout<<"index="<<i<<" ";
cout<<a[i].s<<" ";
temp=a[i].next;
while(temp!=NULL)
{
cout<<temp->s<<" ";
temp=temp->next;
}
cout<<endl;
}

return 0;
}

void placekey(hashtable *a,int key,string str)
{
//position is empty hence place the string
if(a[key].s=="")
{
a[key].s=str;
}

//collision occurs hence use chaining
else
{
hashtable *data=new hashtable;
data->s=str;
data->next=NULL;

hashtable *h=&a[key];
while(h->next!=NULL)
{
h=h->next;
}

//insert data
h->next=data;
}
}

int code(char ch)
{
//convert the character in corresponding integer
int p=ch-'a';
return p;
}
char lastletter(string s)
{
return s[s.size()-1];
}

Below is the screenshot of output

ii) A good hash function is one which is evenly distributed and in which collisions are minimum.The given hash function is not good because it uses mod 11 and thier are 26 letters.Hence distribution is not even and also large number of collision takes place.

b)

In Open Addressing, all elements are stored in the hash table itself. Once an object is hashed,it is stored in the hashtable and if that place is already occupied then its location is stored using some probing scheme

In Closed Addressing, none of the objects are actually stored in the hash table's array; instead once an object is hashed, it is stored in a list which is separate from the hash table's internal array.

I will add answer to part c) later due to lack of time

Hope i have answered your question satisfactorily.Leave doubts in comment section if any.