Often you need to remember something about each value, such as how many times it appeared or where it was last seen. A HashMap stores key to value pairs with O(1) average lookup, so counting frequencies takes one pass. Reach for it when you need a count, an index or any data attached to each key. If you only need to know whether a value exists, a HashSet is simpler, and if you need keys in sorted order, use a TreeMap.