A hash search is a data access method that uses a hash function to map a search key (e.g., an identifier or ID number) directly to a position in a hash table.
- The average search time is O(1), i.e., constant.
- If two different keys produce the same hash value (collision), additional techniques such as chaining or open addressing are applied.
In the context of Relational Databases
- Some DBMSs support hash indexes (e.g., PostgreSQL).
- They are highly efficient for equality queries (
WHERE id = 1500), since the hash function points straight to the expected location. - Limitation: they are not efficient for range queries (
BETWEEN,<,>) or sorting, because the hash does not preserve order. - In practice, B-Tree indexes are more common due to their versatility.
Simple example
Key: NIF = "12345678A".
- Compute:
hash("12345678A") = 42 - Search directly in position
42of the hash table. - If the record is there → found ✔
- If a collision occurs (e.g.,
hash("98765432B") = 42), a resolution strategy is applied.
Comparison with binary search
| Feature | Binary search (B-Tree) | Hash search |
|---|---|---|
| Average complexity | O(log n) | O(1) |
| Requires sorted data | ✔ Yes | ✘ No |
| Range queries | ✔ Efficient | ✘ Not applicable |
| Equality queries | Good | Excellent |
| Typical use in DBMS | Default (B-Tree) | Specific cases (hash index) |
