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
