3
\$\begingroup\$

This code is meant to implement a hash table class which uses linear probing.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

class Hash:
    def __init__(self):
        self.size = 11
        self.vals = [None] * self.size
        self.keys = [None] * self.size
        self.step = 1

    def put(self, key, val):
        ind = self.hash(key)

        if self.keys[ind] == None:
            self.keys[ind] = key
            self.vals[ind] = val

        elif self.keys[ind] == key:
            self.vals[ind] = val

        else:
            ind = self.rehash(ind)

            while (self.keys[ind] != None and 
                   self.keys[ind] != key):
                ind = self.rehash(ind)

            if self.keys[ind] == None:
                self.keys[ind] = key
                self.vals[ind] = val

            elif self.keys[ind] == key:
                self.vals[ind] = val

    def get(self, key):
        ind = self.hash(key)
        start_ind = ind
        val = None
        done = False

        while not done:
            if self.keys[ind] == key:
                val = self.vals[ind]
                done = True

            else:
                ind = self.rehash(ind)

                if ind == start_ind:
                    done = True

                elif self.keys[ind] == None:
                    done = True

        return val

    def hash(self, key):
        return key % self.size

    def rehash(self, oldhash):
        return (oldhash + self.step) % self.size

    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, val):
        self.put(key, val)
\$\endgroup\$
2
\$\begingroup\$

break (or better yet return)

Instead of doing done = False/True. You could just use break and get rid of done altogether. But even better than that, just return.

This:

        if self.keys[ind] == key:
            val = self.vals[ind]
            done = True

Becomes:

        if self.keys[ind] == key:
            return self.vals[ind] # Value found!

This:

            if ind == start_ind:
                done = True

            elif self.keys[ind] == None:
                done = True

Becomes:

            if ind == start_ind: # Not found!
                return

            elif self.keys[ind] == None: # Not found!
                return

(You can return None if you want).

This gets rid of the val variable (and done)

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions. Does that mean that instead of while not done: I would use while True:? \$\endgroup\$ – cycloidistic Nov 18 '16 at 8:24
  • \$\begingroup\$ @cycloidistic: Yes. \$\endgroup\$ – Dair Nov 18 '16 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.