Hash tables, sets, maps, trees, heaps, and graphs

One 、 Hashtable 、 mapping 、 aggregate

• hash Definition
  Hashtable （Hash table）, Also called a hash table , According to the key code value （Key value） Data structures that are accessed directly . 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 （Hash Function）, The array of records is called a hash table （ Or hash table ）.

• The engineering practice
  Telephone directory 、 User information sheet 、 cache （LRU Cache） And key value pair storage （Redis） etc. .

• hash function
  

• hash Collision
  

• set、map
  map yes key-value Yes ,key No repetition ;set： A collection of non repeating elements .

Two 、 Trees 、 Binary tree 、 Binary search tree

• Trees and pictures
  
  

• The list is a special tree , Trees are special graphs

• Traversal of binary tree ：
  1. Before the order （Pre-order）： root - Left - Right
  2. Middle preface （In-order）： Left - root - Right
  3. In the following order （Post-order）： Left - Right - root
  Common traversal algorithms ：1. recursive ;2. iteration + Stack .

• Binary search tree
  Binary search tree , Also known as binary sort tree 、 Ordered binary tree （Ordered Binary Tree）、 Sort binary trees （Sorted Binary Tree）, An empty tree or a binary tree with the following properties ：
  1. The value of all nodes in the left subtree is less than the value of its root node ;
  2. The value of all nodes in the right subtree is greater than the value of its root node ;
  3. And so on ： Left 、 Right subtrees are also binary search trees .
  In the sequence traversal ： Ascending order

3、 ... and 、 Pile and binary pile

• The top of the heap is the maximum or minimum , The biggest one is called the big top pile , The smallest one is called small top pile . The time complexity of finding the best value is O(1).
• Binary heap is realized by complete binary tree , Actually do it with an array . The index for i The left child's index is 2i+1; The index for i The right child's index is 2i+2; The index of the parent node with index is floor（（i-1）/2）;