7
\$\begingroup\$

I was asked to solve the following task:

Given two methods for hashing (division and multiplication) and three methods for collision handling (chaining, open addressing w/ quadratic probing, and open addressing w/ double hashing), contruct classes for all six combinations.

All classes have a parameter \$m\$, classes using the multiplication method require a parameter \$A\$, and classes using double hashing require a second parameter, like \$m_2\$ and/or \$A_2\$.

I took this task purely as a design exercise, so the actual implementation of the algorithms is not important to me.

After lots of thinking, I produced the following design:

from abc import ABCMeta, abstractmethod

class HashTable(object):
    """Abstract base class for hash table.

    Attributes
    ----------
    m : int
        Size of underlying array.

    m_2 : int, optional
        Parameter for second hash function.

    A : float, optional
        Parameter for multiplication method.

    A_2 : float, optional
        Parameter for second multiplication hash function.

    """

    __metaclass__ = ABCMeta

    def __init__(self, m, m_2=None, A=None, A_2=None):
        self._m = m
        self._m2 = m_2
        self._A = A
        self._A2 = A_2
        self._table = [None] * m

    @abstractmethod
    def hash_function(self, key):
        """Return `h(key)`.

        Parameters
        ----------
        key : int
            Value to hash.

        Returns
        -------
        int
            Value between 0 and `m` - 1.

        """
        pass

    @abstractmethod
    def insert(self, key):
        """Insert `key` to hash table.

        Parameters
        ----------
        key
            The key to insert.

        Returns
        -------
        int
            Number of operations needed.

        """
        pass

    @abstractmethod
    def delete(self, key):
        """Delete `key` from the hash table.

        Parameters
        ----------
        key
            The key to delete.

        Returns
        -------
        int
            Number of operations needed.

        """
        pass

    @abstractmethod
    def member(self, key):
        """Check if `key` is in the hash table.

        Parameters
        ----------
        key
            The key to search.

        Returns
        -------
        bool
            True if `key` was found, False otherwise.

        int
            Number of operations needed.

        """
        pass

class DivisionMethodMixin(object):
    def hash_function(self, key):
        return key % self._m

class MultiplicationMethodMixin(object):
    def hash_function(self, key):
        kA = key * self._A
        return int(self._m * (kA - int(kA)))

class ChainingMixin(object):
    def _add_linked_lists(self):
        for i in xrange(len(self._table)):
            self._table[i] = []
        self._add_linked_lists = lambda: None

    def insert(self, key):
        self._add_linked_lists()
        self._table[self.hash_function(key)].append(key)
        return 1

    def delete(self, key):
        self._add_linked_lists()
        self._table[self.hash_function(key)].remove(key)
        return 1

    def member(self, key):
        self._add_linked_lists()
        return (key in self._table[self.hash_function(key)], 1)

class OpenAddressingMixin(object):

    _deleted = object()  # Use a special object to mark deleted keys

    def insert(self, key):
        num_ops = 0
        for i in xrange(self._m):
            num_ops += 1
            hk = self._h(key, i)
            if self._table[hk] in (None, self._deleted):
                self._table[hk] = key
                break
        return num_ops

    def delete(self, key):
        num_ops = 0
        for i in xrange(self._m):
            num_ops += 1
            hk = self._h(key, i)
            if self._table[hk] == key:
                self._table[hk] = self._deleted
                break
        return num_ops

    def member(self, key):
        num_ops = 0
        for i in xrange(self._m):
            num_ops += 1
            hk = self._h(key, i)
            if self._table[hk] is None:
                return (False, num_ops)
            if self._table[hk] == key:
                return (True, num_ops)
        return (False, num_ops)

class OpenAddressingQuadraticProbingMixin(OpenAddressingMixin):
    _h = lambda self, key, i: (self.hash_function(key) + i * i) % self._m

class OpenAddressingDoubleHashingMixin(OpenAddressingMixin):
    _h = lambda self, key, i: (self.hash_function(key) + i * self.hash_function_2(key)) % self._m2

The six required classes are now implemented like so:

class DivisionChainingHashTable(DivisionMethodMixin, ChainingMixin, HashTable):
    pass

class DivisionOAQPHashTable(DivisionMethodMixin, OpenAddressingQuadraticProbingMixin, HashTable):
    pass

class DivisionOADHHashTable(OpenAddressingDoubleHashingMixin, DivisionMethodMixin, HashTable):
    def hash_function_2(self, key):
        return key % self._m2

class MultiplicationChainingHashTable(MultiplicationMethodMixin, ChainingMixin, HashTable):
    pass

class MultiplicationOAQPHashTable(MultiplicationMethodMixin, OpenAddressingQuadraticProbingMixin, HashTable):
    pass

class MultiplicationOADHHashTable(OpenAddressingDoubleHashingMixin, MultiplicationMethodMixin, HashTable):
    def hash_function_2(self, key):
        kA = key * self._A2
        return int(self._m2 * (kA - int(kA)))

The code was written with Python 2.7 in mind, and that is why I don't use meta=ABCMeta in HashTable's declaration, and do explicitly inherit from object. Other than that, I think this code should be compatible with Python 3.6, too.

This design solves the problem, and I think I managed to avoid code duplication and maximize reuse to the best of my abilities. Still, I believe this code is smelly, and something about it bothers me.

I would love to read your opinions on the design, and how would you tackle the problem.

\$\endgroup\$
1
\$\begingroup\$

I don't remember much about different hash tables, but the fact that I haven't been able to figure it out from your code is should say something to you.

For example you m parameter should be named size. We are in python so insert should be __setitem__, member is __contains__ and there is also __getattr__. And they should take object not its key, right?

Next thing. Remember prefer delegation to inheritance? Well it would really be easier to pass a hash function into a constructor instead of using inheritance.

You hash function so far can be described as def f(key, size, *args) or even def f(key, *args)

def multiplication_hash(key, x, y):
    # see how math.modf can be used instead of introducing kA variable
    _, frac = math.modf(x * key)
    return int(y * frac)

t = HashTable(hashfunc=operator.mod)

You don't need to return numops in __getitem__ but still This would be more performant.

def insert(self, key):
    # what this cryptic `_h` and why is parameter is `key` and not the `obj`?
    for i in xrange(self._m):
        hk = self._h(key, i)
        val = self._table[hk]
        # why not mark deleted objects with None?
        if val is None or val is self._deleted:
            self._table[hk] = key
            return i
    return self.size

Oh all this abc stuff. First of all there is collections.Mapping which you can extend. Second I've used it extensively after switching from java to python, but then just stopped.

First of all I'm trying to use classes and dumb data holders as much as possible. Second the standard raise NotImplemented idiom is recognized by linters and IDE (PyCharm) so @abstractmethod isn't doing any good in real life (you're not using notepad to code, right?)

\$\endgroup\$

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.