Building on the application of object-oriented programming principles to the map abstract data type covered at Maps/OOP, this page will cover some of the general ideas and nuances of implementing a hash map in an object-oriented way.
Recap of map inheritance structure
To recap, here is how these classes are organized:
- Map is an interface class that defines the public interfaces that any Map data container must implement
- AbstractMap is an abstract class that does the following:
- Define a map item (utility) class
- This is designed to take a K,V key value pair
- Also defines four more classes:
- Two Iterators and two Iterables - the key and value Iterator and Iterable classes.
- The itemSet() method returns an iterator over the set of all MapItems
- itemSet() returns an iterator over MapItem types, so keySet() and valueSet() both utilize this and unwrap only the key or value from the MapItem object.
- We aren't defining itemSet anywhere in this class - just using it. Then we implement it as an abstract method, requiring concrete classes to implement it.
- itemSet must be defined in our concrete class
- This means that eventually our concrete class will have three total Iterators and three total Iterables - two Iterators and two Iterables defined in the abstract class, for the keys and values, and one Iterator and one Iterable defined in the concrete class, when we know more about how the actual hash map is being implemented under the hood.
More iterators vs iterables:
- Iterable just says, this thing can be used with for-each syntax (it has a specific way to return an iterator). It is part of the core language.
- Iterator has to be defined for each container.
- Don't forget to check for size!
- Especially if you are not wraapping someone else's iterator
Ordering of class declaration and undeclared class declarations
- I could not use MapItem class undefined in the Map interface (most generic of all)
- MapItem class was actually protected and lived in AbstractMap class
- Therefore, we had to hold off declaring an abstract MapItem iterator until the AbstractMap class, not the Map interface
Maps and DictionariesPart of Computer Science Notes
Series on Data Structures
Hash Maps/OOP · Hash Maps/Operations and Performance
Java implementations: SkipList
Flags · Template:MapsFlagBase · e