Please use PYTHON3 and the knowledge of hash function to solve the problem and f

Question

Please use PYTHON3 and the knowledge of hash function to solve the problem and fill in the blanks.

4. (1.5 pts) A hash table has 13 buckets (i.e. its table size is 13) When strings are stored in the hash table, we use the following hash function to return the bucket to use to store the string in: def h(string data, table_size): k=0 for i in range(0,len(string data)): bucketnumber = k % tablesize return bucket_number k = k * 256 + ord (string, data [1]) - - In the function above, ord(string[i]) returns the ASCII code of the ith character of string Here are the ASCII codes for the lowercase letters: a b Cd e f 97 98 99 100 101 102 103 104 105 106 107 108 109 h i k 1 m 102335422

Explanation / Answer

"fox"

    Here ascii value of f is 102

   ascii value of o is 111

   ascii value of x is 120

    Here k = ( ( 0 * 256 + 102 ) * 256 + 111 ) * 256 + 120 = 6713208

            bucket_number = k % 13 = 8

            collision (n) [No collision as Bucket 8 is available initially]

"dog"

    Here ascii value of d is 100

   ascii value of o is 111

   ascii value of g is 103

    Here k = ( ( 0 * 256 + 100 ) * 256 + 111 ) * 256 + 103 = 6582119

            bucket_number = k % 13 = 11

            collision (y) [Bucket 11 is already filled with "cow" hence this is collision]

"owl"

    Here ascii value of o is 111

   ascii value of w is 119

   ascii value of l is 108

    Here k = ( ( 0 * 256 + 111 ) * 256 + 119 ) * 256 + 108 = 7305068

            bucket_number = k % 13 = 4

            collision (n) [No collision as Bucket 4 is available initially]
        

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---