Preview

13 - Hash tables

 1. Read the definition below to recap on Hash tables. What two simpler data structures do hash tables incorporate useful features from?
A Hash table is a beautiful data structure. It is basically a key value look up. 
You are given a key, you can associate a value with it, for very very quick look ups.
The key as well as the value can be any kind of data structure. A string is usually 
used. Hash tables are used when speedy insertion, deletion and look up of 
elements is priority. Putting it very simply, it is useful to remember that 
HASHING is like HOVIS bread because it incorporates the best of both worlds!
They incorporate the useful features of the following two simpler 
data structures, namely the ____________ and the _____________

  Graph / Stack

  Array / Linked List

  Stack / Queue

  Stack / Binary Tree

 2. Look at the diagram below. What goes into the hash function, in this example, and what comes out?
hashfunction_picture_to_delete1.png

  'key' goes in and a 'modulo function' comes out

  'key' goes in and a 'hash value' comes out

  'mod' goes in and a 'key' comes out

  'hash value' goes in and a 'key' comes out

 3. The below example demonstrates a common problem that programmers will get when working with hash tables. What is it called?
uploads/c_hash_table.jpg

  duplication

  cloitering

  collision

  clipping

 4. Ideally, a good hash function would not allow too many duplicate values (collisions), as this could lead to 'clustering'. One way of resolving this however, is to use ______ for certain indexes.

  overflows

  USB drives

  extra collisions

  queues

 5. _______ allows many items to exist at the same location in the hash table. When collisions happen, the item is still placed in the proper slot of the hash table. As more and more items hash to the same location, the difficulty of searching for the item i

  Chaining / Increases

  Collisioning / Increases

  Clipping / Increases

  Chaining / Decreases

 6. Which of the following statements is true (regarding a good hash table)
a) Prevent or allow for a low chance of collision. (i.e. different inputs giving the 
same output)
b)Be slow to calculate to prevent the occurence of clustering or chaining
c)Be quick to calculate, especially if lots of files need to be hashed. It needs to 
be quicker than a bitwise comparison to make it worthwhile. 
d)Provide a smaller output than input, which would mean it would be quicker to 
compare hashes than the original data. 

  a,c,d

  a and c

  a,b,c

  a and d

 7. Can you map the statements a - f below to their respective definitions?
a) These are tables which can be searched for an item in O(1) time using a hash 
function to form an address from the key
b) This is a function which, when applied to the key, produces an integer which 
can be used as an address in a hash table
c) When a hash function maps two different keys to the same table address, 
this is said to occur.
d)__________is the general name for the process of looking for another slot after 
a collision. For example. Rehash(pos) = (pos +1)%size_of_table.
e)This is a simple re-hashing scheme in which the next slot in the 
table is checked on a collision
f) A ___________ hash function is a function which, when applied to all the 
members of the set of items to be stored in a hash table, produces a 
unique set of integers within some suitable range. 

  Hash table / Hash Function / Collision / Rehashing / Linear Probing / Perfect

  Hash Cluster / Hash table / Collision / Reclustering / Linear Probation / Pliable

  Hash Function / Hash table / Clustering / Reclustering / Linear Probing / Pending

  Stack Table / Hash Function / Collision / Hashingagain / Linear Probation / Pointed

 8. Assume that a hash table has been used to implement a dictionary. The hashing algorithm that has been used is Catalogue Number MOD 100. What value is returned by the hashing function when it is applied to the catalogue number 1052?

  10

  52

  1

  0

 9. The following description (from OCR exam board A level example) describes how a value is stored in a hash table. Fill in the blanks.
Hashing algorithm is applied to the ____;
The result is an ______ of where to store the value in an array;
It is possible that the hashing algorithm might generate the same key
for two different values (this is called a _________); in which case a
collision handling method e.g. c_________ is used.

  index / key / chaining / collision

  key / index / collision / chaining

  key / MOD value / collision / chaining

  hash table / key / collision / cluttering

 10. Which statement could be a description of rehashing (taken from the markscheme of the OCR Computing A Level exam board)
a) A larger hash table is created; Each value in the existing table is inserted 
into the new table -in a position determined by a new hashing algorithm; 

b) A smaller hash table is created; Each value in the existing table is deleted
from the first table and a new hashing algorithm is applied to the new table indexes; 

  Both a and b are correct

  b is correct

  Both a and b are incorrect

  a is correct