学习笔记：
哈希表（Hash Table），是根据关键码值（Key Value）而直接进行访问的数据结构。哈希表通过把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。 这个映射函数叫做哈希函数（Hash Function），存放记录的数组叫做哈希表。 关键的是通过哈希函数把要存储的值能够映射到相应的位置，这个位置就是一个下标index，任何一个对象传进来就会映射到一个int的下标，放到数组中即可。
哈希函数选的好的状况会让数值比较分散，不会让数值之间发生碰撞。不同的哈希函数算出来的码值可能相同，不同的字符串经过计算得到相同的数值这种情况叫哈希碰撞。 对于不同的要存储的数据经过哈希函数之后会得到一个相同的值，对应的下标都在尾数相同的一个位置，这时候末尾的位置可能要存储多个元素，排列的方式就是依次往下面存，占别人的位置，最好的方式是在增加一个维度，即拉出来一个链表，这样的方式叫做拉链式解决冲突法，这种时间复杂度是O（1）的，但是如果很多元素都积累在相同的位置时，这时所要查询的时间就是要遍历整个链表，所以在链表很长的情况下效率就会进行退化，退化到O（n）的级别。如果设计的好，哈希函数碰撞的概率就小，在平均时刻哈希函数的查询就是O（1）的时间复杂度。
哈希表的时空复杂度： 哈希表在查询、添加和删除在绝大多数的时候都是O（1）的状态；但是冲突过多可能会有最坏的情况，使得哈希表整个size太小了，以冲突就退化成一个链表了，这时的时间复杂度就退化成O（n）了，一般来说现在的内存都很大，哈希表可以开的也很大，有更多的可以使用的内存空间来换时间的操作。这就可以使得哈希表查询、添加和删除的时间复杂度都是以O（1）的效率来运行。在真正的工程里常用的就不再是哈希表了，而是在哈希表基础上抽象出来的map和set。在Python上就是dict、dictionary或者json，同时set在Python里就是set。
map和set的区别： map是键值对，而key他是不重复的键，但是值是可以重复的。 set是不重复的元素集合，是一个键值对的关系。
树的基本定义，首先有根节点，然后有左子树和右子树，左右子树又有子节点，相对于子节点的上层又叫父节点；平行的节点是兄弟节点。形象分层是从最上一层的第0层逐级增加的。在现实中应用最广的是二叉树（Binary Tree），二叉树就是分为每次两个节点逐级划分，是左子树和右子树，（树和图最大的差别就看是否有环，如果没有环就是树，否则就是图，链表是特殊的树，树是特殊的图——没有环的图就是树）
树节点定义的示例代码： Python
class TreeNode: def__init__(self,val): self.val = val self.left, self.right = None, None
Java
public class TreeNode { public int val; public TreeNode left, right; public TreeNode (int val) { this.val = vla; this.left = null; this.right = null; } }
C++
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode (int x) : val (x), left (NULL), right (NULL) {} }
二叉树遍历（Pre-order/In-order/Post-order） 1.前序（Pre-order）: 根-左-右 2.中序(In-order): 左-根-右 3.后序列(Post-order): 左-右-根
二叉搜索树（Binary Search Tree） 二叉搜索树也称二叉排序树/有序二叉树（Ordered Binary Tree）/排序二叉树（Sorted Binary Tree）,是指一棵空树或者具有下列性质的二叉树： 1.左子树上所有节点的值均小于它上面根节点的值； 2.右子树上所有节点的值均大于它上面根节点的值； 3.以此类推——左、右子树也分别称为二叉查找树。
中序遍历是升序排列。
思考树的解法为什么一般都是用递归的方式？ 它的代码本身对树的定义没有后继节点/或者便于循环的概念，而是直接分成左右节点。访问其中一个子树，更好的方法就是直接对它其中一个节点再调用相同的遍历函数即可。
堆（Heap） 堆是可以迅速找到一堆数中的最大或者最小值的数据结构。 将根节点最大的堆叫做大顶堆/大根堆；根节点最小的堆叫做小顶堆/小根堆。常见的堆有二叉堆和斐波那契堆等。 大顶堆常见操作的时间复杂度： find-max O（1） delete-max O（logn） insert（create） O（logn）/O（1）
二叉堆的性质 通过完全二叉树来实现（严格区分二叉树和二叉搜索树的不同）；二叉堆（大顶）满足下列性质： 1.是一个完全树； 2.数中的任意节点的值总是 >= 其子节点的值。
二叉堆实现细节 1.二叉堆一般都通过数组来实现； 2假设“第一个元素”在数组中的索引为0的话，则父节点和子节点的位置关系如下： a.索引为i的左子索引是（2i+1）； b.索引为i的右子索引是（2i+2）； c.索引为i的父节点索引是floor（（i-1）/2）。 插入（insert）操作： 1.新元素一律先插入到堆的尾部； 2.依次向上调整整个堆的结构（一直到根即可HeapifyUP） 删除（delete max）堆顶操作： 1.将堆尾元素替换到顶部（即堆顶被替代删除掉） 2.依次从根部向下调整整个堆的结构（一直到堆尾即可HeapifyDown）
图：即有点有边。其属性如下：
Graph（V,E）
点（V-vertex） 1.度-入度和出度； 2.点与点之间的连通与否。
边（E-edge） 1.有向和无向（单行线）； 2.权重（边长）。