Chapter 37 - Hash tables Flashcards
Why are hash tables useful?
» Can quickly access data without having to look at all the records
What does a hashing algorithm do?
» Divide the key by the number of available address and take the remainder as the address
What happens when there is a synonym?
» When 2 pieces of data hash to the same address, this cause a collision
What is the simplest way of dealing with a collision?
» Is to store the item in the next available space, assuming it is free
What is a hash table?
» Abstract data structure where data is stored in an array format and enables access to structures that are not stored in a structured manner
What is the purpose of a hash function?
» Generates an address in a table for the data that can calculate the position of an item in the table
What is a collision?
» When a hashing algorithm maps 2 different keys to the same table address
What is the mid-square method?
» Square the item
» Extract the middle 2 digits
» Mod the value by the table size to get an address
What is the folding method?
» Divides the item into equal parts
» Add the pieces together
» Mod the value by the table size to get an address
What is a dictionary?
» An abstract data type composed of a collection of pairs such that each possible key appears at most once in the collection
How is it possible to hash a string?
» By using the ASCII code for each character
» Add the ASCII value for each character
» MOD the value by the table size
What are the consequences of having a fuller hash table?
» More likely it is that there will be collision
What is rehashing?
» Name given to the process of finding an empty slot when a collision has occurred
» Finding an alternative position for items in the hash table
What does each pair consist of in a dictionary?
» Key
» Value
What are the 3 good features of a hashing function?
» Be calculated quickly
» Result in as few collisions as possible
» Use as little memory as possible
What is linear probing?
» To find the item later that has been moved due to a collision
» The hashing function delivers the start position from which a linear search can then be applied until the item is found
What is the disadvantage of linear probing?
» It prevents other items from being stored at their correct location in the hash table
What is clustering?
» Several positions being filled around the common collision values
What is the trade off in a hashing algorithm?
» Between the efficiency of the algorithm and the size of the hash table
What is an alternative method of handling collisions ?
Hint - uses a dimensional array
» Uses 2D array
What is chaining?
» The possibility of more than one item to be placed at the same position
What is the purpose of an overflow table?
» Store the collisions in which items can be searched sequentially
What are the common situations in which has tables can be used?
» File systems linking a file name
» Identifying the keywords in a programming language
What are the 3 operations that are possible on a has table?
» Add
» Delete
» Retrieve - retrieves an item using its hash value
What are the steps to add an item to a hash table?
» Calculate position of the item using a hashing function
» If the calculated position is empty, insert the item and stop
What happens if the calculated position is not empty?
» Check the first position in the overflow table
» If position is empty, insert the item and stop
» Increment the position to check in the overflow table
» Repeat until item is inserted or the overflow table is found to be full
What are the steps to remove an item from a hash table?
» Calculate position of the item using a hashing function
» If the calculated position contains the item to be deleted, delete it and stop
What happens if the calculated position does not contain the item to be deleted?
» Check the first position in the overflow table
» If the position contains the item to be deleted, delete it and stop
» Increment position to check in the overflow table
» Repeat until the item is discovered, or the end of the overflow table is reached
How can we traverse a hash table?
» It is very similar to how you add/ delete an item to a hash table
