## Data Structures

# Hash table vs range query

## When to use which one for efficiency?

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 anindex, also called ahash code, into an array ofbucketsorslots, 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 queryconsists of preprocessing some input data into a data structure to efficiently answer any number of queries on any subset of the input. Particularly, there is a group of problems that have been extensively studied where the input is an array of unsorted numbers and a query consists of computing some function, such as the minimum, on a specific range of the array.

→ Range queries can be used to solve Range Min/Max & Sum Queries and Range Update Queries in O(log n) time.