Hash Table Basics

date2026-07-14document_iddoc_6e5b2ec4e3a69f6ebc84b37f111e6b97descriptionハッシュを、値そのものを探すのでなく置き場所を素早く決める仕組みとして整理し、平均的に高速な探索がなぜ可能かを説明します。prerequisites計算量の基本 / データ構造ポータル / 配列の基本操作type講義statusactive

algorithmdata-structuresundergraduatelecture

data/lecture/information/algorithm/data-structures/data-structures-portal.lecture.n.md

1Introduction

This lecture explains how a hash table implements the dictionary ADT. For separate chaining, it relates the load factor to operation complexity.

2Dictionary ADT

The dictionary ADTDictionary ADT is an abstract data type that maintains a set of keys and records a value associated with each key. Lookup returns the associated value for a present key and an “absent” result otherwise. Insertion adds an absent key-value pair and replaces the associated value of a present key. Deletion removes a present key and its value and leaves the state unchanged for an absent key. The specification does not require an ordering of the keys.

3Hash Functions and Buckets

Let $U$ be the universe of keys and let $m$ be the number of buckets. A hash functionHash function is a function

h : U \to {0, 1, \dots, m - 1}

that maps a key to an array index. A bucketBucket is the storage region for keys mapped to the same index. An operation on key $k$ first selects the bucket indexed by $h (k)$ .

A collisionCollision occurs when $h (k_{1}) = h (k_{2})$ for two distinct keys $k_{1}$ and $k_{2}$ . If the cardinality of $U$ exceeds $m$ , the pigeonhole principle makes collisions unavoidable.

4Separate Chaining

Separate chainingSeparate chaining stores a sequence of key-value pairs in every bucket and places colliding entries in the same sequence. Lookup scans only the bucket selected by $h (k)$ . Insertion and deletion likewise compare keys within that bucket. When each chain is implemented as a linked list, an operation's running time depends on the number of entries in its bucket.

5Load Factor and Expected Complexity

Let $n$ be the number of stored keys. The load factorLoad factor is

α = \frac{n}{m} .

Fix the input sequence of keys and choose a function randomly from a hash-function family. Assume simple uniform hashingSimple uniform hashing assumption: each key maps independently and uniformly to one of the $m$ buckets. The expectation is over this random choice. Under the assumption, the expected number of entries in a bucket is $α$ . Lookup, insertion, and deletion with separate chaining therefore take expected time $O (1 + α)$ . If $α$ is kept below a constant, each operation takes expected time $O (1)$ .

This conclusion is not a deterministic guarantee for every hash function. If all keys map to one bucket, lookup, insertion, and deletion take $O (n)$ time in the worst case.

6Resizing

ResizingResizing allocates a larger bucket array and redistributes all keys when the load factor exceeds a prescribed threshold. Because changing the bucket count changes the range of hash values, merely copying the existing entries is insufficient: the bucket of every key must be recomputed.

A single resize takes $O (n)$ time. If the bucket count grows by a constant factor, however, its cost can be distributed over many insertions. Assume that after resizing a function satisfying simple uniform hashing is selected, that $α$ remains bounded by a constant, and that one hash computation takes $O (1)$ time. Insertion then takes $O (1)$ amortized expected time.

7Scope of Application

Hash tables are appropriate for exact-key lookup.
When an application directly requires sorted keys, range queries, or a minimum key, an order-preserving data structure such as a balanced search tree is more appropriate.

8Summary

A hash table selects a bucket with a hash function and resolves collisions by separate chaining. Under simple uniform hashing and a bounded load factor, dictionary operations take expected $O (1)$ time, whereas their worst-case time is $O (n)$ .