企业官网建设流程全解析

哈希表的核心思想是使用一个哈希函数。这个函数接收一个键（必须是可哈希的不可变对象，如整数、字符串、元组），并输出一个整数。这个整数被用作索引，来访问一个类似数组的“哈希表”。

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.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_106.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_107.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_109.png

https://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.png

https://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.png

https://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.png

https://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.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_126.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_127.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_129.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_131.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_133.png

计算模拟 🎲

上一节我们探讨了哈希表的工作原理。本节中，我们将学习如何使用模拟这一强大的计算技术来解决实际问题。

模拟允许我们用计算来描述和复现现实世界的事件。其基本流程是：

1. 定义事件：明确你要模拟的现实世界场景。

2. 设计计算实验：用代码构建该事件的模型，通常引入随机性。

3. 重复实验：使用循环多次运行该实验。

4. 跟踪结果：记录你感兴趣的特定结果发生的次数。

5. 分析报告：根据重复实验的结果，计算并报告目标值（如概率、平均值）。

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_135.png

https://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.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_140.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_141.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_143.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_145.png

https://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.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_150.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_151.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_153.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_154.png

importrandom<https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_156.png><https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_158.png>defdice_probability(side_of_interest,num_trials=10000):dice_faces=['.','..','...','....','.....','......']# 代表1到6点count=0for_inrange(num_trials):roll=random.choice(dice_faces)# 模拟一次掷骰ifroll==side_of_interest:count+=1probability=count/num_trialsreturnprobability<https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_160.png><https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_162.png><https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_164.png><https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_165.png><https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_166.png><https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_168.png><https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_170.png>print(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.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_174.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_175.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_177.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_179.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_180.png

https://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. 设计实验：在1到3之间随机生成一个流速flow_rate。

2. 计算单次结果：注满时间time = 600 / flow_rate。

3. 重复实验：将此过程重复大量次数（如10,000次）。

4. 报告结果：计算所有time的平均值。

importrandomdeffill_pool_simulation(size=600,num_trials=10000):fill_times=[]for_inrange(num_trials):# 生成1到3之间的随机流速flow_rate=1+2*random.random()time_to_fill=size/flow_rate fill_times.append(time_to_fill)average_time=sum(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.png

https://github.com/OpenDocCN/cs-notes-pt2-zh/raw/master/docs/mit-6100l-cs-py-prog/img/cb405334840604e69c721d8295bc8a66_187.png

感谢大家在本课程中的努力与参与！编程是一项强大的技能，希望你们能享受用它来探索和解决问题的过程。祝大家考试顺利，假期愉快！