Bottom Page

• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 Help me understand what to do silverfang Programmer named Tim Posts: 5 Threads: 3 Joined: Aug 2019 Reputation: 0 Likes received: 0 #1 Aug-03-2019, 04:26 AM (This post was last modified: Aug-03-2019, 04:27 AM by silverfang. Edited 1 time in total.) Here is the question I am given: (Implement Map using open addressing with quadratic probing) Implement Map using open addressing with quadratic probing. For simplicity, use f(key) = key % size as the hash function, where size is the hash-table size. Initially, the hash- table size is 4. The table size is doubled whenever the load factor exceeds the threshold (0.5). I have absolutely no idea what to do here. Any help is welcomed and appreciated! Below is the code I am given for the problem. ```# Define the default hash-table size DEFAULT_INITIAL_CAPACITY = 4 # Define default load factor DEFAULT_MAX_LOAD_FACTOR = 0.75 # Define the maximum hash-table size to be 2 ** 30 MAXIMUM_CAPACITY = 2 ** 30 class Map: def __init__(self, capacity = DEFAULT_INITIAL_CAPACITY, loadFactorThreshold = DEFAULT_MAX_LOAD_FACTOR): # Current hash-table capacity. Capacity is a power of 2 self.capacity = capacity # Specify a load factor used in the hash table self.loadFactorThreshold = loadFactorThreshold # Create a list of empty buckets self.table = [] for i in range(self.capacity): self.table.append([]) self.size = 0 # Initialize map size # Add an entry (key, value) into the map def put(self, key, value): if self.size >= self.capacity * self.loadFactorThreshold: if self.capacity == MAXIMUM_CAPACITY: raise RuntimeError("Exceeding maximum capacity") self.rehash() bucketIndex = hash(key) % self.capacity # Add an entry (key, value) to hashTable[index] self.table[bucketIndex].append([key, value]) self.size += 1 # Increase size # Remove the entry for the specified key def remove(self, key): bucketIndex = hash(key) % self.capacity # Remove the first entry that matches the key from a bucket if len(self.table[bucketIndex]) > 0: bucket = self.table[bucketIndex] for entry in bucket: if entry[0] == key: bucket.remove(entry) self.size -= 1 # Decrease size break # Remove just one entry that matches the key # Return true if the specified key is in the map def containsKey(self, key): if self.get(key) != None: return True else: return False # Return true if this map contains the specified value def containsValue(self, value): for i in range(self.capacity): if len(self.table[i]) > 0: bucket = self.table[i] for entry in bucket: if entry[1] == value: return True return False # Return a set of entries in the map def items(self): entries = [] for i in range(self.capacity): if self.table[i] != None: bucket = self.table[i] for entry in bucket: entries.append(entry) return tuple(entries) # Return the first value that matches the specified key def get(self, key): bucketIndex = hash(key) % self.capacity if len(self.table[bucketIndex]) > 0: bucket = self.table[bucketIndex] for entry in bucket: if entry[0] == key: return entry[1] return None # Return all values for the specified key in this map def getAll(self, key): values = [] bucketIndex = hash(key) % self.capacity if len(self.table[bucketIndex]) > 0: bucket = self.table[bucketIndex] for entry in bucket: if entry[0] == key: values.append(entry[1]) return tuple(values) # Return a set consisting of the keys in this map def keys(self): keys = [] for i in range(0, self.capacity): if len(self.table[i]) > 0: bucket = self.table[i] for entry in bucket: keys.append(entry[0]) return keys # Return a set consisting of the values in this map def values(self): values = [] for i in range(self.capacity): if len(self.table[i]) > 0: bucket = self.table[i] for entry in bucket: values.append(entry[1]) return values # Remove all of the entries from this map def clear(self): self.size = 0 # Reset map size self.table = [] # Reset map for i in range(self.capacity): self.table.append([]) # Return the number of mappings in this map def getSize(self): return self.size # Return true if this map contains no entries def isEmpty(self): return size == 0 # Rehash the map def rehash(self): temp = self.items() # Get entries self.capacity *= 2 # Double capacity self.table = [] # Create a new hash table self.size = 0 # Clear size for i in range(self.capacity): self.table.append([]) for entry in temp: self.put(entry[0], entry[1]) # Store to new table # Return the entries as a string def toString(self): return str(self.items()) # Return a string representation for this map def setLoadFactorThreshold(self, threshold): self.loadFactorThreshold = threshold # Return the hash table as a string def getTable(self): return str(self.table) def hash(astring, tablesize): sum = 0 for pos in range(len(astring)): sum = sum + ord(astring[pos]) return sum%tablesize``` ichabod801 Bunny Rabbit Posts: 4,231 Threads: 94 Joined: Sep 2016 Reputation: 271 Likes received: 1262 #2 Aug-03-2019, 01:04 PM I'm assuming you know what a hash table is. Open addressing keeps everything on the hash table. Quadratic probing is a way to deal with hash collisions. Note that you are using hash % table size, that reduces the range of possible hashes drastically, so you will often have two different hashes trying to store in the same spot on the table. That's a hash collision. Quadratic probing means you keep trying new hashes (probing) by adding n**2 to the hash (quadratic). So if hash is taken, you try hash + 1, hash + 4, hash + 9, and so on until you find an open slot. This page has some discussion of the issues and how to implement them. jefsummers likes this post Craig "Ichabod" O'Brien - xenomind.com I wish you happiness. Recommended Tutorials: BBCode, functions, classes, text adventures « Next Oldest | Next Newest »

Top Page

Forum Jump:

Users browsing this thread: 1 Guest(s)