散列表
最有用的基本数据结构之一。查找时间都为O(1)，O(1)被称为常量时间，即所需的时间都相同。
散列函数将输入映射到数字。它需要满足下列几个条件：
1）他必须是一致的，即你不管什么时候每次输入相同时，输出都要一样。如果不是这样，散列表将毫无用处。
2）它应将不同的输入映射到不同的数字。
散列表在Python语言中时用字典dict{}来表示。
冲突
有可能不同的输入会映射到同一个位置，这就叫冲突。因此可以在同一个位置储存一个链表，这样才不会发生冲突。解决冲突的方法：
1）散列函数很重要。理想的散列函数将键均匀的映射到散列表的不同位置。
2）散列函数用的好，链表就不会很长。
性能
散列表的查找速度与数组一样快，而插入与删除速度与链表一样快，因此它兼具两者的优点。而要避免冲突，需要有：
1)较低的填装因子；2)良好的散列函数
填装因子=散列表包含的元素数/位置总数。
填装因子越低，发生冲突的可能性越小，散列表的性能越高。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。
广度优先搜索算法
广度优先算法能让你找出两样东西之间最短的距离。使用广度优先搜索可以：
1）编写国际跳棋A，计算最少走多少步就可以获胜
2）编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词
3）根据你的人际关系网络找到关系最近的医生
图算法是广度优先算法最有用的
图由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。广度优先搜索是一种用于图的查找算法，可帮助回答两类问题：
第一类：从节点a出发，有前往b的路径吗
第二类：从节点a出发，前往节点b的哪条路径最短
队列是一种先进先出（First In First Out FIFO）的数据结构，可用于广度优先搜索算法。
实现图的算法是由散列表表示
有向图用箭头表示，关系是单向的，无向图没有箭头，直接相连的节点叫做邻居。例如下面的两个图是等价的。
实现算法
fromcollectionsimportdequegraph={} graph["you"]=["alice","Bob","claire"] #我的一度关系defperson_is_seller(name): #判断是否是销售的returnname[-1]=='m'#名字末尾为m说明是销售的defsearch(name): search_queue=deque() #创建一个队列search_queue+=graph[name] #将你的邻居都加入这个搜索队列中searched=[] #已经检查过的人whilesearch_queue: #只要队列不为空person=search_queue.popleft() #就取出其中的第一个人ifpersonnotinsearched: ifperson_is_seller(person): #检查这个人是不是销售的print(person+' is a mango seller!') returnTrueelse: search_queue+=graph[person] #表示销售商就将这个人的朋 友都加入搜索队列searched.append(person) #将这个人标记为检查过returnFalse#如果达到这里就说明队列中没有人是销售商search("you")
算法执行过程如下图
运行时间
如果在你的整个人际网络中搜索销售商，就意味着你将沿着每条边前行（边是从一个人到另外一个人的箭头或连接），因此运行时间至少为O（边数）。
你还使用了一个队列，其中包含要检查每一个人。将一个人添加到队列的时间是固定的，即为O（1），因此对每个人都这样做的时间为O（人数）。所以广度优先搜索的运行时间为O（人数＋边数），通常为O（V+E），其中V为顶点数，E为边数。
有序列表中，如果任务A依赖于任务B，在列表中任务A就必须在任务B后面，这种被称为拓扑排序，使用它可以根据图创建一个有序列表。如下图就是拓扑顺序。
下面的图被称为树。树是一种特殊的图，其中没有往后指的边
