Hashing, Hash Tables and Hashing function

Question 1

Another name for a hashing function?

Answer 1

hashing algorithm

Question 2

What is a hashing function?

Answer 2

A set of rules which is applied to a key field of the data to point to an address or location within a hash table (hash value).

Question 3

What is a common hashing algorithm?

Answer 3

divide key by the number of cells within a table and take the remainder as the address

Question 4

What is the purpose of a hashing algorithm and a hash table?

Answer 4

To create an index for the data by transforming the key fields into addresses. It is done to allow quick lookup, deletion or insertion of data.

Question 5

What is the problem we often experience with a hashing algorithm? What is this called?

Answer 5

The hashed value is equal to a cell location which is already taken. This is called a synonym

Question 6

What is the name of a situation where two record keys point to the same address or location within a hash table?

Answer 6

a collision

Question 7

What do we usually do to overcome the collision?

Answer 7

We place the item at the next free space within the hash table

Question 8

What is a hash table?

Answer 8

a collection of items set out in a way which allows quick access. It is 2d , with one dimension containing the data and the other the key (hashed one)

Question 9

A hash table is used to…..

Answer 9

to access data in a random way, just like an array

Question 10

Can hashing be applied to strings?

Answer 10

Yes by searching up the ASCII values of the alphanumeric data

Question 11

How is a hash table usually implemented?

Answer 11

An array or a list

Question 12

What makes a good hashing function?

Answer 12

one that tries to avoid getting duplicate data and causing collisions, however this is unavoidable it can be reduced

Question 13

What does a hash table store?

Answer 13

keys using hash values as an index

Question 14

Does a hashing function always return the same hashed value for the same keys?

Answer 14

YES, this is because later we will be able to find the location of the key within the hash table

Question 15

What does storing key values in the next free space come to?

Answer 15

clustering

this increases the likelihood of collisions

Question 16

How can we deal with clustering?

Answer 16

combining a hash table with a linked list which will be linked to a hash value within hash table and store keys that have overflown

Question 17

How can we avoid having clustering and collisions?

Answer 17

by having a good hashing algorithm

Question 18

How do we search for an item within a hash table?

Answer 18

• apply hashing algorithm to the key field of the item
• examine resulting cell
• if the item is there return it
• if the cell is empty the item is not in the table
• if there is another item at this index then keep moving forward until a free cell is found or the item you’re looking for is found

Question 19

What will an efficient hashing algorithm do well?

Answer 19

generate the least collisions

Question 20

What is a folding method?

Answer 20

process of creating a hash value. The key is split into equal size clusters and these are added together. If the resulting address is exceeding the maximum capacity of the table then the address is divided by a 100.

Question 21

The fuller the hash table becomes the more likely….

Answer 21

collisions will occur, this needs to be taken into account when designing a hashing algorithm and deciding on table size

Question 22

What is rehashing?

Answer 22

process of finding the next empty slot when a collision has occurred. It can loop round to the beginning of the table if the end has been reached. This can be amended to e.g. check every 3 spaces

Question 23

What are the primary uses of hashing and hash tables?

Answer 23

• to provide efficient lookup
• encrypted passwords, PINs, etc.
• used to implement a dictionary

Question 24

When we assign a key to the next free cell what is this called?

Answer 24

linear probing , this creates clustering as the hashed index is not randomly distributed

Question 25

What is this called when we implement a linked list which has a hash table index pointing to it. This linked list contains the data.

Answer 25

separate chaining