Hash Table Data Structure.

Hash map use case.


In computer science and programming, a hash table (hash map / dictionary) is a set abstract data type mapping keys to values. A hash function is used to compute an index or a hash code to construct an array of buckets from which the desired value can be found. The hashing is done for faster access to elements and the efficiency of mapping relies on the performance of the used hash function.

Hash Table Data Structure.



In ideal case the hash function will assign each key to a unique bucket, but there are cases of collision (same index for more than one key) due to imperfect hash function, which are solved using several techniques such as separate chaining or open addressing.
We can consider Python's built-in dictionary implementation as a hash mapping or hash table example.

There are many applications of hashing in real life like cryptography, passwords handling, gaming, graphic tools and many more.



Hash Table Data Structure Python code:



class Hash_Table:
 
    # Creating empty bucket
    def __init__(self, size):
        self.size = size
        self.hash_table = self.create_buckets()
 
    def create_buckets(self):
        return [[] for _ in range(self.size)]
 
    # Inserting values
    def set_val(self, key, val):
       
        hashed_key = hash(key) % self.size
         
        bucket = self.hash_table[hashed_key]
 
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
             
            # check if the bucket has same key
            if record_key == key:
                found_key = True
                break
         
        # Update the value if key is not unique or append for new key
        if found_key:
            bucket[index] = (key, val)
        else:
            bucket.append((key, val))
 
    # search value by the key
    def get_val(self, key):
       
        # Get the index
        hashed_key = hash(key) % self.size
         
        # Get the bucket
        bucket = self.hash_table[hashed_key]
 
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
             
            # check if the bucket has same key
            if record_key == key:
                found_key = True
                break
 
        # Return the value by key
        if found_key:
            return record_val
        else:
            return "NOT found"
 
    # Remove a value by key
    def delete_val(self, key):
       
        # Get the index
        hashed_key = hash(key) % self.size
         
        # Get the bucket
        bucket = self.hash_table[hashed_key]
 
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
             
            # check if the bucket has same key
            if record_key == key:
                found_key = True
                break
        if found_key:
            bucket.pop(index)
        return
 
    # Print the hash map
    def __str__(self):
        return "".join(str(item) for item in self.hash_table)
 
 
hash_table = Hash_Table(7)
print ("Empty hash table: ")
print(hash_table)  
# insert some values
hash_table.set_val(111, 'Victoria')  
hash_table.set_val(112, 'Helen')
hash_table.set_val(113, 'Sabina')
hash_table.set_val(115, 'Helen2')
hash_table.set_val(114, 'Tata')
print ("Filled hash table: ")
print(hash_table)

print ("Search a record with key: ")
print(hash_table.get_val(111))
 
print ("Delete a record with key: ")
hash_table.delete_val(112)
print(hash_table)

OUT:
Empty hash table:
[][][][][][][]
Filled hash table:
[(112, 'Helen')][(113, 'Sabina')][(114, 'Tata')][(115, 'Helen2')][][][(111, 'Victoria')]
Search a record with key:
Victoria
Delete a record with key:
[][(113, 'Sabina')][(114, 'Tata')][(115, 'Helen2')][][][(111, 'Victoria')]





See also related topics: