Hashing, Hash Tables and Hashing function Flashcards Preview

A Level Computer Science Data Structures > Hashing, Hash Tables and Hashing function > Flashcards

Flashcards in Hashing, Hash Tables and Hashing function Deck (25)
Loading flashcards...
1
Q

Another name for a hashing function?

A

hashing algorithm

2
Q

What is a hashing function?

A

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

3
Q

What is a common hashing algorithm?

A

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

4
Q

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

A

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.

5
Q

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

A

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

6
Q

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

A

a collision

7
Q

What do we usually do to overcome the collision?

A

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

8
Q

What is a hash table?

A

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)

9
Q

A hash table is used to…..

A

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

10
Q

Can hashing be applied to strings?

A

Yes by searching up the ASCII values of the alphanumeric data

11
Q

How is a hash table usually implemented?

A

An array or a list

12
Q

What makes a good hashing function?

A

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

13
Q

What does a hash table store?

A

keys using hash values as an index

14
Q

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

A

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

15
Q

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

A

clustering

this increases the likelihood of collisions

16
Q

How can we deal with clustering?

A

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

17
Q

How can we avoid having clustering and collisions?

A

by having a good hashing algorithm

18
Q

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

A
  • 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
19
Q

What will an efficient hashing algorithm do well?

A

generate the least collisions

20
Q

What is a folding method?

A

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.

21
Q

The fuller the hash table becomes the more likely….

A

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

22
Q

What is rehashing?

A

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

23
Q

What are the primary uses of hashing and hash tables?

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

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

A

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

25
Q

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.

A

separate chaining