Hash Map Flashcards
Is a Hash Map and Hash Table the same?
Yes each language has their own implementation of a Hash Table.
HashMap in Java
Object in JavaScript
Dictionary in Python
How does the hash table (also known as hash map) data structure map keys to values?
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.
Is a Hash Map ordered?
No a hash map is unordered
What is the role of equals() and hashCode() methods in a hash map?
** do this apparently its important **
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”);
Emer will be overwritten to become Maisie for the key 2 because we cannot have duplicate keys
Is the order of a HashMap guaranteed?
No a HashMap is unordered
Can you have null value and key in a Hash Map?
Yes, but no real world use case
How do you get a value for a given key from a Hash Map<Integer, String>?
String value = map.get(key);
You pass the key to the get function and this will return the value for that key
Describe the map interface in Java?
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
When do we use Concurrent Hash Map?
We use Concurrent Hash Map in multi threaded environments
How do you remove an element from a HashMap?
map.remove(key)
Is a TreeMap ordered?
Yes entries are sorted based on their natural ordering ie., ascending / alphabetical
Can we define our own rule for ordering a Tree Map?
Yes by using a comparator during the construction of the TreeMap
TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder())
Give 3 examples of what a TreeMap is useful for?
- Find lowest
- Find highest
- Find all keys less than or greater than a certain value
Describe the principle of the red black tree?
- Guarantees all entries will be sorted and predictable order
(root, left always less than root of node, right always greater than or equal too) - Self balancing binary search tree
(guarantees Search, get, put, remove the logarithmic time)
Are Hash Maps or Tree Maps synchronized?
No
Is the order of a TreeMap guaranteed?
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.
How do we check if a key exists in a map?
map.containsKey(key);
O(1) time because unique key
How do we check if a value exists in a map?
map.containsValue(value)
O(n) time because you have to check each value for the keys until you find it
What are 4 examples of implementations of the Map interface in Java?
HashMap
Concurrent HashMap
Tree Map
Linked HashMap
How do you iterate over the keys of a hash map?
for(int i : map.keySet()){
…
}
Can you store null keys and null values in a Hash Map?
Yes
Can a HashMap contain duplicate keys?
No
What are the 3 collection views a map provides?
A set of keys
A collection of values
A set of key-value mappings
How do you iterate over all of the entries in a map?
for(Map.Entry e : map.entrySet()){
System.out.println( e.getValue() + “ “ + e.getKey();
}
Describe the internal implementation of a hash map?
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
How do you get the hash of a String?
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
When may a collision occur?
When 2 or more distinct keys are mapped to the same index in memory
Explain how there may be a collision if:
Size of internal array = 5
map.put(6, “A”)
map.put(11, “C”)
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
What are 4 techniques to resolve collisions?
Chaining
Linear probing
Quadratic probing
Double hashing
Describe chaining?
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
What is open addressing?
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
What is Linear probing?
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
What is quadratic probing?
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
What is double hashing?
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
