Data Structures

Hash table vs range query

When to use which one for efficiency?

Photo by Mark Fletcher-Brown on Unsplash

Each data structure has associated costs and benefits. In practice, it is hardly ever
true that one data structure is better than another for use in all situations. If one
data structure or algorithm is superior to another in all respects, the inferior one
will usually have long been forgotten.

Hash table

In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.

→ Hash tables are good for doing a quick search on things.

Range query

In data structures, a range query consists of preprocessing…