哈希表的核心思想是使用一个哈希函数。这个函数接收一个键必须是可哈希的不可变对象如整数、字符串、元组并输出一个整数。这个整数被用作索引来访问一个类似数组的“哈希表”。https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_101.png关键点由于我们知道了索引通过哈希函数计算得出而通过索引访问数组是常数时间Θ(1)。如果哈希函数本身的计算也是常数时间那么整个字典查找操作的平均时间复杂度就是Θ(1)。https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_103.png以下是Python中哈希函数的例子hash(123)# 返回 123hash(hello)# 返回一个整数如 -1182655620hash((1,2))# 返回一个整数https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_104.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_106.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_107.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_109.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_110.png哈希碰撞与哈希表大小一个理想的哈希函数会将每个不同的键映射到哈希表中唯一的位置。但如果我们想为所有可能的键例如所有20字符长的名字都预留唯一位置需要的哈希表将极其巨大2^160 个位置而实际存储的键可能只有几千个造成巨大的空间浪费。https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_112.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_114.png因此实际的解决方案是使用一个大小合理的哈希表例如10000个位置并允许哈希碰撞——即不同的键经过哈希函数计算后得到了相同的索引。当发生碰撞时多个键值对会被存储在哈希表的同一个“桶”中通常以链表形式组织。查找时先通过哈希函数定位到桶然后在桶内的链表中线性搜索目标键。优秀哈希函数的特点以下是设计优秀哈希函数和哈希表的一些原则https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_116.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_118.png均匀分布哈希函数应将输入均匀地映射到哈希表的所有桶中避免大量键聚集在少数桶内。确定性对同一个键哈希函数必须始终返回相同的值否则无法正确查找。高效性哈希函数的计算本身应该是快速的。利用全部输入哈希函数应使用键的全部信息进行计算以减少碰撞。https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_120.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_122.png在最坏情况下如果所有键都哈希到同一个桶查找就退化为在链表中线性搜索时间复杂度为Θ(n)。但在平均情况下拥有良好哈希函数和合适大小的哈希表字典的查找、插入和删除操作都能达到Θ(1)的时间复杂度这使得字典成为处理大量数据时极其高效的工具。https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_124.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_126.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_127.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_129.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_131.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_133.png计算模拟 上一节我们探讨了哈希表的工作原理。本节中我们将学习如何使用模拟这一强大的计算技术来解决实际问题。模拟允许我们用计算来描述和复现现实世界的事件。其基本流程是定义事件明确你要模拟的现实世界场景。设计计算实验用代码构建该事件的模型通常引入随机性。重复实验使用循环多次运行该实验。跟踪结果记录你感兴趣的特定结果发生的次数。分析报告根据重复实验的结果计算并报告目标值如概率、平均值。https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_135.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_137.png示例1模拟掷骰子https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_139.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_140.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_141.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_143.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_145.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_147.png我们想估算掷一个公平的六面骰子得到点数4的概率。设计实验用列表表示骰子的六个面使用random.choice()函数随机选择一面模拟一次掷骰子。重复实验用for循环重复此过程例如10,000次。跟踪结果每次掷骰后检查结果是否为4如果是则计数器加1。报告结果实验结束后用计数器 / 总实验次数估算概率。https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_149.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_150.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_151.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_153.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_154.pngimportrandomhttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_156.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_158.pngdefdice_probability(side_of_interest,num_trials10000):dice_faces[.,..,...,....,.....,......]# 代表1到6点count0for_inrange(num_trials):rollrandom.choice(dice_faces)# 模拟一次掷骰ifrollside_of_interest:count1probabilitycount/num_trialsreturnprobabilityhttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_160.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_162.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_164.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_165.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_166.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_168.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_170.pngprint(dice_probability(....))# 估算得到4点的概率通过增加num_trials如到1,000,000次我们可以得到更接近理论值1/6 ≈ 0.1667的估计。https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_172.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_174.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_175.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_177.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_179.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_180.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_182.png示例2更复杂的问题——水池注水时间https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_184.png一个更有趣的问题是水以随机流速1到3加仑/分钟注入一个600加仑的水池注满水池的平均时间是多少数学求解需要计算积分较为复杂。但用模拟则非常简单设计实验在1到3之间随机生成一个流速flow_rate。计算单次结果注满时间time 600 / flow_rate。重复实验将此过程重复大量次数如10,000次。报告结果计算所有time的平均值。importrandomdeffill_pool_simulation(size600,num_trials10000):fill_times[]for_inrange(num_trials):# 生成1到3之间的随机流速flow_rate12*random.random()time_to_fillsize/flow_rate fill_times.append(time_to_fill)average_timesum(fill_times)/num_trialsreturnaverage_timeprint(fill_pool_simulation())# 输出平均注满时间约为329模拟结果显示平均注满时间约为329分钟这既不是简单平均值300分钟600/2也不是时间范围的中间值400分钟。模拟通过几行代码就给出了一个复杂问题的近似解展示了计算在解决跨学科问题中的强大能力。课程总结与展望 本节课中我们一起学习了列表内存模型、哈希表原理以及计算模拟的应用。现在让我们对整个课程进行回顾。在本课程中我们共同学习了Python编程基础语法、变量、运算符。控制流条件分支if/elif/else、循环for、while、异常处理。数据结构列表、字典、元组等及其操作。代码组织通过函数实现分解与抽象通过类进行面向对象编程将数据与行为绑定。算法如二分查找展示了算法设计对效率的巨大影响。计算复杂度使用大O大Θ表示法分析算法效率。对于未来的学习你可以考虑6.100B下半学期的课程聚焦数据科学涵盖优化算法、高级模拟和机器学习基础。6.101编程基础深入Python编程处理真实数据集强调编写高效、健壮的代码。6.102软件构建学习使用TypeScript等语言注重编写安全、易理解、易维护的代码包含团队合作项目。其他方向如机器学习、算法等课程也是很好的进阶选择。如果你暂时不继续学习编程课程但希望保持技能建议每周花少量时间如30分钟进行编程练习防止生疏。https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_186.pnghttps://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_187.png感谢大家在本课程中的努力与参与编程是一项强大的技能希望你们能享受用它来探索和解决问题的过程。祝大家考试顺利假期愉快