Custom Hashmap

hash.py

class bst:
    def __init__(self, k, v):
        self.left = None
        self.right = None
        self.v = v
        self.k = k
        self.size = 1

    def __str__(self):
        # for debugging only
        return ','.join(['<' + str(node.k) + ',' + str(node.v) + '>' for node in self])

    def __len__(self):
        return self.size

    def __iter__(self):
        # simple dfs generator
        stack = [self]
        node = None
        while len(stack) != 0:
            node = stack.pop()
            if node.right is not None:
                stack.append(node.right)
            
            yield node
            
            if node.left is not None:
                stack.append(node.left)

    def insert(self, k, v):
        # return True if created, False if replaced

        if k == self.k:
            self.v = v
            return False
        
        elif k < self.k:
            if self.left is not None:
                if self.left.insert(k, v):
                    self.size = self.size + 1
                    return True
                else:
                    return False
            else:
                self.left = bst(k, v)
                self.size = self.size + 1
                return True
        
        elif k > self.k:
            if self.right is not None:
                if self.right.insert(k, v):
                    self.size = self.size + 1
                    return True
                else:
                    return False
            else:
                self.right = bst(k, v)
                self.size = self.size + 1
                return True
        return True



class hashmap:
    # use a bst instead of list for collisions
    # still not guaranteed to be O(log n), we need a balanced bst for that
    # Better than a list though in average case

    def __init__(self, size=10, max_entries_in_bucket=2):
        self.hashtable = [None for i in range(size)]
        self.n = size
        self.max_entries_in_bucket = max_entries_in_bucket

    def hash_func(self, k):
        return (k % self.n)

    def is_prime(self, n):
        for f in xrange(2, n):
            if n % f == 0:
                return False
        return True

    def next_best_size(self):
        candidate = self.n + 1
        while not self.is_prime(candidate):
            candidate = candidate + 1
        return candidate

    def get(self, k):
        bucket = self.hashtable[self.hash_func(k)]
        
        if bucket is None:
            return None

        for item in bucket:
            if item.k == k:
                return item[1]
        return None

    def set(self, k, v):
        hash = self.hash_func(k)
        bucket = self.hashtable[hash]
        
        if bucket is None:
            self.hashtable[hash] = bst(k, v)
        else:
            bucket.insert(k, v)

        if len(self.hashtable[hash]) > self.max_entries_in_bucket:
            self.rehash()

    def show(self):
        i = 0
        for bucket in self.hashtable:
            print i, '->', str(bucket)
            i = i + 1

    def rehash(self):
        print 'Rehashing...', self.next_best_size()
        # self.n = self.n * self.incr_factor # increase size to reduce collisions
        self.n = self.next_best_size()
        new_hashtable = [None for i in range(self.n)]

        for bucket in self.hashtable:
            if bucket is not None:
                for item in bucket:
                    k = item.k
                    v = item.v
                    new_bucket = new_hashtable[self.hash_func(k)]
                    if new_bucket is not None:
                        new_bucket.insert(k, v)
                    else:
                        new_hashtable[self.hash_func(k)] = bst(k, v)
        self.hashtable = new_hashtable



if __name__ == '__main__':
    h = hashmap(3)

    try:
        while True:
            ch = input('1. Enter value\n2. Get value\n3. Show All\nChoice (^C to exit) ->> ')
            if ch == 1:
                k = input('Enter k:')
                v = raw_input('Enter v:')
                h.set(k,v)
            elif ch == 2:
                k = input('Enter k:')
                print 'The value for', k, 'is ->', h.get(k)
            elif ch == 3:
                h.show()
            print '---------------------\n'
    except KeyboardInterrupt:
        print '\nBye!\n'