Hashing

Question 1

Define ‘lossy compression’

Answer 1

Compression where non-essential data is removed to free up space, for example:

Different shades of the same colour in an image
Frequencies of sound outside the human hearing range

Question 2

Define ‘lossless compression’

Answer 2

Compression where the computer analyses patterns in the data, and summarises it in a shorter format - without removing any information.

Question 3

How does lossy compression work in images?

Answer 3

Different shades of certain colours are removed
Picture is reconstructed with less coloured pixels

Question 4

How does lossy compression occur in sounds?

Answer 4

Sounds with frequencies outside the range of human hearing are removed from the file
Quieter notes playing at the same time as louder notes are also removed from the file

Question 5

What is the difference between lossy and lossless types?

Answer 5

Lossy: Is most effective at reducing file size

Lossless: Maintains the information of the original data

Question 6

What is lossy compression typically used for?

Answer 6

Audio files and pictures

Question 7

State the effect of using lossy compression on pictures and audio

Answer 7

Pictures files: Would lose their original resolution, as there are less individual colours to make up the picture

Sound files: Would lose their sharpness

Question 8

State one method of lossless compression and where it is used

Answer 8

Run Length Encoding: Used in pictures and sound files.

Dictionary Compression: Used in word files

Question 9

Explain how Dictionary Compression works:

Answer 9

Repeating words / characters are added to a dictionary, and assigned a [shorter] binary value

Question 10

Explain what state a data set must be in in order to use binary search

Answer 10

Data must be sorted in either ascending or descending order

Question 11

What is a hashing table?

Answer 11

A data structure which will find any record in a dataset instantly

Question 12

What is hashing?

Answer 12

Organising large data sets so each record has its own unique address

Records are organised via hashing algorithms/hash functions

Question 13

Define ‘collision’

Answer 13

When an algorithm generates the same address for primary keys

Question 14

State the simplest method for dealing with collisions

Answer 14

Putting the item in the next free slot in the table

Question 15

State one alternative method for dealing with collisions

Answer 15

Incrementing the ‘skip’ value by adding another number to find a free space

Question 16

Define ‘load factor’

Answer 16

Measure of how full up the table is

Question 17

What is the ideal load factor of a hashing table?

Answer 17

No more than 50%-70%

Question 18

State two other hashing algorithms

Answer 18

• The ‘mid-square’
• The ‘folding method’

Question 19

Explain how the ‘mid-square’ hashing algorithm works

Answer 19

• Square the number
• Extract digits
• Perform the mod (remainder) function to get an address

Question 20

Explain how the ‘folding’ hashing algorithm works

Answer 20

• Divide the item into equal-size pieces
• Add the pieces together
• Perform the mod (remainder) function to get an address

Question 21

How can we hash alphanumeric data?

Answer 21

Convert each character to its ASCII code, then applying a hashing algorithm

Question 22

What must happen if an item is to be deleted

Answer 22

Items to be deleted must be replaced with a dummy item/marker, e.g. the word ‘Deleted’