# 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="" %} ```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 %} --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-5.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.