Maps, Hash Tables, and Skip Lists

Maps, Hash Tables, and Skip Lists

1. Maps

   • It's an abstract data type designed to efficiently store and retrieve values based upon a uniquely identifying search key for each.
   • Also known as associative arrays
   • Map ADT
     • size()
     • isEmpty()
     • get(k)
     • put(k,v)
     • remove(k)
     • keySet()
     • values()
     • entrySet()
   • Applications
     • Counting word frequencies
     • University's information system. Takes the student ID as the key to map his records
     • The domain-name system (DNS) maps a host name, such as www.wiley.com, to an Internet-Protocol (IP) address, such as 208.215.179.146.