Choosing a Username

When you sign up for a website, you are usually asked to pick a username. A username can belong to only one person, so before the site lets you have the one you typed, it checks whether someone already took it. If the username is free, you get it; if not, you are asked to try another. The site is keeping a collection of unique usernames.

We already know enough to build this. We can keep the taken usernames in an ArrayList. Each time someone registers, we scan the list to see whether the username is already there. If it is not, we add it; if it is, we reject the registration. This works, but our code is responsible for keeping the usernames unique. Every place in our program that adds a username must enforce the uniqueness constraint.

With the restricted access data structures like stack, we restricted how we reach the data. We allowed access only at the ends, and that restriction gave us a guarantee we did not have to enforce by hand. We can do the same thing here, but this time we restrict what the collection may hold rather than how we reach it. We want a data structure that does not store the same element twice. Then uniqueness is not a rule every caller has to remember. It is built into the data structure.

The need for uniqueness comes up in other scenarios as well. For example, email addresses on a mailing list should be unique, otherwise a message might be sent multiple times to the same person. Counting views of an Instagram post or TikTok story requires that each view be counted only once otherwise someone can write a simple script to artificially inflate the view count. Tags applied to products on an e-commerce site should also be unique.

In this chapter, we will study set, a data structure that holds a collection of distinct elements. The name comes from mathematics, where a set is an unordered collection of distinct objects.