Preview

10 - Hash Table

 1. Hashing involves applying a hashing algorithm to a data item, known as the hashing key, to create a ____________
Note: The following presentation may be useful and is available from www.teachingcomputing.com

  list

  dictionary set

  hash value

  second hashing algorithm

 2. Hashing algorithms take a large range of values (such as all possible strings or all possible files) and map them onto a _______________________ (such as a 128 bit number).

  similar decimal value (usually one more or one less)

  larger set of values

  smaller set of values

  set of hexadecimal values

 3. Hashing is often compared to providing the 'best of both worlds', in this case, the best of the features of both:

  graphs and tables

  linked lists and arrays

  ordinary lists and radix trees

  graphs and binary trees

 4. Hashing has two main applications. Hashed values can be used to speed data retrieval, and can be used to ________________________

  create graphs and insert nodes

  create IP addresses and DNS tables

  decrypt any password in the world

   check the validity of data

 5. In the following example, a hashing value is produced using MOD in the hashing algorithm. What is 60 MOD 6?
hashKey MOD 6


Hash Key	Hashing Algorithm	Hashing Value
======================================================
12345		12345 MOD 6		3
67564		67564 MOD 6		4
34237		34237 MOD 6		1
23423		23423 MOD 6		5
00332		00332 MOD 6		2

  3

  0

  2

  4

 6. The following excerpt summarises some rules for creating a good hash function. Which rule, if any, is incorrect?
Rules for a good hash function
==================================
1. Use only the data being hashed

2. Use all of the data being hashed

3. Be deterministic (predictable, not random)

4. Uniformly distribute data (a big range of hash codes is good)

5. Generate very similar hash codes for similar data.

  Only rule 3 is incorrect - it is better to use random data for better results

  They are all correct

  Only rule 5 is incorrect - you should generate different hash codes for similar data

  All of the rules are incorrect and do not apply in any way to creating a hash function

 7. The following shows the creation of a hash table to store scores. What number would go in the missing blanks?
usingahashtablequestion1.png

  4

  2

  3

  1

 8. Analyse the image below and select a statement from the options below that best describe what is happening.
usingahashtablequestion2.png

  The term for this is 'competition' as both hash values compete for one cell position.

  Both names generate the same hash value and the second one simply goes into the second slot.

  There's a problem - both names generate a hash value of 1 causing what is termed a 'collision'

  Mr Goose's hash value would be changed to 1+1 to give 2, and this could then be put in the next slot.

 9. What is one method for resolving the problem caused by collision?

  hash algorithmic pointing

  direct addressing

  semi-hash addressing

  open addressing

 10. Resolving collision can lead to ______________, and ____________ can be resolved by using an 'overflow'.

  cluttering

  cloitering

  clustering

  coping

 11. A good hash function would ideally have thousands, or even millions, of duplicate values.

  TRUE

  FALSE

 12. Another resolution to collision is _________. This allows each slot to hold a reference to a collection (or chain) of items.

  carting

  cpu-ing

  chaining

  clipping

 13. Ideally, a hashing algorithm should:

  provide a bigger output than input (to allow for more careful comparisons)

  either encrypt or delete all outputs on generation, to ensure the maximum security

  provide a completely identical output to input (to ensure consistency)

  provide a smaller output than input (to allow for faster comparing of hashes than the original data)

 14. 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

  collision

  hash table

  hash function

  secondary clustering

 15. This is a function which, when applied to the key, produces an integer which can be used as an address in a hash table.

  secondary clustering

  hash function

  hash table

  collision

 16. These are collision sequences generated by addresses calculated with quadratic probing.
Note: Quadratic probing is an open addressing scheme in computer programming 
for resolving collisions in hash tables—whenan incoming data's hash value 
indicates it should be stored in an already-occupied slot or bucket

  secondary clustering

  hash function

  hash table

  collision

 17. This 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.

  primary hash function

  non-collision function

  perfect hash function

  unique collision function

 18. This is the process of searching for another slot after a collision.
For example: Rehash(pos) = (pos+1)% size_of_table

  positional hashing

  rehashing

  post-collision unhashing

  poshashing

 19. This is a simple re-hashing scheme in which the next slot in the table is checked on a collision.

  positional hashing

  quadratic probing

  linear probing

  rehashing

 20. What is the following excerpt describing?
The tendency for many adjacent slots to be filled when linear probing is used

  clustering

  rehashing

  collising

  chaining

 21. The following excerpt describes how a hash value is stored in a table. Fill in the blanks
How a hash value is stored
===========================

1. Hashing algorithm is applied to the _____

2. The result is  _____ of where to store the value
in an array

3. It is possible that the hashing algorithm might
generate the same _____ for two different values.

4. If the above occurs it is called a collision.

5. A collision handling method like open addressing or ________
is used. 

  key / an index / key / chaining

  index / a key / index / chaining

  key / an index / collision / secondary hashing

  hash value / a key /index / closed addressing

 22. In re-hashing it is often necessary to create a larger hash table.

  TRUE

  FALSE

 23. In re-hashing, each value in the existing table is inserted into the new table - in a position _______________________________

  determined by a new hashing algorithm

  that starts at 0 and goes up by +1 for each value

  randomly assigned to the value

  that starts at 0 and ends at 10

 24. A dictionary (e.g. in Python) is a ____________________________________________

  typical index structure which is identical to the structure of a variable

  type of linked list that has pointers and dynamic cells to hold data

  type of online book that stores paragraphs of information along with index numbers, keys, values and pairs

  data structure that contains a collection of key-value pairs where the value is accessed via the key

 25. In the following example, showing a Python dictionary at work, what would the output be?
>>> D['a'] = 1
>>> D['b'] = 2
>>> D['c'] = 3
>>> D
{'a': 1, 'c': 3, 'b': 2}


>>> D['b'] 

  b

  1

  2

  3