2.4 Hash Table.py

import binascii


class HashNode(object):
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None


class HashTableUsingChaining(object):
    def __init__(self, length, key_type="int"):
        self.hash_table = [HashNode(None, None) for i in range(length)]
        self.key_type = key_type

        # n for hash function mod
        self.hash_function_n = self.__max_prime_num(length)

    def __max_prime_num(self, length):
        """
        Calculate the largest prime number smaller than the length.
        Args:
            length: length of the hash table

        Returns:
            value: largest prim number smaller than the length

        """
        for value in reversed(range(1, length+1)):
            prime = True
            for i in range(2, value):
                if value % i == 0:
                    prime = False
                    break
            if prime:
                return value

        raise IndexError("No prime number found! Try another length!")

    def __hash_function(self, key, n):
        """
        Hash function using mod.
        Args:
            key: integer key to hash
            n: mod n

        Returns:
            index of the key after hashing

        """
        return key % self.hash_function_n

    def __key_type_check(self, key):
        """
        Check the type of keys.

        """
        if self.key_type == "string":
            if not isinstance(key, str):
                raise ValueError("Key type error!")

        elif self.key_type == "int":
            if not isinstance(key, int):
                raise ValueError("Key type error!")

        else:
            raise ValueError("Unknown key type!")

    def __str_to_int(self, key: str):
        """
        Transform from string to integer, in order to use the hash function.

        """
        string = binascii.b2a_hex(key.encode('utf-8'))
        return int(string, 16)

    def insert(self, key, value):
        """
        Insert a key-value pair.
        Args:
            key: integer key
            value: any value

        """
        self.__key_type_check(key)
        key_int = self.__str_to_int(key) if self.key_type == "string" else key

        index = self.__hash_function(key_int, self.hash_function_n)

        if not self.hash_table[index].key:
            self.hash_table[index].key = key
            self.hash_table[index].value = value

        # if the node has already existed, use a chain
        else:
            insert_node = HashNode(key, value)
            insert_node.next = self.hash_table[index]
            self.hash_table[index] = insert_node

    def search(self, key):
        """
        Search for a certain key.

        """
        self.__key_type_check(key)
        key_int = self.__str_to_int(key) if self.key_type == "string" else key

        index = self.__hash_function(key_int, self.hash_function_n)
        node = self.hash_table[index]

        if not node.key:
            print("No key found!")
        else:
            while node.key:
                if node.key == key:
                    print("Key: {}, Value: {}".format(node.key, node.value))
                    break
                else:
                    node = node.next
                    if not node:
                        print("No key found!")
                        break


