# Create six hash tables - 2 hashing schemes x 3 collision handling schemes

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):
for i in xrange(len(self._table)):
self._table[i] = []

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

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

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

_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)

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

_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

pass

def hash_function_2(self, key):
return key % self._m2

class MultiplicationChainingHashTable(MultiplicationMethodMixin, ChainingMixin, HashTable):
pass

pass

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.

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?)