I have run across a number of cases where I have a Map where once I set it up, the keys never change (although the values against them do). I don’t necessarily know what the keys will be until I create the map but once I do they are fixed.
I was wondering, is there a way to take advantage of this fact to design a Map like data structure that retrieves values more efficiently than the standard implementations?
The class signature would roughly follow the Map interface and might look something like:
public class FixedKeyMap<K,V> {
// Takes in a list of keys for the map.
// These keys cannot be added to or removed from.
// All values are initially set to null.
public FixedKeyMap(List<K> keys) {}
// If the Key is valid, replace its value with this one.
// Otherwise do nothing or throw an exception.
public void put(K key,V value) {}
// If key is valid then get the value associated with it
// Otherwise return null or throw an exception.
public V get(K key) { }
// If key is valid then sets its value to null. Does not remove it.
// Otherwise, do nothing or throw an exception.
public void remove(K key) { }
// Sets all values to null but does not remove keys.
public void clear() {}
// Returns a set containing all of the keys.
public Set<K> keySet() { }
}
I looked at the HashMap source and it looks like you would be able to pull out a lot of code around load factors and capacities and simplify some of the other code because the size would be known at creation time.
Anyone have any thoughts on how such a thing might be designed to take advantage of the fact that the keys are all known up front? Could you get rid of the hashing function altogether?
I do recognize that this is a micro optimisation and may or may not be worth the effort for a given application but the question seemed interesting and so I thought I would ask if others had any ideas.
