hash table

Question 1

describe operation of adding key-val pair

Answer 1

hash(key) to get hash index
insert & rec key into hash table at hash index

Question 2

hash collision def

Answer 2

when diff keys have same hash index

Question 3

good hash function (hint: data, key, hash values)

Answer 3

• must use all input data
• uniformly distributes hash vals across entire set of possible hash values
• small difference in data causes a large difference in hash values
  OR
  generates very different hash values for similar (but non-identical) keys

Question 4

conflict resolution (open addressing)

Answer 4

• rehashing function will be called continuously until diff/new location found
• key-value pair will be stored at diff/new location
• lookups for keys should check subsequent locations if first key does not match

Question 5

conflict resolution (closed addressing)

Answer 5

• linked list can be instantiated at each array position
• key-value pairs are stored in linked list at each hash position
• lookup for keys done by walking through the linked list, checking for matching key

Question 6

application: why hash table can’t be a stack

Answer 6

• hash table does not remember order of insertion
• each item is hashed to a location that is unique to the index & not in running order

Question 7

advantage of hash table

Answer 7

time complexity O(1), constant time access as input data grows

(assuming hash collisions x occur v often, mention it esp if prev part of qn talked abt it)

Question 8

if hash table size n, exp how >n entries wld be stored in hash table

Answer 8

• the current hash table is unable to do so. :. a new hash table w larger capacity has to be created
• current entries have to be extracted, rehashed w the new size & inserted into the new hash table

Question 9

hash table vs bst

Answer 9

(context: 2023 nyjc prelim 3cii, prev parts mentioned unbalanced tree + hash collision :. need mention in final eval)

• for a large variety of keys, the % of hash collisions wld incr → collision resolution cld incr t complexity of inserting frm O(1) to O(n)
• while for BST, t complexity is O(logn) but can worsen till O(n) if tree is maximally unbalanced whr it can undergo rebalancing. :. given t complexity comparison, BST more suitable