Hash Tables

Why hash tables matter

Many algorithmic problems repeatedly ask the same kind of question: “have we seen this value before?” or “what data is associated with this key?”. If we scan an array from the beginning every time, a single lookup can take O(n). A hash table organizes data so that lookup, insertion, and deletion take O(1) on average.

That speed comes from a simple idea: a key is transformed into a hash, and the hash helps us quickly choose the place where the record should be searched for. But there are several important steps between that idea and a reliable data structure — a good hash function, collision handling, and choosing correctly between storing key-value pairs and storing a set of values.

What this section covers

• Hash Table Basics. We will examine the general “key → hash → bucket” scheme and understand where fast data access comes from.
• Hash Functions. We will discuss the properties of a hash and why equal keys must be handled consistently.
• Collisions. We will see why different keys sometimes end up in the same place and how a hash table stays correct in that situation.
• Hash Map. You will learn to find a value quickly by its key and choose this structure for algorithmic problems.
• Hash Set. We will examine storing unique values and performing fast membership checks.
• Frequency Map. We will learn one of the most common techniques: counting how many times each value appears.
• Fast Lookup Patterns. We will combine the ideas from the section and see how extra memory can replace repeated linear searches with fast checks.

One structure, many algorithmic techniques

Set<Integer> seen = new HashSet<>();
seen.add(42);

boolean exists = seen.contains(42);

Here, checking whether a value exists looks almost like asking the data structure a direct question. In the following topics, we will examine why such a check can be fast and how the same idea powers maps, sets, frequency counting, and many lookup problems.