Chapter 37 - Hash tables
No description yet. This curated deck is ready for daily study.
Card preview (24)
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