# Data Structure (II) - 04 Hashing
> PART (II) - 04
> Other parts in this series $\rightarrow$ [Data Structure - Syllabus ](/bU7575BKTwmwkvmJ5742xA)

# What is hashing
Hashing is a technique used in data structures that efficiently stores and retrieves data in a way that allows for quick access. It involves mapping data to a specific index in a hash table using a hash function that enables fast retrieval of information based on its key.
## Performance Comparison of Arrays and Trees
||Array<br>(Sorted)|Array<br>( Not Sorted)|Tree<br>(Unbalanced) |Tree<br>(Balanced)|
|:---:|:---:|:---:|:---:|:---:|
Insertion| O(n) |O(1) |O(h)| O(log n)|
Searching| O(log n)| O(n)| O(h) |O(log n)|
Deletion| O(n) |O(1) |O(h) |O(log n)|

# Static Hashing
* hash function: to transform a key into a table index.
* hash collision: Two records (keys) attempt to insert into the same bucket (position)
## Hash Table

In static hashing, identifiers/keys are stored in a hash table.
* **Slot**: space for storing data
* **Bucket**: Each bucket may consist of $s$ slots to hold
* **synonym** (同義字)
* $k_1$ and $k_2$ are synonyms if $h(k_1)=h(k_2)$
* **Hash collision**: home bucket for new data is not empty

## Hash Functions
* Division
* $h(k)=k\%D$, $D$=remainder (餘數)
* Since the bucket address is from 0 to b-1 if, there are b buckets, usually D=b.
* Prime numbers (質數) are good choice for D
* For most practical dictionaries, D is a good cadidate if it has no prime factor smaller than 20
* Mid-square
* Folding
* Digit Analysis