· 8 years ago · Mar 12, 2018, 02:32 AM
1#!/usr/bin/env python3
2# -*- coding: utf-8 -*-
3
4# Implementing an Open-Address Hash Table in Python
5
6# This implementation uses the multiplication hash method and linear probing
7
8from math import sqrt
9from math import floor
10
11class HashTable(object):
12 def __init__(self, arr = None, table_size = 8):
13 """
14 Accepts an array of unique integers and a table size (both optional)
15 Creates a HashTable object that utilizes open addressing
16 """
17 # Create a flag for deleted items
18 self.deleted = (False, False)
19 # Min load factor, resize when table is less than 1/4 full
20 self.min_load = 1/4
21 # Max load factor, resize when table is more than 2/3 full
22 self.max_load = 2/3
23 # Track total number of elements in the array in order to resize as needed
24 self.elements = 0
25 # If an initial array is supplied, set initial table size to 4*n
26 # and insert each element into the array
27 if arr != None:
28 self.table_size = len(arr)*4
29 self.table = self.__create_array(self.table_size)
30 for item in arr:
31 self.insert(item)
32 # If there is no supplied array, generate a hash table using
33 # default values
34 else:
35 self.table_size = table_size
36 self.table = self.__create_array(self.table_size)
37
38 def __str__(self):
39 """ Returns the keys stored in HashTable as a string """
40 return str(self.table)
41
42 def delete(self, key):
43 """
44 Accepts a key
45 Deletes key from hash table if it exists
46 """
47 if self.contains(key):
48 deletion_index = self.__del_probe(key)
49 self.table[deletion_index] = self.deleted
50 self.elements -= 1
51 # Resize table if it becomes too small
52 if self.elements < self.min_load * self.table_size:
53 self.__shrink_table()
54 else:
55 print("The hash table does not contain the value: " + str(key))
56
57 def insert(self, key):
58 """ Accepts key. Inserts it into the hash table. """
59 # Track num elements in table
60 self.elements += 1
61 # Make sure adding the element does not surpass load factor,
62 # If it does, grow table before adding element
63 if self.elements > self.max_load * self.table_size:
64 self.__grow_table()
65 # Probe for first available insertion point
66 insertion_index = self.__ins_probe(key)
67 self.table[insertion_index] = key
68
69 def contains(self, key):
70 """ Accepts key. Checks if it is contained in the hash table """
71 # If __del_probe returns a value > 0, it is contained
72 if self.__del_probe(key) >= 0:
73 return True
74 else:
75 return False
76
77 def __ins_probe(self, key):
78 """ Accepts key
79 Returns first empty index to store key via linear probing
80 """
81 index = self.__hash_key(key)
82 # Check from given index to end of table
83 for i in range(index, self.table_size):
84 if self.table[i] == None or self.table[i] == self.deleted:
85 return i
86 # If the table is full from index to end of table, check first half
87 # This is possible b/c linear probing hash tables are prone to clustering
88 for i in range(0, index):
89 if self.table[i] == None or self.table[i] == self.deleted:
90 return i
91
92 def __del_probe(self, key):
93 """ Accepts key
94 Returns first index containing key via linear probing
95 """
96 index = self.__hash_key(key)
97 # Check from given index to end of table
98 for i in range(index, self.table_size):
99 if self.table[i] != None or self.table[i] != self.deleted:
100 if self.table[i] == key:
101 return i
102 # If the table is full from index to end of table, check first half
103 # This is possible b/c linear probing hash tables are prone to clustering
104 for i in range(0, index):
105 if self.table[i] != None or self.table[i] != self.deleted:
106 if self.table[i] == key:
107 return i
108 # If no index containing the key has been found, return false
109 return -1
110
111 def __hash_key(self, key):
112 """
113 Implementation of the Multiplication Hashing Method
114 Accepts Key, Returns index of array to store key in
115 """
116 constant_factor = (sqrt(5) - 1) / 2
117 hashed_key = floor(self.table_size * (key * constant_factor % 1))
118 return hashed_key
119
120 def __shrink_table(self):
121 """
122 Reduces table size by a factor of 2
123 """
124 # Adjust table_size value to new value
125 self.table_size = self.table_size // 2
126 # Table doubling for amortized O(1)
127 self.__resize(self.table_size)
128
129 def __grow_table(self):
130 """ Increases table size by a factor of 2 """
131 # Adjust table_size value to match
132 self.table_size = 2 * self.table_size
133 # Table doubling for amortized O(1)
134 self.__resize(self.table_size)
135
136 def __resize(self, size):
137 """
138 Creates a new array of given size which contains all elements
139 that existed in the original hash table
140 """
141 # Copy the current table
142 old_table = list(self.table)
143 # Create a new table of the appropriate size
144 self.table = self.__create_array(size)
145 # Start tracking total elements again
146 self.elements = 0
147 # Populate the table with old values, (except deleted flag)
148 for element in old_table:
149 if element != self.deleted and element != None:
150 self.insert(element)
151
152 def __create_array(self, size):
153 """ Creates an array of given size, populated with None """
154 return [None]*size