Chapter 37 - Hash tables

Question 1

Why are hash tables useful?

Answer 1

» Can quickly access data without having to look at all the records

Question 2

What does a hashing algorithm do?

Answer 2

» Divide the key by the number of available address and take the remainder as the address

Question 3

What happens when there is a synonym?

Answer 3

» When 2 pieces of data hash to the same address, this cause a collision

Question 4

What is the simplest way of dealing with a collision?

Answer 4

» Is to store the item in the next available space, assuming it is free

Question 5

What is a hash table?

Answer 5

» Abstract data structure where data is stored in an array format and enables access to structures that are not stored in a structured manner

Question 6

What is the purpose of a hash function?

Answer 6

» Generates an address in a table for the data that can calculate the position of an item in the table

Question 7

What is a collision?

Answer 7

» When a hashing algorithm maps 2 different keys to the same table address

Question 8

What is the mid-square method?

Answer 8

» Square the item
» Extract the middle 2 digits
» Mod the value by the table size to get an address

Question 9

What is the folding method?

Answer 9

» Divides the item into equal parts
» Add the pieces together
» Mod the value by the table size to get an address

Question 10

What is a dictionary?

Answer 10

» An abstract data type composed of a collection of pairs such that each possible key appears at most once in the collection

Question 11

How is it possible to hash a string?

Answer 11

» By using the ASCII code for each character
» Add the ASCII value for each character
» MOD the value by the table size

Question 12

What are the consequences of having a fuller hash table?

Answer 12

» More likely it is that there will be collision

Question 13

What is rehashing?

Answer 13

» 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

Question 14

What does each pair consist of in a dictionary?

Answer 14

» Key
» Value

Question 15

What are the 3 good features of a hashing function?

Answer 15

» Be calculated quickly
» Result in as few collisions as possible
» Use as little memory as possible

Question 16

What is linear probing?

Answer 16

» 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

Question 17

What is the disadvantage of linear probing?

Answer 17

» It prevents other items from being stored at their correct location in the hash table

Question 18

What is clustering?

Answer 18

» Several positions being filled around the common collision values

Question 19

What is the trade off in a hashing algorithm?

Answer 19

» Between the efficiency of the algorithm and the size of the hash table

Question 20

What is an alternative method of handling collisions ?

Hint - uses a dimensional array

Answer 20

» Uses 2D array

Question 21

What is chaining?

Answer 21

» The possibility of more than one item to be placed at the same position

Question 22

What is the purpose of an overflow table?

Answer 22

» Store the collisions in which items can be searched sequentially

Question 23

What are the common situations in which has tables can be used?

Answer 23

» File systems linking a file name
» Identifying the keywords in a programming language

Question 24

What are the 3 operations that are possible on a has table?

Answer 24

» Add
» Delete
» Retrieve - retrieves an item using its hash value

Question 25

What are the steps to add an item to a hash table?

Answer 25

» Calculate position of the item using a hashing function
» If the calculated position is empty, insert the item and stop

Question 26

What happens if the calculated position is not empty?

Answer 26

» 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

Question 27

What are the steps to remove an item from a hash table?

Answer 27

» Calculate position of the item using a hashing function
» If the calculated position contains the item to be deleted, delete it and stop

Question 28

What happens if the calculated position does not contain the item to be deleted?

Answer 28

» 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

Question 29

How can we traverse a hash table?

Answer 29

» It is very similar to how you add/ delete an item to a hash table