08 Hashing
Data structure to store key-element pairs. Each key-element pair is called an item.
Benefits¶
- data encryption
- Search optimization, by reducing the search space
Parts¶
- Hash Function
- Bucket/Array (called dictionary/table)
Types¶
| Hashing | Hash Function | Use | |
|---|---|---|---|
| Component | \(\sum x_n\) | ||
| Polynomial | \(\sum x_{n} a^{n}\) | Unique code | |
| Division | \(k \% n\) | Reduce code size | \(k=\) key (element) \(n =\) prime (unique code) |
| MAD | \((a k + b) \% n\) |
Finding Remainder in calculator¶
Mode > Bases > Decimal
Remainder = Dividend - (Divisor * Quotient) = Dividend - (Divisor * \(\frac{\text{Dividend}}{\text{Divisor}}\))
Reason¶
Dividend = (Divisor * Quotient) + Remainder
Example¶
\[ \begin{aligned} & 10 \% 3 \\ &= 10 - \left( 3 * \frac{10}{3} \right) \\ &= 10 - ( 3 * 3 ) \\ &= 10 - 9 \\ &= 1 \end{aligned} \]