Hashmaps

#datastructures #python #cpp

Definition

Hashmaps, also known as hash tables or dictionaries, are a fundamental data structure in computer science used to efficiently store and retrieve key-value pairs. In a hashmap, each key is mapped to a specific value through a hash function, which converts the key into a numeric index that is used to store and retrieve the associated value in an array-like data structure called a bucket.

The process of adding a key-value pair to a hashmap involves the following steps:

The hash function takes the key as input and produces a hash code, which is an integer value that represents the key in a more compact and standardized form.
The hash code is then used to compute an index into the array-like bucket structure, where the value associated with the key can be stored.
If there is already a value stored at the computed index, a collision has occurred, and a collision resolution strategy is used to handle the collision and store the new value in a different bucket.
If there is no value stored at the computed index, the new key-value pair is stored in the bucket at that index.
When retrieving a value from a hashmap, the process is similar:
The hash function is applied to the key to compute the hash code.
The hash code is used to compute the index into the bucket structure where the value should be stored.
The value at the computed index is returned, or if there is no value stored at that index, the key is not in the hashmap.
Hashmaps have several advantages over other data structures for storing key-value pairs. First, they offer fast average-case performance for accessing and retrieving values, with a time complexity of O(1) for both operations. Second, they can handle a large number of key-value pairs without requiring significant amounts of memory. Finally, hashmaps are dynamic data structures that can be resized and rehashed as needed to accommodate changes in the number of key-value pairs.

Implementation

class HashTable:
    def __init__(self, size):
        self.size = size
        self.hash_table = self.create_buckets()

    def create_buckets(self):
        return [[] for _ in range(self.size)]

    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
            if record_key == key:
                found_key = True
                break
        if found_key:
            bucket[index] = (key, val)
        else:
            bucket.append((key, val))

    def get_val(self, key):
        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
            if record_key == key:
                found_key = True
                break
        if found_key:
            return record_val
        else:
            return "No record found"

    def delete_val(self, key):
        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
            if record_key == key:
                found_key = True
                break
        if found_key:
            bucket.pop(index)
        return

    def __str__(self):
        return "".join(str(item) for item in self.hash_table)

Disadvantages:
However, hashmaps also have some disadvantages. The most significant issue is the possibility of collisions, which can degrade the performance of the data structure if not handled properly. Additionally, hashmaps can be vulnerable to certain types of attacks, such as hash collision attacks, which can be used to overwhelm the bucket structure with intentionally crafted keys.

To address these issues, hashmaps use various techniques for collision resolution, such as chaining (where multiple values are stored in the same bucket as a linked list) or open addressing (where additional buckets are probed until an empty bucket is found). Additionally, hash functions can be designed to minimize the likelihood of collisions or to be resistant to collision attacks.

Top comments (3)

Alessio Izzo • Mar 22 '23

I'm sorry but I don't get why you are using this structure. Why don't you use dictionaries in python?
As a general advice: the code looks complicated and maybe a simple example of how to use it would help a lot understanding what you want to achieve or the problem you want to solve.