当前位置:网站首页>Deng Junhui's notes on data structure and algorithm learning - Chapter 9
Deng Junhui's notes on data structure and algorithm learning - Chapter 9
2020-11-09 08:20:00 【osc_0m0d4mbq】
List of articles
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 .
版权声明
本文为[osc_0m0d4mbq]所创,转载请带上原文链接,感谢
边栏推荐
- linx7.5 初始安装
- Copy on write collection -- copyonwritearraylist
- First development of STC to stm32
- 14. Introduction to kubenetes
- Service grid is still difficult - CNCF
- 商品管理系统——SPU检索功能
- A solution to the problem that color picker (palette) cannot use shortcut keys in sublime Text3 plug-in
- Natural language processing (NLP) roadmap - KDnuggets
- GDI 及OPENGL的区别
- This program cannot be started because msvcp120.dll is missing from your computer. Try to install the program to fix the problem
猜你喜欢
LTM understanding and configuration notes
First development of STC to stm32
File queue in Bifrost (1)
5 个我不可或缺的开源工具
App crashed inexplicably. At first, it thought it was the case of the name in the header. Finally, it was found that it was the fault of the container!
23 pictures, take you to the recommended system
For the first time open CSDN, this article is for the past self and what is happening to you
基于LabVIEW实现的几种滚动字幕
程序员都应该知道的URI,一文帮你全面了解
After Android solves the setrequested orientation, the rotation of the mobile phone screen does not trigger the onconfigurationchanged method
随机推荐
Huawei HCIA notes
Have you ever thought about why the transaction and refund have to be split into different tables
5 个我不可或缺的开源工具
Talk about my understanding of FAAS with Alibaba cloud FC
老大问我:“建表为啥还设置个自增 id ?用流水号当主键不正好么?”
对象
This program cannot be started because msvcp120.dll is missing from your computer. Try to install the program to fix the problem
Oschina plays disorderly on Monday
Investigation of solutions to rabbitmq cleft brain problem
[Python from zero to one] 5. Detailed explanation of beautiful soup basic syntax of web crawler
程序员都应该知道的URI,一文帮你全面了解
C + + adjacency matrix
B. protocal has 7000eth assets in one week!
Adding OpenGL form to MFC dialog
Exception capture and handling in C + +
Three ways to operate tables in Apache iceberg
First development of STC to stm32
写时复制集合 —— CopyOnWriteArrayList
object
The vowels in the inverted string of leetcode