Storing a Password

When you log into a website, you type your username and your password, and the site has to find the password it stored for that username and check it against what you typed. In the set chapter the site kept the taken usernames in a set, which was enough to tell if a username is available or already in use. A set cannot find the password.

We already know enough to build this. We could keep the usernames in one ArrayList and the passwords in a second, lining them up by position so that the password at index i belongs to the username at index i. To log someone in, we scan the username list for a match, note its index, and read the password at that same index in the other list. This works, but the two lists have to be kept aligned. Every registration must append to both, every removal must delete from both at the same index, and a single mismatch can corrupt the pairing for every entry after it.

With the set, we let the structure enforce the no-duplicates rule. Here we want a structure that stores each username together with its password, so the pairing is built in and looking up a password is one operation.

The same need shows up whenever we hold a collection of pairs and, given the first part of a pair, want the second: a contacts app pairing each name with a phone number; a gradebook pairing each student with a grade; a cache pairing each web address with the page fetched from it.

In this chapter, we will look at a data structure called a map. It holds a collection of key–value pairs and looks up the value for a given key. The name comes from mathematics, where a map is a function that pairs each input with exactly one output. In the same way, each key in a map has exactly one value. You may also see this structure called a dictionary, an associative array, or a symbol table.