当前位置:网站首页>Hash table
Hash table
2022-07-04 21:38:00 【Wu_ Candy】
This is the first step of infinite testing 163 Original article
During the interview , Have been asked : Do you know what the underlying data structure of the dictionary is ?
What we are mainly talking about today is what the data structure of hash table looks like ; How hash collision is caused and how to solve hash collision .
1. Definition
Hashtable (Hash table, Also called a hash table ), According to the key code value (Key value) Data structures that are accessed directly . in other words , It accesses records by mapping key values to a location in a table , To speed up the search . This mapping function is called the hash function , The array of records is called a hash table .
The example of dictionary stored value is as follows . In order to understand the data structure of hash table more popularly , Let's look at the picture below :
put("jack","666")
put("Rose","777")
put("Evan","888")
Hash Table Mainly by 2 Part of it is made up of :
- hash function
- Table 「 The bottom layer is an array , The general array size is 2n 」 As for why , For the convenience of bit operation
Hash Functions and Table The role of
hash The main function is to convert key To operate , Generate an index value of an integer index. Corresponding to our case :
hash("Jack") --> index = 14
hash("Rose") --> index = 01
hash("Evan") --> index = 03
And then according to index The corresponding value Store in Table Array . To complete the key and value Mapping .
2.Hash Collision
Let's add another set of data to the dictionary (Jeffery,999)
, hypothesis hash("Jeffery") --> index = 03
, At this point, you will find that ,Jeffery and Rose Of index All for 3, The conflict , This is it. Hash Collision .
3. solve Hash Collision
solve Hash Common methods of conflict :
- 1. Open addressing (Open Addressing): According to certain rules, probe other addresses , Until you meet an empty place
- 2. Then the hash method (Rr-Hashing)“ Design multiple hash function
- 3. Chain address (Separate Chaining) For example, through a linked list, the same index The elements of
Today we mainly want to introduce the chain address method , If I found hash At the time of the collision , You can use a single linked list to list the same index The elements of , As shown in the figure below :
4. How to survive key Hash value of ?
key Common types may be : Integers 、 Floating point numbers 、 character string 、 Define the object . Different kinds of key, Hash values are generated differently , But the goal is the same :
- 1. Try to make every key The hash value of is unique
- 2. Try to make key All of the information in the calculation
In this paper, the key All are strings , With jack For example :jack The hash value of can be expressed as :j * n^3 + a * n^2 + c * n^1 + k * n^0
jack
Of ASCII It's all traceable , Therefore, an integer can be obtained through the above calculation T, And then through Table The size of the array & An operation
perhaps % Decouple operation
, You can get inedx Subscript value .
About integers 、 Floating point numbers 、 Define how the hash value of an object is calculated , If you are interested, you can search , There is a systematic explanation .
summary
Today, I mainly introduce how the hash table data structure stores values , Then it explains how hash collision is generated and how to solve it , Finally, the string key How to calculate the hash value of . I believe you will read this article carefully , I have a clear understanding of what a hash table is .
边栏推荐
- redis管道
- [ 每周译Go ] 《How to Code in Go》系列文章上线了!!
- Liu Jincheng won the 2022 China e-commerce industry innovation Figure Award
- minidom 模块写入和解析 XML
- EhLib 数据库记录的下拉选择
- Kubeadm初始化报错:[ERROR CRI]: container runtime is not running
- Jerry's ad series MIDI function description [chapter]
- A quick start to fastdfs takes you three minutes to upload and download files to the ECS
- 更强的 JsonPath 兼容性及性能测试之2022版(Snack3,Fastjson2,jayway.jsonpath)
- 杰理之AD 系列 MIDI 功能说明【篇】
猜你喜欢
FastDfs的快速入门,三分钟带你上传下载文件到云服务器
Analyzing the maker space contained in steam Education
创客思维在高等教育中的启迪作用
torch. Tensor and torch The difference between tensor
开源之夏专访|Apache IoTDB社区 新晋Committer谢其骏
ApplicationContext 与 BeanFactory 区别(MS)
[ 每周译Go ] 《How to Code in Go》系列文章上线了!!
Daily question -leetcode1200- minimum absolute difference - array - sort
Interpreting the development of various intelligent organizations in maker Education
How to remove the black dot in front of the title in word document
随机推荐
Methods of improving machine vision system
How to use concurrentlinkedqueue as a cache queue
redis发布订阅的使用
应用实践 | 蜀海供应链基于 Apache Doris 的数据中台建设
Rotary transformer string judgment
Shutter WebView example
[wechat applet] collaborative work and release
The video sound of station B is very low - solution
EhLib 数据库记录的下拉选择
MP3是如何诞生的?
y56.第三章 Kubernetes从入门到精通 -- 业务镜像版本升级及回滚(二九)
In the release version, the random white screen does not display the content after opening the shutter
Numpy vstack and column_ stack
华为模拟器ensp的路由配置以及连通测试
Difference between ApplicationContext and beanfactory (MS)
redis RDB AOF
Interviewer: what is XSS attack?
2021 CCPC Harbin I. power and zero (binary + thinking)
torch. Tensor and torch The difference between tensor
TCP三次握手,四次挥手,你真的了解吗?