Hash Map

Question 1

Is a Hash Map and Hash Table the same?

Answer 1

Yes each language has their own implementation of a Hash Table.

HashMap in Java
Object in JavaScript
Dictionary in Python

Question 2

How does the hash table (also known as hash map) data structure map keys to values?

Answer 2

A hash table uses the hash function

The hash function is passed a key and uses the hash code and buckets to work out the index location of the value:

index = hashcode % capacity

The hash function is designed to minimize collisions, which occur when two different keys produce the same index.

The hash function is deterministic which means it should always produce the same index for a given key

When collisions occur, the hash table uses a collision resolution (ie., chaining, linear or quadratic probing, douvle hashing) strategy to store both values at the same index or to find a new index for one of the values.

Question 3

Is a Hash Map ordered?

Answer 3

No a hash map is unordered

Question 4

What is the role of equals() and hashCode() methods in a hash map?

Answer 4

** do this apparently its important **

Question 5

What happens if you have do this:

HashMap<Integer, String> m = new HashMap<>();
m.put(1, “Kieran”);
m.put(2, “Emer”);
m.put(2, “Maisie”);

Answer 5

Emer will be overwritten to become Maisie for the key 2 because we cannot have duplicate keys

Question 6

Is the order of a HashMap guaranteed?

Answer 6

No a HashMap is unordered

Question 7

Can you have null value and key in a Hash Map?

Answer 7

Yes, but no real world use case

Question 8

How do you get a value for a given key from a Hash Map<Integer, String>?

Answer 8

String value = map.get(key);

You pass the key to the get function and this will return the value for that key

Question 9

Describe the map interface in Java?

Answer 9

The map interface is a generic interface that is a contract that declares what implementations need to do to get and update key, value pairs

Question 10

When do we use Concurrent Hash Map?

Answer 10

We use Concurrent Hash Map in multi threaded environments

Question 11

How do you remove an element from a HashMap?

Answer 11

map.remove(key)

Question 12

Is a TreeMap ordered?

Answer 12

Yes entries are sorted based on their natural ordering ie., ascending / alphabetical

Question 13

Can we define our own rule for ordering a Tree Map?

Answer 13

Yes by using a comparator during the construction of the TreeMap

TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder())

Question 14

Give 3 examples of what a TreeMap is useful for?

Answer 14

1. Find lowest
2. Find highest
3. Find all keys less than or greater than a certain value

Question 15

Describe the principle of the red black tree?

Answer 15

1. Guarantees all entries will be sorted and predictable order
   (root, left always less than root of node, right always greater than or equal too)
2. Self balancing binary search tree
   (guarantees Search, get, put, remove the logarithmic time)

Question 16

Are Hash Maps or Tree Maps synchronized?

Answer 16

No

Question 17

Is the order of a TreeMap guaranteed?

Answer 17

Yes is guaranteed to be sorted based on the natural order of its keys or according to a Comparator provided at the time of creation.

Question 18

How do we check if a key exists in a map?

Answer 18

map.containsKey(key);

O(1) time because unique key

Question 19

How do we check if a value exists in a map?

Answer 19

map.containsValue(value)

O(n) time because you have to check each value for the keys until you find it

Question 20

What are 4 examples of implementations of the Map interface in Java?

Answer 20

HashMap
Concurrent HashMap
Tree Map
Linked HashMap

Question 21

How do you iterate over the keys of a hash map?

Answer 21

for(int i : map.keySet()){
…
}

Question 22

Can you store null keys and null values in a Hash Map?

Answer 22

Yes

Question 23

Can a HashMap contain duplicate keys?

Answer 23

No

Question 24

What are the 3 collection views a map provides?

Answer 24

A set of keys
A collection of values
A set of key-value mappings

Question 25

How do you iterate over all of the entries in a map?

Answer 25

for(Map.Entry e : map.entrySet()){
System.out.println( e.getValue() + “ “ + e.getKey();
}

Question 26

Describe the internal implementation of a hash map?

Answer 26

A key is passed to the hash function which maps the entry to an index of the imaginary internal array in memory and uses the modulus operator to reduce the index by the size of the internal array

index = key % size of internal array

Question 27

How do you get the hash of a String?

Answer 27

You get the numeric representation of all the characters

public static int hash(String k){
int hash = 0;
for(var ch : k.toCharArray()){
hash += ch;
return hash % 100;
}

Implicit casting to an Integer

Question 28

When may a collision occur?

Answer 28

When 2 or more distinct keys are mapped to the same index in memory

Question 29

Explain how there may be a collision if:
Size of internal array = 5
map.put(6, “A”)
map.put(11, “C”)

Answer 29

The remainder after dividing both of these by 5 is 1

6%5 = 1
11%5 = 1

So they are mapped to the same index and it is highly likely there will be a collision

Question 30

What are 4 techniques to resolve collisions?

Answer 30

Chaining
Linear probing
Quadratic probing
Double hashing

Question 31

Describe chaining?

Answer 31

Chaining is a technique to resolve collisions

Each bucket in the Hash Table is a Linked List that stores multiple values that have the same hashcode

When a collision occurs, add the element to the end of the Linked List

To find a value, traverse the Linked List

Question 32

What is open addressing?

Answer 32

Open addressing inserts elements in the next available slot in the hash table (instead of using a data structure)

3 types of open addressing are:
Linear probing
Quadratic probing
Double hashing

Question 33

What is Linear probing?

Answer 33

Linear probing probes successive slots in a hash table until an empty slot is found by incrementing the index by 1 each time

(hash1 + i) % internal array size

We need to reduce by the size of the internal array to make sure the index falls within the size of the array

Question 34

What is quadratic probing?

Answer 34

Quadratic probing solves the clustering problem we get with linear probing because getting the squared value, instead of the next value each time means the values are more spread out

(hash1 + i^2) % internal array size

Question 35

What is double hashing?

Answer 35

Double hashing uses 2 hash functions instead of 1 to determine the index of a given key.

Hash1: determines the initial index
Hash2: determines the “step size” added to the initial index to find the next available index

This process is repeated until an empty index is found

(hash1(key) + i*hash2(key)) % internal array size

hash2(key) = prime - (key%prime)

^ hash2 is an example of a common 2nd hash function, the prime number must be smaller than the size of our internal array