Part1 -
How do hashtables/HashMap work ?
At the heart of the hash table algorithm is a simple array of items; this is often simply called the hash table. Hash table algorithms calculate an index from the data item's key and use this index to place the data into the array. The implementation of this calculation is the hash function
What happens if two keys have the same hashCode ?
Often termed as hash collision , hashtable implementations have to deal with it. One of the ways and the most common way to deal with this situation is to maintain a list of values
for keys with the same hashCode. HashCode of the keys would result into the same value and hence point to the same index in the array, containing mulitple key-values.
Run a equals on the key and return the appropriate value back to the caller.
What happens if the two keys have the same equals value ?
Pretty obvious duplicate keys cannot be stored and hence the original key/value is retained and new one being added is rejected
When implementing a LRU cache which datastructure would one use ?
LinkedHashMap would be an obvious choise for a couple of reasons -
1. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
2. The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.
3. A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order)
How would one define a structural modification in a HashMap ?
A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.
How would one define a structural modification in a LinkedHashMap ?
A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered linked hash maps, affects iteration order.
In insertion-ordered linked hash maps, merely changing the value associated with a key that is already contained in the map is not a structural modification.
In access-ordered linked hash maps, merely querying the map with get is a structural modification.
Its important to understand structural modifications , since maps are not synchronized unlike a hashtable if a thread structurally modifies a map while another thread is iterating over the same there could be serious concurrency issues. Potentially resulting in ConcurrentModificationException
Please comment below with any interesting questions/discussions you might have come across with hashtables/maps
MORE STUFF-
