# 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="array" %}
[array](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/array)
{% endcontent-ref %}

{% content-ref url="broken-reference" %}
[Broken link](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/broken-reference)
{% endcontent-ref %}

{% content-ref url="binary-search-tree" %}
[binary-search-tree](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/binary-search-tree)
{% endcontent-ref %}

{% content-ref url="untitled-4" %}
[untitled-4](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-4)
{% endcontent-ref %}

{% content-ref url="array/extra-array" %}
[extra-array](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/array/extra-array)
{% endcontent-ref %}

{% content-ref url="stack" %}
[stack](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/stack)
{% endcontent-ref %}

{% content-ref url="binary-tree" %}
[binary-tree](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/binary-tree)
{% endcontent-ref %}

{% content-ref url="broken-reference" %}
[Broken link](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/broken-reference)
{% endcontent-ref %}

{% content-ref url="untitled-6" %}
[untitled-6](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-6)
{% endcontent-ref %}

{% content-ref url="untitled-5" %}
[untitled-5](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-5)
{% endcontent-ref %}

{% content-ref url="untitled-2" %}
[untitled-2](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-2)
{% endcontent-ref %}

{% content-ref url="untitled-3" %}
[untitled-3](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-3)
{% endcontent-ref %}

{% content-ref url="queue/queue-sandbox" %}
[queue-sandbox](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/queue/queue-sandbox)
{% endcontent-ref %}

{% content-ref url="untitled-5" %}
[untitled-5](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-5)
{% endcontent-ref %}

{% content-ref url="untitled-4/double-linked-list" %}
[double-linked-list](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-4/double-linked-list)
{% endcontent-ref %}

{% content-ref url="untitled-1" %}
[untitled-1](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled-1)
{% endcontent-ref %}

{% content-ref url="untitled" %}
[untitled](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/untitled)
{% endcontent-ref %}

{% content-ref url="heap" %}
[heap](https://py-v2.gitbook.io/datastructures-in-pytho/abstract-data-structures/untitled-1/heap)
{% endcontent-ref %}