> For the complete documentation index, see [llms.txt](https://py-v2.gitbook.io/datastructures-in-pytho/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://py-v2.gitbook.io/datastructures-in-pytho/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/-MiknVIveZ2bsgbftGA-" %}
[Array](/datastructures-in-pytho/abstract-data-structures/untitled-1/array.md)
{% endcontent-ref %}

{% content-ref url="/pages/-MijCdFOOut61t8F5Btg" %}
[Broken mention](broken://pages/-MijCdFOOut61t8F5Btg)
{% endcontent-ref %}

{% content-ref url="/pages/-MikqNsTv4w1fWqC6Y43" %}
[Binary Search Tree](/datastructures-in-pytho/abstract-data-structures/untitled-1/binary-search-tree.md)
{% endcontent-ref %}

{% content-ref url="/pages/-MikVdCCbgqgLy\_M4dTE" %}
[Linked List](/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-4.md)
{% endcontent-ref %}

{% content-ref url="/pages/-Mj3ntRThI\_vo12JGZ0X" %}
[Extra-Array](/datastructures-in-pytho/abstract-data-structures/untitled-1/array/extra-array.md)
{% endcontent-ref %}

{% content-ref url="/pages/-Mj2XpLyHFcsBfbPHIoe" %}
[Stack](/datastructures-in-pytho/abstract-data-structures/untitled-1/stack.md)
{% endcontent-ref %}

{% content-ref url="/pages/-MikVdLCmv7EpCLrboRo" %}
[Binary Tree](/datastructures-in-pytho/abstract-data-structures/untitled-1/binary-tree.md)
{% endcontent-ref %}

{% content-ref url="/pages/-MijCeYPz6AN7g1l\_XjH" %}
[Broken mention](broken://pages/-MijCeYPz6AN7g1l_XjH)
{% endcontent-ref %}

{% content-ref url="/pages/-MikVdILddI6WdL0wQfX" %}
[Recursion](/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-6.md)
{% endcontent-ref %}

{% content-ref url="/pages/-MikVdF16KtPDUwqD8eb" %}
[Hash Table](/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-5.md)
{% endcontent-ref %}

{% content-ref url="/pages/-MikVd4o\_RQF16iMPPiI" %}
[Searching](/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-2.md)
{% endcontent-ref %}

{% content-ref url="/pages/-MikVd8R1sRWADHQ4CTZ" %}
[Sorting](/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-3.md)
{% endcontent-ref %}

{% content-ref url="/pages/-Mj3wNE4b78xsKaL\_o0S" %}
[Queue Sandbox](/datastructures-in-pytho/abstract-data-structures/untitled-1/queue/queue-sandbox.md)
{% endcontent-ref %}

{% content-ref url="/pages/-MikVdF16KtPDUwqD8eb" %}
[Hash Table](/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-5.md)
{% endcontent-ref %}

{% content-ref url="/pages/-Mj3LVs7DQBZd0qV6uc7" %}
[Double Linked List](/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-4/double-linked-list.md)
{% endcontent-ref %}

{% content-ref url="/pages/-MikVbqocxg2W4MYf8TS" %}
[Graphs](/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-1.md)
{% endcontent-ref %}

{% content-ref url="/pages/-MikVb-\_tqwYyiA4v7Tm" %}
[Exotic](/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled.md)
{% endcontent-ref %}

{% content-ref url="/pages/-Mj8l2MkH2-0NJA5QV56" %}
[Heap](/datastructures-in-pytho/abstract-data-structures/untitled-1/heap.md)
{% endcontent-ref %}