Data Structures: Hash Tables

What are Hashtables?

Hashtables are a type of data structures that stores data as key-value pairs. This means every Node or Bucket has both a key, and a value. Hashing can also be defined as a technique that is used to uniquely identify a specific object from a group of similar objects.

Hashtables Components

1. Buckets

A bucket is what is contained in each index of the array of the hashtable. Each index is a bucket. An index could potentially contain multiple key-value pairs if a collision occurs.

2. Collisions

A collision is what happens when more than one key gets hashed to the same location of the hashtable.

3. Hash

A hash is the result of some algorithm taking an incoming string and converting it into a value that could be used for either security or some other purpose. In the case of a hashtable, it is used to determine the index of the array.

The result (hash) is the index of the key-value pair in the hash table.

Pros & Cons of Hash Tables

Can hold keys of many data types as long as they're hashTable.
Worst case time complexity of Access, Insert, Delete or Search are O(n).
Hard to look for maximum and minimum values.
requesting a value with a given key takes O(1).
requesting a key from a given value takes O(n).

Internal Methods

Add()

send the key to the GetHash method.
Once you determine the index of where it should be placed, go to that index
Check if something exists at that index already, if it doesn’t, add it with the key/value pair.
If something does exist, add the new key/value pair to the data structure within that bucket.

Find()

The Find takes in a key, gets the Hash, and goes to the index location specified.
Once the index location is found in the array.
The algorithm iterates through the bucket and see if the key exists and return the value.

Contains()

The Contains method will accept a key, and return a bool on if that key exists inside the hashtable.
The best way to do this is to have the contains call the GetHash and check the hashtable if the key exists in the table given the index returned.

GetHash()

The GetHash will accept a key as a string
conduct the hash.
Return the index of the array where the key-value should be placed.

Implementation

Creating the Hashtmap class

Initializing an object through init method and giving it a size attribute (this size it not static you can put any size you want --> it represents the size of the list that will be created )
Another attribute (map) to create the list of the provided size.

class HashTable:
    def __init__(self, size = 1024):
        self.size = size
        self.map = [None]*size

Hash method

This method takes a stirng key as an argument and returns its hashed value according to ASCII

    def hash(self, key):
        ascii_sum = 0
        for char in key:
            ascii_char = ord(char)
            ascii_sum += ascii_char

        hashed = (ascii_sum * 19) % self.size
        return hashed

Set method

This method sets key-value pairs at the hashed bucket (list) if it was empty or adds them as collisions if it wasn't.
it also updates the key value if it was passed with another value.

    def set(self, key, value):
       // return hashed value which is the index of the key
        hashed = self.hash(key)  

        if self.map[hashed] is None:
            self.map[hashed] = [[key, value]]

        else: 
            self.map[hashed].append([key, value])

Get method

This method takes a key and returns the value associated with that key in the map

    def get(self, key):
        hashed = self.hash(key)
        return self.map[hashed]

Contains method

This method return True if the hashmap contains a specific key, and false if it doesn't

    def contains(self, key):
        if self.map[self.hash(key)]:
            return True

        else:
            return False

keys method

This method returns a new list with all keys in the hashmap

    def keys(self):
        lst = []
        for i in self.map:
            if i:
                [lst.append(index[0]) for index in i]
        return lst