Hashing

Question 1

What is the general idea of a hash table?

Answer 1

To hash/map an unordered list of entries to a specific position in an array

Question 2

How does a hash table improve the time of the insert, delete and lookup methods?

Answer 2

Gives them a O(1) worst case complexity. It will always be O(1) if there are no collisions

Question 3

What is the main disadvantage of a hash table?

Answer 3

that some positions will be null so spaces will arise which makes the methods more complex

Question 4

What is the table size abbreviated as?

Answer 4

TS which is the number of buckets

Question 5

What is the hash function?

Answer 5

The operations done to the key to yield it’s respective index value

Question 6

When does a collision arise

Answer 6

When the hash function gives the same index as another key

Question 7

How can the problem of collisions be solved?

Answer 7

Have each array point to another data structure(embedded DS)

Question 8

How do the embedded DS effect the total time complexity?

Answer 8

balanced tree: O(logN)

list: O(N)

Question 9

What tradeoff exists when choosing a TS?

Answer 9

Amount of space and the number of collisions

Question 10

What methods can a hash function implement to spread out keys?

Answer 10

multiply some or all values by a constant

Question 11

What is the problem with multiplying keys by a constant?

Answer 11

array overflow

Question 12

What is the problem with adding properties together to get the index?

Answer 12

permutations

Question 13

How is hashing done?

Answer 13

by performing operation(s) on the key to get an index value

Question 14

What is each element being hashed called?

Answer 14

A bucket. The index corresponding to it is the bucket index

Question 15

When does the number of items not correspond with the number of buckets?

Answer 15

When collisions occur

Question 16

What is the most important attribute when choosing a key?

Answer 16

uniqueness

Question 17

What is the most important attribute when choosing a hash function?

Answer 17

To get an even spread across the buckets/indeices a..b in other words no collisions

Question 18

What is the most important attribute when choosing a TS?

Answer 18

Preferably a table size just above the number of items i.e get the load function as close to one as possible

Question 19

What common operation is done on the bucket?

Answer 19

modulo

Question 20

If the TS is 50 then what is the modulo hash function?

Answer 20

H(key) = key % 50

Question 21

What does a perfect hash function accomplish?

Answer 21

avoids all collisions

Question 22

What is wrong with the modulus hash function h(k) = k % 1000, and a table size 20000?

Answer 22

Collisions are likely since the function only hashes to the first 1000 indices

Question 23

What does mid square hash function do?

Answer 23

1. )key^2

2. )modulus of middle n digits by the table size

Question 24

What is the load factor

Answer 24

The number of entries/TS

Question 25

What is a trivial hash function and when is it appropriate?

Answer 25

When the actual keys are used as the index value. This is usually done when the data is small enough

Question 26

How can hash functions be implemented in java?

Answer 26

overriding the equals/hash code

Question 27

What does the common hash method known as extraction do?

Answer 27

separate the digits of the key

Question 28

What does the common hash method known as weighting do?

Answer 28

Multiplies extracted digits by a constant

Question 29

What does the common hash method known as folding do?

Answer 29

combines the extracted/weighted digits into one value