Concepts of dictionary, hash table and array

explain ： This article is also what I learned from consulting materials on the Internet , Does not mean complete accuracy ！！ Only represent personal thoughts , Welcome to errata .

important ： Don't confuse the abstract data structure with the underlying implementation .

Catalog

One 、 Array

Two 、 Dictionaries

3、 ... and 、 Hashtable

Four 、 summary

---

One 、 Array

The data structure is called one-dimensional array , Linear table can be used 、 vector 、 One dimensional matrix to store .

The data structure is called two-dimensional array , It can be used as a two-dimensional matrix or as an internal storage of some other structure .

characteristic

        1. An array is a collection of elements of the same data type .

        2. The elements in an array are stored in sequence , They are stored in memory in this order .

        3. An array element is represented by the name of the entire array and its own ordinal position in the array . for example ,a[0] Indicates the name is a The first element in the array of ,a[1] Representative array a The second element of , And so on .

Two 、 Dictionaries

        Dictionary is an applied concept , Is a structure that stores key value pairs , You can use hash tables 、 Red black tree implementation .

        therefore , Many people are confused , What's the difference between a dictionary and a hash table , Why is it so similar , Are stored key value pairs . At the bottom of the dictionary is the hash table （ not always , It could be a tree ） ah ！！

3、 ... and 、 Hashtable

Baidu Encyclopedia ：“ Hash table （Hash table, Also called Hashtable ）, Is according to the key （Key） And directly access the data structure in memory storage location . in other words , It works by calculating a function of the key value , Map the data you want to query to a location in the table to access records , This speeds up the search . This mapping function is called the hash function , The array of records is called Hash table .

         The hash table stores entry, That is, key value pairs . Hash function pairs Key Hash to get a hash value , This value is the address of the key value pair in the hash table . Then you can guess , If the hash function is not designed so well , Probability will produce sparsity , It can be understood as a one-dimensional array , Elements are stored randomly , Spacing between elements N Empty space . in other words , From a mathematical point of view, a hash table may be a sparse array .

         So it seems , Hash （ hash ） Functions are extremely important , A good hash algorithm can make the hash table close to the array , Instead of sparse arrays （ One dimensional matrix ）.

          What is hash collision ？ It's just one. Entry Key Get a hash value after hashing , This value is its pit , Then I found that the pit had been occupied , This is hash collision . There are two ways to solve hash collision ： Open chain method and open addressing method .

        Open chain method is easy to understand , When it was found that the pit was occupied , Just create a linked list , The corresponding position of the hash table stores the pointer to this linked list , Later elements can be stored on demand , It can be placed at the end of the chain , It can be inserted at the end of the chain , It can also be arranged in order of size , Anyway, choose on demand , The addition and deletion of linked lists are very convenient .

        The open addressing method is when this pit is found to be occupied , Then go down to find out whether the next position is occupied , If not, just take this entry Put it in , If it is still occupied , Just keep looking for , Get it done . Of course, what is introduced here is only an implementation , There are other options , This is a concept , Those who are interested can continue Google Study .

        When the number of key value pairs increases , The hash table may not fit , Then we need to expand the capacity . There are many different expansion schemes , among redis There is an expansion factor . For example 0.5, Apply first 1000 Space , When occupying 500 After three positions , Start to reapply for space , also rehash To the new hash table , and redis It's progressive rehash, Those who are interested can read this book , It's very detailed , Strongly recommend ：《redis Design and implementation 》

        To make a long story short , A hash table is a sparse array , When hash collision occurs, it can become a sparse array + Linked list or sparse array + Trees .

Four 、 summary

        Dictionaries and hash tables are data structures that store key value pairs , But the dictionary is the application layer , It 's an abstract concept , The bottom layer can be a hash table or a red black tree . One of the basic data structures of hash table is sparse array , If the hash function is well designed , It can be similar to an array , That is, there is no vacancy . Array is a continuous storage data structure .