Arrays vs Hash Maps vs Sets

Choosing the right structure among arrays, hash maps, and hash sets based on access patterns and tradeoffs.

You need to repeatedly check whether specific integer values exist in a large, unordered collection, with frequent lookups by value. Which structure offers the best average-case performance for this task, and why?