Hash table

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")

Copy

  Hash Table Mainly by 2 Part of it is made up of ：

1. hash function
2. 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^0jack 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 .