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

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

graphs and binary trees

graphs and tables

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?

2

1

3

4

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

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

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.

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