This is the 8th day of my participation in Gwen Challenge

1. Introduction to dictionaries

1.1 What is a dictionary?

Dictionaries are one of python data types.

Dictionaries contain data items in curly braces.

Info = {‘name’:’JUEJING’,’address’:’juejin ‘}

  • Each element of a dictionary consists of two parts, key: value
  • The dictionary looks for values based on keys

1.2 Dictionary Features
  • Dictionaries, like lists and collections, are mutable data types
  • Dictionaries, like lists, can store multiple pieces of data

Dictionaries are made up of key-value pairs,

  • Key objects are unique, so only immutable data types (numbers, strings, and tuples) can be used as key objects
  • The value object can be any Python data type

DICT = DICT = {"num":8,"List":["List",8],"Tuple":("Tuple",5),"Dict":{"Name":"Dictonary"},"STR":"STR",("world",10):"Earth",5:"Lucky"} # Print dictionary (DICT)Copy the code

2. Dictionary memory distribution

At the heart of dictionary objects are discrete lists. A hash table is a sparse array (an array that always has blank elements)

Each element of the array is called a bucket. Each bucket has two parts, a reference to a key object and a reference to a value object.

Since all buckets have the same structure size, we can read the specified bucket by deviation.

2.1 Key-value pair stored procedures
Student = {} # add: "name":"Tom","age":7,"sex":"boy" student["name"] = "Tom" student["age"] = 7 student["sex"] = "boy"Copy the code

We want to put the key-value pair “name” = “Tom” into the dictionary object student. How does that work?

  1. The first step is to calculate the hash value of student[” name “].
>>> bin(hash("name"))
'0b10XXX1100011100111101001001111101010100010101000'
Copy the code
  1. Once we get the hash value, we take the deviation from the right-most 3 digits of the hash value, which is “000” and the decimal digit is 0.
  2. We check to see if the corresponding bucket is empty, and if so, we put the key-value pair in it.
  3. If it is not empty, then the three bits to the right are taken as the deviation, that is, “101”, and the decimal digit is 5.
  4. Then see if the bucket with deviation of 4 is empty until an empty bucket is found and the key-value pair is inserted.

2.2 Dictionary lookup process
Student = {"name":"Tom","age":7,"sex":"boy"} print(student["name"])Copy the code

Student’s name. How does that process work?

  1. We will calculate the “name” object from student[“name”]
>>> bin(hash("name"))
'0b10XXX1100011100111101001001111101010100010101000'
Copy the code
  1. Determine the deviation. The rightmost 3 digits of the hash value are used as the deviation “000”, and the decimal digit is 0.
  2. Check to see if the offset is 0 and the corresponding bucket is empty, or if not, return None.
  3. If not empty, the corresponding hash value is computed for the key object of this bucket
  4. Compare to the “name” hash of student[“name”]
  5. If two hash values are equal, the value object in the corresponding array is returned
  6. If they are not equal, the deviation is recalculated by taking the other digits in turn.
  7. If None is found, None is returned.

conclusion

Summary of dictionary Usage:

  1. Keys must be hashed (1) Numbers, strings, tuples, all hashed. (2) User-defined objects need to support the following three points: Hash () function supports equality detection through __eq__() method If a == b is true, hash(a)==hash(b) is also true
  2. Dictionaries are huge overhead in memory, typically space swap time
  3. Key queries are fast
  4. Adding new keys to a dictionary can cause expansion, which changes the order of the keys in the hash table, so don’t modify the dictionary at the same time as you iterate on it.