Question

Implement your own version of the following Hash table in python language with mentioned functionalities: • Insert • Delete • Contains • Get Value by key • Size • Iterator • Traverse/Print

Answer 1

# A node of chains
class HashNode(object):


    # Reference to next node


    # Constructor
    def __init__(self, key, value, hashCode):
        #instance fields found by Java to Python Converter:
        key = None
        value = None
        hashCode = 0
        self.next = None


        self.key = key
        self.value = value
        self.hashCode = hashCode


# Class to represent entire hash table
class Map(object):
    # bucketArray is used to store array of chains


    # Current capacity of array list


    # Current size of array list


    # Constructor (Initializes capacity, size and
    # empty chains.
    def __init__(self):
        #instance fields found by Java to Python Converter:
        self.__bucketArray = None
        self.__numBuckets = 0
        self.__size = 0


        self.__bucketArray = []
        self.__numBuckets = 10
        self.__size = 0


        # Create empty chains
        i = 0
        while i < self.__numBuckets:
            self.__bucketArray.append(None)
            i += 1


    def size(self):
        return self.__size
    def isEmpty(self):
        return len(self.this) == 0


    def __hashCode(self, key):
        return java.util.Objects.hashCode(key)


    # This implements hash function to find index
    # for a key
    def __getBucketIndex(self, key):
        hashCode = self.__hashCode(key)
        index = hashCode % self.__numBuckets
        # key.hashCode() coule be negative.
        index = index * -1 if index < 0 else index
        return index


    # Method to remove a given key
    def remove(self, key):
        # Apply hash function to find index for given key
        bucketIndex = self.__getBucketIndex(key)
        hashCode = self.__hashCode(key)
        # Get head of chain
        head = self.__bucketArray[bucketIndex]


        # Search for key in its chain
        prev = None
        while head is not None:
            # If Key found
            if head.key is key and hashCode == head.hashCode:
                break


            # Else keep moving in chain
            prev = head
            head = head.next


        # If key was not there
        if head is None:
            return None


        # Reduce size
        self.__size -= 1


        # Remove key
        if prev is not None:
            prev.next = head.next
        else:
            self.__bucketArray[bucketIndex] = head.next


        return head.value


    # Returns value for a key
    def get(self, key):
        # Find head of chain for given key
        bucketIndex = self.__getBucketIndex(key)
        hashCode = self.__hashCode(key)


        head = self.__bucketArray[bucketIndex]


        # Search key in chain
        while head is not None:
            if head.key is key and head.hashCode == hashCode:
                return head.value
            head = head.next


        # If key not found
        return None


    # Adds a key value pair to hash
    def add(self, key, value):
        # Find head of chain for given key
        bucketIndex = self.__getBucketIndex(key)
        hashCode = self.__hashCode(key)
        head = self.__bucketArray[bucketIndex]


        # Check if key is already present
        while head is not None:
            if head.key is key and head.hashCode == hashCode:
                head.value = value
                return
            head = head.next


        # Insert key in chain
        self.__size += 1
        head = self.__bucketArray[bucketIndex]
        newNode = HashNode(key, value, hashCode)
        newNode.next = head
        self.__bucketArray[bucketIndex] = newNode


        # If load factor goes beyond threshold, then
        # double hash table size
        if (1.0 * self.__size) / self.__numBuckets >= 0.7:
            temp = self.__bucketArray
            self.__bucketArray = []
            self.__numBuckets = 2 * self.__numBuckets
            self.__size = 0
            i = 0
            while i < self.__numBuckets:
                self.__bucketArray.append(None)
                i += 1


            for headNode in temp:
                while headNode is not None:
                    self.add(headNode.key, headNode.value)
                    headNode = headNode.next


    # Driver method to test Map class
    @staticmethod
    def main(args):
        map = Map()
        map.add("this", 1)
        map.add("coder", 2)
        map.add("this", 4)
        map.add("hi", 5)
        print(len(map))
        print(map.pop("this"))
        print(map.pop("this"))
        print(len(map))
        print(not map)