一、散列表如Java中的map,Python中的dict
SHA函数:
待定。。。
你几乎根本不用自己去实现散列表,因为你使用的编程语言提供了散列表实现。你可使用
Python提供的散列表,并假定能够获得平均情况下的性能:常量时间。
散列表是一种功能强大的数据结构,其操作速度快,还能让你以不同的方式建立数据模型。
你可能很快会发现自己经常在使用它。
总结:
? 你可以结合散列函数和数组来创建散列表。
? 冲突很糟糕,你应使用可以最大限度减少冲突的散列函数。
? 散列表的查找、插入和删除速度都非常快。
? 散列表适合用于模拟映射关系。
? 一旦填装因子超过0.7,就该调整散列表的长度。
? 散列表可用于缓存数据(例如,在Web服务器上)。
? 散列表非常适合用于防止重复。
二、图:广度优先搜索 是用于图查找的算法,帮助回答两个问题:
1)、从A到B有路径吗?
2)、从A到B的最短路径是什么?
使用队列存储数据(队列是按添加顺序存储)
队列是先进先出,栈是先进后出
广度优先搜索的运行时间为(V+E)=边数+点数
拓扑排序:从某种程度上说,这种列表是有序的。如果任务A依赖于任务B,在列表中任务A就必须在任 务B后面。这被称为拓扑排序,使用它可根据图创建一个有序列表。
总结:
-
广度优先搜索指出是否有从A到B的路径。
-
? 如果有,广度优先搜索将找出最短路径。
-
? 面临类似于寻找最短路径的问题时,可尝试使用图来建立模型,再使用广度优先搜索来
解决问题。
-
? 有向图中的边为箭头,箭头的方向指定了关系的方向,例如,rama→adit表示rama欠adit钱。 ?无向图中的边不带箭头,其中的关系是双向的,例如,ross - rachel表示“ross与rachel约
会,而rachel也与ross约会”。
-
? 队列是先进先出(FIFO)的。
-
? 栈是后进先出(LIFO)的。
-
? 你需要按加入顺序检查搜索列表中的人,否则找到的就不是最短路径,因此搜索列表必
须是队列。
-
? 对于检查过的人,务必不要再去检查,否则可能导致无限循环