Deng Junhui's notes on data structure and algorithm learning - Chapter 9

Want to make APP Same thing as WeChat , Can run small programs smoothly ？ | Experience will send you to Xinjiang 、 Huawei 、 Cherry keyboard ！>>>

day58
Chapter nine The dictionary

9. The dictionary

9.b Hash principle

Hashing- hash
The data comes from a fairly large space , But the actual data to be stored and organized is a very small subset of it , Space efficiency is extremely low
Compress space
The pigeon nest problem , take x From a larger definition domain , Mapping to a smaller range of values , There are ways to reduce conflict （ Design better hash function or increase hash table length M）, But it can't be avoided （ How to solve ？）

9.c Hash function

gcd: The greatest common factor is 1
Take the middle bit , It can make the influence of each digit of the original key code closer to each other , Here's the picture , Square operations can be decomposed into addition operations
The more random the hash function is , The more irregular , The better .
key It may not be an integer , You need to convert it to hashcode, Do it again. , Here's the picture
It is necessary to , If you use a simple calculation method , It's easy to have hash conflicts

9.d Conflict

9.d1 Hash resolves conflicts 1

Skip when searching , Insert directly when inserting .

9.d2 Hash resolves conflicts 2

Closed addressing vs Open addressing
The linear heuristics described above , It's too close to each other , There will be a lot of unnecessary conflicts . You can open the space properly
Suppose the size of a cache is 1KB, Only the pointer is stored in the bucket （4 byte ）, Well, unless 16 Secondary hash conflict , To make the cache invalid , Need extra I/O.
b+a≥2, yes M The nontrivial factor of , This is related to M Contradict prime numbers .
For some primes （ for example 7,11） The long table , The two-way search chain works , Some primes （ for example 5,13） The effect of the surface length is not good .

9.e bucket / Count sorting

among n Is the number of elements ,[0,M) Is the element range
Where the red line is the integral of the blue line
Linear scan over and over again count[], Scan again count[] obtain accum[], You can sort in linear time .