Ask Question
23 November, 15:24

Provided below is the implementation of the hashtable data structure we went over together in class. You are to implement the rehash method, which will be called with a new size for the internal buckets array. rehash will create a new buckets array, copy all the key/value pairs from the old buckets array into the new one, using linked list chains as before to support collisions, then switch to using the new buckets array. rehash should run in O (N) time, where N is the number of key/value pairs,. Your implementation of rehash should not make use of any other hashtable or list methods (other than those demonstrated in __setitem__ and __getitem__). Note that the first and last lines of rehash are given; you should not alter them.

+5
Answers (1)
  1. 23 November, 15:59
    0
    numBuckets = 47

    def create ():

    global numBuckets

    hSet = []

    for i in range (numBuckets):

    hSet. append ([])

    # print "[XYZ]: create () hSet: ", hSet, " type (hSet) : ", type (hSet)

    return hSet

    def hashElem (e):

    global numBuckets

    return e % numBuckets

    def insert (hSet, i):

    hSet[hashElem (i) ]. append (i)

    # print "[XYZ]: insert () hSet: ", hSet, " type (hSet) : ", type (hSet)

    def remove (hSet, i):

    newBucket = []

    for j in hSet[hashElem (i) ]:

    if j! = i:

    newBucket. append (j)

    hSet[hashElem (i) ] = newBucket

    print "[XYZ]: remove () i: ", i," hashElem[i]: ", hashElem (i), " hSet[hashElem (i) : ", hSet[hashElem (i) ]

    def member (hSet, i):

    return i in hSet[hashElem (i) ]

    def testOne ():

    s = create ()

    for i in range (40):

    insert (s, i)

    print "[XYZ]: S: ", s

    insert (s, 325)

    insert (s, 325)

    insert (s, 9898900067)

    print "[XYZ]: S: ", s

    print "[XYZ]:, member (s, 325) : ", member (s, 325)

    remove (s, 325)

    print "[XYZ]: After Remove, member (s, 325) : ", member (s, 325)

    print "[XYZ]: member (s, 9898900067) ", member (s, 9898900067)

    testOne ()
Know the Answer?
Not Sure About the Answer?
Find an answer to your question ✅ “Provided below is the implementation of the hashtable data structure we went over together in class. You are to implement the rehash ...” in 📘 Computers and Technology if you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers