Question

4. Hashing and Hash Tables. You need to use the ASCII table in the last page for this question. Study the following hash functions for ASCII C strings that are at least 3-char long unsigned hash1(const char, unsigned unsigned vto]+01997 return (v % m); unsigned hash2Cconst char unsigned) unsigned v-o]k(2] 877 return 1 + (v % ( -1)); (a) Given that m-, 7, compute the hash values and fill the following table (3%) String k hash1k, ) hash2(k, 7) aph dfs bfs prim lman kstra (b) Write a C function oahash (const char »k, int i, int m) that computes the probe sequence for open-addressing hash tables with double hashing. (2%) Use both hash1) and hash20) (c) Suppose you insert the strings in (a) (from top to bottom, one by one) into an empty open-addressing hash table of size m7 using double hashing, show the final contents of the hash table. (3%) (d) What will be the expected number of probes required to confirm that a string does not exist in the hash table completed in (c)? (2%)

Answer 1

ta dis bts 오 dijkstia unsianud catash Ctchar r, int , int m) oara TABLE srze l Table -size is efeed aluod double hmh bis 31 dykstra afs bell man for bell man - S Ccollisien

stving to be seanclud is "Xyz" hash (y) is calcud at d Thauh tobl sm contained no stin If other st

2.

unsigned oahash(const char*k,int i,int m)
{
return (hash1(k,m) + i * hash2(k,m)) % TABLE_SIZE;
}