Maps, Hash Tables & Binary Search Trees

Question 1

What is a Map ADT?

Answer 1

A map models a collection of key-value entries that is searchable ‘by the key’
The main operations of a map are for searching, inserting and deleting items
Multiple entries with the same key are not allowed

Question 2

What is the difference between a Map and Priority queue?

Answer 2

Map - access any key
Priority Queue - access only the minimum key

Question 3

How does a map work as a doubly linked list?

Answer 3

Store the items of the map in a list S, in arbitrary order, as well as a size counter, so that getSize is O(1)

Question 4

What is the performance of a list-based Map?

Answer 4

put() - takes O(n) as you have to check if the key occurs in the map already
get and remove take O(n) time since in the worst case, you traverse the whole list

Question 5

What is a Hash Table and what are its time complexities for looking up keys, inserting and deleting them?

Answer 5

A CDT which is suitable for implementing maps
Convert each key into an index into a (big) array
Look-up, insertion and deletion of keys usually runs in O(1) time

Question 6

What is a hash function?

Answer 6

Maps keys of a given type to integers in a fixed interval [0, N-1]
Example - H(k) = k mod N
The integer h(k) is called the hash value of key k

Question 7

What does a hash table consist of?

Answer 7

A hash function (h)
Array (called table) of size N

Question 8

What is a compression function?

Answer 8

A compression function is the 2nd part of a hash function. The goal is to be applied directly on top of the hash function, to ensure the keys gets ‘dispersed’ in an ‘apparently random’ way.

Question 9

What is Separate Chaining?

Answer 9

Let each cell in the table point to a linked list of entries that map there e.g. if something collides with an entry that is already there, then it just gets added to the linked list

Question 10

What are the problems with Separate Chaining?

Answer 10

Requires additional memory outside of the table

Question 11

What is open addressing and what are its problems?

Answer 11

The colliding item is placed in a different cell of the table
Linear probing handles collisions by placing the next colliding item in the next available table cell
Each table cell inspected is referred to as a ‘probe’
Disadvantage - colliding items lump together, causing future collisions to cause a longer sequence of probes

Question 12

How do you delete an element from a hash table safely?

Answer 12

Use ‘lazy deletion’ - don’t mark the entry as a blank, but as a ‘deleted’ cell and fix the entries later

Question 13

What is double hashing?

Answer 13

Double hashing uses a secondary hash function d(k), which handles collisions by placing an item in the first available cell of the series.
For reference, linear probing is d(k) = 1 i.e. take the next available spot. If it doesn’t exist, then move yet 1 more space forward.
The table size N must be a prime to allow probing of all the cells

Question 14

What is the performance of hashing?

Answer 14

In the worst case, searches, insertion and removals on a hash table take O(n) time. Otherwise, normally O(1)
Reference - worst case occurs only when all keys collide

Question 15

What does ‘load factor’ mean?

Answer 15

This affects the performance of a hash table. It is a measure of how ‘full’ the array for the hash table is. In Java, the highest this is allowed to go is 75%, and then it gets re-hashed.

Question 16

What is re-hashing?

Answer 16

When the table gets too full, then ‘re-hash’. This creates a new, larger tables and new hash function, followed by transferring all the elements to the new table. This can be done in two ways:
All at once - O(n) amortised time
A few at a time - O(1) amortised time

Question 17

What are the differences between Hash Maps and Priority Queues?

Answer 17

Hash map does not use the ordering of keys e.g. does not implement min(). If you wish to do that, then it would take O(n) time
Priority Queue does not allow direct access to a key e.g. there is no easy way to do get(k), would have to walk through all the entries

Question 18

What is a binary search tree?

Answer 18

It is a binary tree storing key-value entries at its internal nodes and satisfying the following ‘search tree’ property:
Let u, v and w be any three nodes such that u is in the left subtree of v and w is in the right subtree of v. Then we must have key(u) < key(v) < key(w) (assuming no duplicate entries)

Question 19

How do you search within a binary search tree?

Answer 19

To search for key k, trace a downward path starting at the root. The next node visited depends on the outcome of the comparison of k with the key of the current node
If we reach a leaf, the key is not found and we return null

Question 20

How do you access the minimum key of a binary search tree?

Answer 20

Always go left. If sorted correctly, then that should be the smallest node

Question 21

How do you insert into a binary search tree?

Answer 21

Use a get(k) function. If the key has not been found, then insert the new key as a leaf node to the current node selected. If it is found, then replace the value found.

Question 22

How do you delete from a binary search tree a node with one child?

Answer 22

Remove the node, and then connect the child node to the parent of the removed node.

Question 23

How do you delete from a binary search tree a node with two children?

Answer 23

Find the internal node (w) that follows n in an inorder traversal (typically the next highest value)
Copy the key (w) into the node to be deleted.
Remove the original node w and its left child z (which if null, is fine, but if not, then follow procedure for deletion of one node)

Question 24

What is a balanced search tree?

Answer 24

A balanced search tree is when all depths have been filled.

Question 25

What is the time complexity of search, insertion and deletion for a balanced binary search tree?

Answer 25

All of the methods are O(log n)

Question 26

What is the performance of a binary search tree?

Answer 26

Space used is O(n)
Methods find, insert and remove take O(height)
Height h is O(n) in worst case, and O(log n) in best case

Question 27

What is self-balancing?

Answer 27

Constantly re-structure the trees
Keep the trees height balanced so that the height is logarithmic in the size
Performance of self-balancing is always logarithmic

Question 28

What is the issue with self-balancing?

Answer 28

Could make trees balanced using a ‘total rebuild’ but that would result in O(n)
Counter this issue by looking at the path to some recently changed node, not the entire tree, and fixing that.