Glossary: Data Structures and Algorithms in Java

average case

The cost you can expect in typical use, as opposed to the worst case. HashMap lookups are O(1) in the average case because collisions are rare.