Abstract
- Take in a variable-length text and give a fixed-length Hash Digest
- We want a hash function that calculates Hash to be certain - always gives the same output given the same input, and efficient - takes as little computation as possible
Key must be Immutable
If the key changes, then its hash value will change, and we will lose the mapping between the key & the bucket index
Objects created on Heap Segment can be key even if we can manipulate the elements inside the object. This is because we use its Memory Address to generate the Hash, instead of the elements inside the object
Uses modular arithmetic to calculate bucket index
We should use Prime Number (质数) to calculate bucket index, this can greatly reduce Hash Collision when there is some kind of pattern in the give input like the input is a multiple of 3
Hash function in programming languages
Refer to hello-algo
Desired Properties for Security
Avalanche effect (雪崩效应)
- If an input is changed slightly, the output changes significantly
Collision resistance (抗碰撞性)
- It is hard to find two inputs that hash to the same output