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

  dictionary set

  list

  second hashing algorithm

  hash value

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

  smaller set of values

  larger set of values

  similar decimal value (usually one more or one less)

  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:

  linked lists and arrays

  graphs and binary trees

  graphs and tables

  ordinary lists and radix trees

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

  create IP addresses and DNS tables

  decrypt any password in the world

  create graphs and insert nodes

   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

  4

  2

 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.

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

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

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

  They are all correct

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

  2

  1

  3

  4

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

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

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

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

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

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

  hash algorithmic pointing

  open addressing

  semi-hash addressing

  direct addressing

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

  coping

  cloitering

  clustering

  cluttering

 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.

  chaining

  clipping

  carting

  cpu-ing

 13. Ideally, a hashing algorithm should:

  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)

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

 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

  secondary clustering

  collision

  hash table

  hash function

 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

  collision

  hash function

  hash table

 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

  perfect hash function

  non-collision 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

  post-collision unhashing

  poshashing

  rehashing

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

  quadratic probing

  linear probing

  positional hashing

  rehashing

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

  clustering

  collising

  chaining

  rehashing

 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. 

  index / a key / index / chaining

  key / an index / collision / secondary hashing

  hash value / a key /index / closed addressing

  key / an index / key / chaining

 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 _______________________________

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

  determined by a new hashing algorithm

  that starts at 0 and ends at 10

  randomly assigned to the value

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

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

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

  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

 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'] 

  1

  2

  b

  3