class HashTableUsingOpenAddressing(object):
    def __init__(self, length,  key_type="int", mode='l'):
        self.hash_table = [HashNode(None, None) for i in range(length)]
        self.length = length
        self.key_type = key_type
        self.hash_function_n = self.__max_prime_num(length)
        self.hash_function_n2 = 5

        if mode == 'l':
            self.hash_mode = "LinearProbing"
        elif mode == 'd':
            self.hash_mode = "DoubleHashing"
        else:
            raise ValueError("Unknown hash table type!")

    def __max_prime_num(self, length):
        """
        Calculate the largest prime number smaller than the length.
        Args:
            length: length of the hash table

        Returns:
            value: largest prim number smaller than the length

        """
        for value in reversed(range(1, length + 1)):
            prime = True
            for i in range(2, value):
                if value % i == 0:
                    prime = False
                    break
            if prime:
                return value

        raise IndexError("No prime number found! Try another length!")

    def __hash_function(self, key, n):
        """
        Hash function using mod.
        Args:
            key: integer key to hash
            n: mod n

        Returns:
            index of the key after hashing

        """
        return key % n

    def __key_type_check(self, key):
        """
        Check the type of keys.

        """
        if self.key_type == "string":
            if not isinstance(key, str):
                raise ValueError("Key type error!")

        elif self.key_type == "int":
            if not isinstance(key, int):
                raise ValueError("Key type error!")

        else:
            raise ValueError("Unknown key type!")

    def __str_to_int(self, key: str):
        """
        Transform from string to integer, in order to use the hash function.

        """
        string = binascii.b2a_hex(key.encode('utf-8'))
        return int(string, 16)

    def insert(self, key, value):
        """
        Insert a key-value pair.
        Args:
            key: integer key
            value: any value

        """
        self.__key_type_check(key)
        key_int = self.__str_to_int(key) if self.key_type == "string" else key

        index = self.__hash_function(key_int, self.hash_function_n)

        if not self.hash_table[index].key:
            self.hash_table[index].key = key
            self.hash_table[index].value = value

        # if the node has already existed, use a linear probing or double hashing
        else:
            pointer = index
            node = self.hash_table[pointer]

            if self.hash_mode == "LinearProbing":
                step = 1
            # double hashing
            else:
                step = self.__hash_function(key, self.hash_function_n2)

            while self.hash_table[pointer].key:
                pointer += step
                if pointer >= self.length:
                    pointer -= self.length
                if pointer == index:
                    raise IndexError("Hash table out of range!")

            self.hash_table[pointer].key = key
            self.hash_table[pointer].value = value

    def search(self, key):
        self.__key_type_check(key)
        key_int = self.__str_to_int(key) if self.key_type == "string" else key

        index = self.__hash_function(key_int, self.hash_function_n)

        if not self.hash_table[index].key:
            print("Key not found!")
        else:
            pointer = index
            node = self.hash_table[pointer]

            if self.hash_mode == "LinearProbing":
                step = 1
            # double hashing
            else:
                step = self.__hash_function(key, self.hash_function_n2)

            while node.key:
                pointer += step
                if pointer >= self.length:
                    pointer -= self.length
                if self.hash_table[pointer].key == key:
                    print("Key: {}, Value: {}".format(self.hash_table[pointer].key, self.hash_table[pointer].value))
                    break
                if pointer == index:
                    print("Key not found!")
                    break


def main():
    #############################
    # hash table for integer
    print("-> hash table for integer")

    hash_table = HashTableUsingChaining(15)
    print("hash function using {}".format(hash_table.hash_function_n))

    # insert chaining test
    hash_table.insert(1, 2341)
    hash_table.insert(14, 1244)

    # search test
    hash_table.search(1)
    hash_table.search(14)
    print('------------------------')

    #############################
    # hash table for string
    print("-> hash table for string")

    hash_table_str = HashTableUsingChaining(15, key_type="string")
    hash_table_str.insert('abc', 123)
    hash_table_str.insert('cdf', 'sfb')
    hash_table_str.search('kfc')
    hash_table_str.search('abc')
    hash_table_str.search('cdf')
    print('------------------------')

    #############################
    # hash table for linear probing
    print("-> hash table for linear probing")

    hash_table_linear_probing = HashTableUsingOpenAddressing(15)
    hash_table_linear_probing.insert(3, 'abc')

    # 16 % 13 = 3, so next index: 3 + 1 = 4
    hash_table_linear_probing.insert(16, 'cdf')
    hash_table_linear_probing.search(14)
    hash_table_linear_probing.search(16)
    print("index 3: {}".format(hash_table_linear_probing.hash_table[3].key))
    print("index 4: {}".format(hash_table_linear_probing.hash_table[4].key))
    print('------------------------')

    #############################
    # hash table for double hashing
    print("-> hash table for double hashing")

    hash_table_double_hashing = HashTableUsingOpenAddressing(15, mode='d')
    hash_table_double_hashing.insert(4, 'abc')

    # 17 % 13 = 4, and 17 % 5 = 2, so next index: 4 + 2 = 6
    hash_table_double_hashing.insert(17, 'cdf')
    hash_table_double_hashing.search(14)
    hash_table_double_hashing.search(16)
    print("index 3: {}".format(hash_table_double_hashing.hash_table[4].key))
    print("index 6: {}".format(hash_table_double_hashing.hash_table[6].key))


if __name__ == "__main__":
    main()