HashIndex

Hashindex is a type of database index that uses a hash function to map search keys to locations, or buckets, in an index structure. The hash function converts a key into a numeric value, which determines where the corresponding record reference or record data is stored. On insertion, the key is hashed to pick a bucket; on lookup, the same hash is computed to locate the bucket and a search within that bucket confirms the exact match. Collisions, where two keys hash to the same bucket, are resolved by methods such as separate chaining or open addressing.

Hash indexes are designed for fast exact-match queries and typically offer near-constant-time lookups when the hash distribution is uniform. They do not preserve order, so they are not well suited for range queries or ordered scans. Maintenance tasks include handling updates and deletions, and resizing or rehashing may be required as the dataset grows or shrinks. Poor hash functions or skewed data can lead to bucket contention and degraded performance.

Variants of hash indexing include static hash indexes and dynamic schemes such as extendible hashing and linear hashing, which adjust the index structure as data changes. Disk-based implementations must manage overflow space and caching considerations, while in-memory versions emphasize speed and memory usage.

Hash indexes are commonly used for workloads that rely on exact-key lookups on a column and where range predicates are infrequent. In practice, they are often used alongside other index types, such as B-trees, to support a broader range of query patterns.