> For the complete documentation index, see [llms.txt](https://bryan-guner.gitbook.io/my-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-5.md).

# Hash Table

```python
"""
Hashtables (associative arrays)
"""


# linear probing
class HashTable(object):

    def __init__(self):
        self.size = 10
        self.keys = [None] * self.size
        self.values = [None] * self.size

    def put(self, key, data):

        index = self.hashfunction(key)

        # not None -> it is a collision !!!
        while self.keys[index] is not None:
            if self.keys[index] == key:
                self.values[index] = data  # update
                return

            # rehash try to find another slot
            index = (index + 1) % self.size

        # insert
        self.keys[index] = key
        self.values[index] = data

    def get(self, key):

        index = self.hashfunction(key)

        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]

            index = (index + 1) % self.size

        # it means the key is not present in the associative array
        return None

    def hashfunction(self, key):
        sum = 0
        for pos in range(len(key)):
            sum = sum + ord(key[pos])

        return sum % self.size

table = HashTable()

table.put("apple", 10)
table.put("orange", 20)
table.put("car", 30)
table.put("table", 40)

print(table.get("car"))
```

## Hash Table

* Describe an implementation of a least-used cache, and big-O notation of it.
* A question involving an API's integration with hash map where the buckets of hash map are made up of linked lists.
* Implement data structure `Map` storing pairs of integers (key, value) and define following member functions in O(1) runtime: `void insert(key, value)`, `void delete(key)`, `int get(key)`, `int getRandomKey()`.

{% embed url="<https://gist.github.com/bgoonz/4089b60131f0679eb0c16c831e623811>" %}

```python
"""Write a HashTable class that stores strings
in a hash table, where keys are calculated
using the first two letters of the string."""

class HashTable(object):
    def __init__(self):
        self.table = [None]*10000

    def store(self, string):
        """Input a string that's stored in
        the table."""
        index = self.calculate_hash_value(string)
        if(self.lookup(string)==-1):
            self.table[index] = [string]
        else:
            self.table[index].append(string)
        pass

    def lookup(self, string):
        """Return the hash value if the
        string is already in the table.
        Return -1 otherwise."""
        index = self.calculate_hash_value(string)
        if(self.table[index]!=None):
            return index
        else:
            return -1

    def calculate_hash_value(self, string):
        """Helper function to calulate a
        hash value from a string."""
        hash_val = ord(string[0])*100+ord(string[1])
        return hash_val

# Setup
hash_table = HashTable()

# Test calculate_hash_value
# Should be 8568
print hash_table.calculate_hash_value('UDACITY')

# Test lookup edge case
# Should be -1
print hash_table.lookup('UDACITY')

# Test store
hash_table.store('UDACITY')
# Should be 8568
print hash_table.lookup('UDACITY')

# Test store edge case
hash_table.store('UDACIOUS')
# Should be 8568
print hash_table.lookup('UDACIOUS')

#print(hash_table.table)
```

{% content-ref url="/pages/enW2lSXXp3eJnMVAPOII" %}
[Array](/my-docs/pythonnotes/abstract-data-structures/untitled-1/array.md)
{% endcontent-ref %}

{% content-ref url="/pages/WvqmSzLeimHHeTzSVLwo" %}
[Binary Search Tree](/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-search-tree.md)
{% endcontent-ref %}

{% content-ref url="/pages/elNgqdtjORrnmaofkEgI" %}
[Linked List](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-4.md)
{% endcontent-ref %}

{% content-ref url="/pages/vgEVzHJattVXgB9JCcXO" %}
[Extra-Array](/my-docs/pythonnotes/abstract-data-structures/untitled-1/array/extra-array.md)
{% endcontent-ref %}

{% content-ref url="/pages/7eiX2YnAhvNnjY7OiRJy" %}
[Stack](/my-docs/pythonnotes/abstract-data-structures/untitled-1/stack.md)
{% endcontent-ref %}

{% content-ref url="/pages/K2Fb2qoBZc5fio9pP5ZI" %}
[Binary Tree](/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-tree.md)
{% endcontent-ref %}

{% content-ref url="/pages/5w44kr7eSNwzBPsybKTo" %}
[Recursion](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-6.md)
{% endcontent-ref %}

{% content-ref url="/pages/4w3lLbf7UKIMgQ0GuYjN" %}
[Hash Table](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-5.md)
{% endcontent-ref %}

{% content-ref url="/pages/BLnvGjl0WoqZ9npdIr6P" %}
[Searching](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-2.md)
{% endcontent-ref %}

{% content-ref url="/pages/aDu8lYDCInQiGtYNEfzQ" %}
[Sorting](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-3.md)
{% endcontent-ref %}

{% content-ref url="/pages/nemaGQmas79yIx2pLK7y" %}
[Queue Sandbox](/my-docs/pythonnotes/abstract-data-structures/untitled-1/queue/queue-sandbox.md)
{% endcontent-ref %}

{% content-ref url="/pages/4w3lLbf7UKIMgQ0GuYjN" %}
[Hash Table](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-5.md)
{% endcontent-ref %}

{% content-ref url="/pages/Bw6QkD4iYM6zszBi6Pvs" %}
[Double Linked List](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-4/double-linked-list.md)
{% endcontent-ref %}

{% content-ref url="/pages/WKSCy91DvXLWkyMYSwoP" %}
[Graphs](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-1.md)
{% endcontent-ref %}

{% content-ref url="/pages/HA6U4P21mzp0ei2zS5qt" %}
[Exotic](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled.md)
{% endcontent-ref %}

{% content-ref url="/pages/bS4bA0QClN1EyxgFa7pw" %}
[Heap](/my-docs/pythonnotes/abstract-data-structures/untitled-1/heap.md)
{% endcontent-ref %}