Week 11

• questions on the lab?
• Today, we cover maps and hash maps.
• For reference, let's take a quick look at name/value pairs for a mainframe OS
  • What is a name/value pair?
  • perhaps a simpler construct: a dictionary!
• lecture notes
• map code project

• Quick Summary from Tuesday's lecture on hash maps, or hash tables:

1. hash function is a way to mash up (my term) the name of something into a numerical key
2. the % operator is one way to lower/minimize the number of possible keys into a manageable number of buckets
3. we use buckets to hold one or more values based on the key
4. with a small range of keys, we can use an array data structure to O(1) access a bucket and we can represent a bucket with a linked list data structure.
5. if the number of keys available is too small for the number of values we are using, we approach O(n) accesses to get values (no difference from a linked list & no advantage to using a hash map!) so we may want to resize

• we will need the hashCode() method
• Today, and tomorrow, we will implement our own hash map data structure
  • Bluej project
  • UPDATE THE CODE WE STARTED TO DEVELOP IS HERE!
    • MyHashMap

• It is located here, be sure to pick up the MyHashMap java file above, I added it last evening.
  • moodle link
• The key, so to speak, of using the KeyValuePair is to remember to use the generics: <KeyValuePair<K,V»

Check out the author page too!