[音乐播放]
>> 道格·劳埃德：现在你 知道了很多关于阵列，
你也知道了很多关于链表。
我们已经讨论 利弊，我们
讨论了链表 可以越做越小，
但他们需要更多的大小。
数组是更直接 用，但他们限制在尽可能多
因为我们要设置的大小 在阵列中，最开始
然后我们坚持了下来。
>> 但是，这是，我们已经差不多 用尽我们所有的主题
有关链接列表和数组。
或者我们？
也许我们可以做一些事情 更具创造性。
而那种贷出的 哈希表的想法。
>> 因此，在哈希表中，我们要尝试 结合的阵列与一个链表。
我们将采取优势 阵列，如随机访问，
能够只是去阵列 单元4或数组元素8
而不必遍历整个。
这是相当快的，对不对？
>> 但是，我们也希望有我们的数据 结构能够增大和缩小。
我们不需要，我们不 要进行限制。
我们希望能够 添加和删​​除的东西
很容易，而如果你还记得， 是与一个阵列很复杂。
我们可以把这种 新事物的哈希表。
>> 如果正确实施， 样的，我们正在做
两个数据的优点 你已经看到了结构，
数组和链表。
插入可以开始 趋向THETA 1。
西塔我们还没有真正讨论过， 但THETA只是平均情况下，
什么实际将要发生。
你不会总是会 有最坏的情况下，
而你并不总是有 在最好的情况下，有啥
一般情况下？
>> 那么平均的插入 为哈希表
可以开始接近恒定的时间。
和删除可以得到 接近恒定的时间。
和查找可以得到 接近恒定的时间。
That's--我们没有一个数据 结构尚未能做到这一点，
所以这已经听上去 像一个非常伟大的事情。
我们真的减轻了 每个自身的缺点。
>> 要达到这种性能 升级虽然，我们
需要重新思考我们如何加入 数据到该结构。
具体来说，我们要的 数据本身告诉我们
它应该在的结构。
如果我们再需要看它是否在 结构，如果我们需要找到它，
我们想看看数据 再次，并能够有效地，
使用数据，随机访问它。
只是通过查看 数据，我们应该有
那里正是我们的想法 会发现它在散列表中。
>> 散列现在的缺点 表是，他们是真的
非常糟糕的订购或排序数据。
而事实上，如果你开始 用它们来订货或排序
数据你失去所有的 优点以前
有在插入和删除的条款。
的时间变得更接近 THETA的n，我们已经基本上
退步成一个链表。
因此，我们只希望使用哈希 如果我们不关心表
数据是否被排序。
对于上下文中 你会使用他们在CS50
你可能不关心 该数据排序。
>> 所以一个哈希表是一个组合 的两个不同的片
与我们熟悉。
第一个是一个函数，它 我们通常所说的哈希函数。
并且散列函数是要 返回一些非负整数，其
我们通常所说的哈希码，好不好？
第二件是一个数组，这是 有能力的类型，我们的存储数据
要放置到数据结构中。
我们将暂缓对 链表元素现在
和刚开始的基本知识 哈希表来让你的头周围，
然后我们将可能打击 你的心一点点，当我们
结合数组和链表在一起。
>> 其基本思路虽然 是我们采取了一些数据。
我们通过运行数据 散列函数。
和因此数据被处理 它吐出一个数字，好不好？
然后用这个数字 我们只存储数据
我们要存储在 阵列在那个位置。
因此，例如，我们有可能 串该哈希表。
它有它10个元素，所以 我们可以在上面安装10串。
>> 比方说，我们要散列约翰。
因此，约翰的数据，我们要插入 这个哈希表的地方。
我们在哪里放呢？
那么通常与 阵列到目前为止，我们可能
将其放在数组位置0。
但是现在我们有了这个新的散列函数。
>> 而且，我们说，我们跑约翰 通过这个哈希函数
并且它吐出4。
那么这就是我们 会希望把约翰。
我们希望把约翰数组位置 4，因为如果我们散列约翰again--
让我们后来说，我们 要搜索，看看
如果约翰存在于该散列 table--所有我们需要做的
通过相同的散列运行它 功能，让4号出来，
并且能够找到John 立即在我们的数据结构。
这是相当不错的。
>> 比方说，我们现在做的这个 再次，我们要散列保罗。
我们想增加保 到这个哈希表。
比方说，我们这次运行 保罗通过散列函数，
生成的哈希码为6。
现在好了，我们可以把保罗 在阵列位置6。
如果我们需要仰视是否 保罗是该哈希表中，
我们需要做的就是运行保 通过散列函数再次
我们会得到6出来了。
>> 然后我们只要看看 在数组位置6。
保罗吗？
如果是这样，他的哈希表中。
保罗不是吗？
他不是哈希表所示。
这是非常简单的。
>> 现在，你如何定义一个散列函数？
那么真的没有限制的 可能的散列函数的数量。
其实有一些真的， 真正好的在互联网上。
有一些真的， 真正糟糕的在互联网上。
它也很容易 写一个坏的。
>> 是什么让一个很好的 散列函数，对不对？
好一个良好的散列函数应该 只使用被散列数据，
和所有的数据被散列。
所以，我们不希望使用anything-- 我们不会将任何东西
别人比数据等。
我们要使用的所有数据。
我们不希望只使用了一块 这一点，我们要使用它的全部。
哈希函数应该 同样是确定性的。
这意味着什么？
那么这意味着我们每一次 通过完全相同的数据片
到哈希函数，我们总是 得到相同的哈希码了。
如果我通过约翰进入 散列函数，我得到了4。
我应该能够做到一万 次，我会永远得到4。
因此，没有随机数有效 可以参与我们的散列tables--
在我们的哈希函数。
>> 散列函数也应 均匀地分布数据。
如果每次通过运行数据 哈希函数你得到的哈希码0，
这可能没那么大吧？
你可能想大 一系列的散列码。
同样的事情可以传播 从整个表。
并且也将是巨大的，如果真的 类似的数据，像约翰和乔纳森，
也许被摊开来衡量 在散列表中的不同位置。
这将是一个很好的优势。
>> 这里有一个散列函数的例子。
我前面写了这一个。
这不是一个特别 好的哈希函数
其原因并不真的 熊进入现在。
但是你看这是怎么回事呢？
好像我们在声明一个变量 称为sum并将其设置等于0。
然后，显然我在做什么 只要的strstr [J]不等于
反斜杠0。
我在做什么呢？
>> 这基本上只是一个 实施[的方法是什么？ STRL？]
并检测当你 达到串的结尾。
所以我没有真正 计算字符串的长度，
我只是用我的时候我打的 反斜杠字符0我知道
我已经到达字符串的结尾。
然后，我会继续 通过该字符串迭代，
加入的strstr [j]的概括，然后再在 到头来会返回一个总和模
HASH_MAX。
>> 基本上所有该散列 功能正在做的是加入了
所有的ASCII值 我的字符串，然后它的
返回一些哈希码 通过HASH_MAX改装成。
这可能是大小 我的数组，对不对？
我不希望是越来越哈希 如果我的数组大小为10的代码，
我不希望得到 出散列码11，12，
13，我不能把东西放进 阵列的那些位置，
这将是非法的。
我遭受分段错误。
>> 现在，这里是另一种快速的一边。
通常你可能不会 要编写自己的散列函数。
它实际上是一个有点 一门艺术，而不是一门科学。
而且有很多是进入他们。
互联网，就像我说的，是全 真正好的哈希函数，
你应该使用互联网 找到散列函数，因为它是真的
只是一种不必要的 浪费时间来创建自己的。
>> 你可以写简单的人 用于测试目的。
但是，当你真正要 开始散列数据和将其存储
到一个哈希表你 可能会想
使用中生成的一些功能 对你来说，存在于互联网上。
如果你只是确保 举你的源代码。
有没有理由 这里抄袭任何东西。
>> 计算机科学界是 肯定是增长的，真值
开源的，这真的很重要 举你的源代码，使人们
可以归属为 他们是工作
做对社会的利益。
所以，永远是sure-- 而不是只为哈希
功能，但一般当 使用代码从外部源，
始终引用源。
给予信贷是谁做的人 一些工作，所以你不必。
>> 好让我们重温这 哈希表一秒钟。
这是我们离开 我们关闭后插入
约翰和保罗到这个哈希表。
你在这里看到的一个问题？
您可能会看到两个。
但是，在特殊的，你 看到这个可能出现的问题？
>> 如果我凑林戈，它 事实证明，处理后
通过散列函数数据 林戈也产生了哈希码6。
我已经在有数据 hashcode--阵列位置6。
因此，它可能会成为一个位 现在我的问题，对不对？
>> 我们把这种冲突。
和碰撞发生当两个 数据块通过相同的散列运行
函数产生相同的哈希码。
想必大家仍然希望得到既 个数据到哈希表中，
否则我们也不会运行林戈 任意地通过散列函数。
我们大概是想获得 林戈到该阵列。
>> 我们是如何做到的，虽然，如果他 和保罗这两个产量哈希码6？
我们不希望覆盖保罗， 我们希望保罗在那里了。
因此，我们需要找到一种方式来获得 元素融入到哈希表
仍然保留我们的快速 插入和快速查找。
而对付它的方法之一是 做一些所谓的线性探测。
>> 使用这种方法，如果我们有一个 碰撞，好了，我们怎么办？
嗯，我们不能把他放在数组位置 6，或生成任何哈希码，
让我们把他的哈希码加1。
如果这完全让我们 把他放在哈希码加2。
这之中的好处，如果他 不完全是，我们认为他是，
而且我们要开始搜索， 也许我们不必走得太远。
或许我们不必以搜索 哈希表的所有n个元素。
也许我们需要搜索 他们夫妇。
>> 所以我们仍然趋向 即平均情况是接近1比
接近N，所以也许这会工作。
因此，让我们看看这个 可能工作在现实中。
而让我们看看，也许我们可以检测 这里可能出现的问题。
>> 比方说，我们凑巴特。
所以，现在我们要运行一个新的集 通过哈希函数的字符串，
我们通过哈希运行巴特 函数，我们得到哈希码6。
我们来看看，我们看到6 空的，所以我们可以把巴特那里。
>> 现在，我们哈希丽莎和 还生成散列码6。
现在好了，我们正在使用这种 线性探测，我们开始在6方法，
我们看到，6已满。
我们不能把丽莎6。
因此，我们下一步怎么走？
让我们去7。
7的空白，使作品。
所以，让我们把丽莎那里。
>> 现在，我们哈希荷马，我们得到7。
确定好我们知道，7的全 现在，所以我们不能把荷马那里。
因此，让我们去8。
8可用？
是啊，和8的接近7，因此，如果 我们要开始寻找我们
不会有走的太远。
因此，让我们把荷马在8。
>> 现在，我们哈希Maggie和 返回3，谢天谢地
我们能够只把马吉在那里。
我们没有做任何 那种探测的。
现在，我们哈希玛吉，和 玛吉也返回6。
>> 那么6已满，7已满，8已满， 9，没事感谢上帝，9是空的。
我可以把玛吉9。
我们已经能够看到，我们开始 有这样的问题，即现在我们
开始舒展的东西那种 对远离他们的哈希码。
与1的THETA，即平均 案件是恒定的时间，
开始变得有点缓慢 - 开始倾向于多一点
对n个THETA。
我们开始失去 利用哈希表。
>> 这个问题，我们刚才看到 一些所谓的集群。
而什么是真正不好 集群是，一旦你现在
有两个要素是并排 方面，它使得它更容易，
你有双倍的 偶然的机会，你要去
有另一个碰撞 与该集群，
和群集将由一个生长。
你会不断扩张 你具有碰撞可能性。
而最终它只是糟糕 作为不排序的数据在所有。
>> 另一个问题是，虽然我们 不过，到目前为止了这一点，
我们刚刚排序 了解什么是哈希表，
我们仍然只有空间10串。
如果我们想继续哈希 斯普林菲尔德的公民，
我们只能拿到其中10个在那里。
如果我们尝试添加一个11或12， 我们没有地方放了。
我们可能只是在不停的旋转 圈试图找到一个空白点，
我们也许卡住 在无限循环。
>> 因此，这种借给想法 一种叫做链接。
而这正是我们要带给 链表放回图片。
如果有什么，而不是仅仅存储 数据本身的阵列中，
该数组的每个元素可以 持多个数据？
嗯，这是没有意义的，对不对？
我们知道，一个数组只能 hold--一个阵列的每个元素
只能容纳一块 的该数据类型的数据。
>> 但是，如果该数据类型 是一个链表，对吧？
那么，如果每 数组的元素是
的指针的一个链表头？
然后我们可以建立 这些链表
和他们成长随意， 因为链表允许
我们扩大和缩小了很多 灵活不是一个数组一样。
因此，如果我们现在用的是什么， 我们利用这一点，对不对？
我们开始种植这些链 这些阵列单元。
>> 现在我们可以容纳无限 的数据量，或不无限的，
的任意量 数据，到我们的哈希表
而没有运行到 碰撞的问题。
我们还淘汰 集群做这个。
而同时我们知道，当我们插入 成一个链表，如果你还记得
从我们的视频链接列表，单 链表和双向链表，
这是一个固定时间操作。
我们只是增加了前面。
>> 而对于查查，还有我们所知道的 在链表查找
可能是一个问题，对不对？
我们必须通过搜索 它从开始到结束。
有没有随机 访问在一个链表。
但是，如果不是有一个链接 列表，查找会为O n个，
我们现在有10链表， 或1000链表，
现在它除以10，O n的， 或N邻除以1,000。
>> 虽然我们谈论 理论上约复杂性
不顾常数，在现实 世界这些事情实际上很重要，
对？
事实上，我们会发现 这种情况的发生
运行速度快10倍， 或快1000倍，
因为我们分配一个长 链跨越1000小型连锁店。
所以，每次我们有时间来搜索 通过这些链，我们可以之一
无视999链，我们不关心 约，只是寻找一个。
>> 这是对平均 是1000倍更短。
因此，我们仍然有几分 趋向于这种平均情况
的是恒定时间，但 只是因为我们正在利用
由一些巨大的常数因子分。
让我们来看看，这可能 实际上看起来虽然。
因此，这是哈希表，我们有 之前我们宣布一个哈希表
是能够存储10串。
我们不打算这样做了。
我们已经知道了 该方法的局限性。
现在，我们的哈希表将是 10个节点，指针数组
到链表的头。
>> 而现在它是空。
这10个三分球中的每一个为空。
有没有在我们的 哈希表现在。
>> 现在，让我们开始把一些 事情到这个哈希表。
而让我们看看这种方法是 将有利于我们一点点。
现在，让我们凑乔伊。
我们将运行字符串乔伊通过 散列函数和我们返回6。
那么我们现在做什么？
>> 现在好了，正与链表， 我们不是在与阵列。
当我们正在努力 用链表我们
知道我们需要动态地启动 分配空间和建筑链。
这就是那种how--这些都是核心 建立一个链表的元素。
因此，让我们动态 分配空间，容祖儿，
然后让我们把他加为链条。
>> 所以，现在看看我们所做的。
当我们哈希乔伊，我们得到了哈希码6。
现在指针数组位置6 指向的链接的列表的头部，
而现在它是唯一 链表元件。
并且在该节点 链表是乔伊。
>> 因此，如果我们需要仰视乔伊 后来，我们只需再次散列乔伊，
我们再次拿到6，因为我们的 散列函数是确定性的。
然后我们开始在头 链表指出
由数组位置 6，我们可以遍历
跨越，试图找到乔伊。
如果我们建立我们 有效哈希表，
而我们的散列函数有效 很好地分发数据，
平均每个那些链接 在每个数组位置列表
将1/10如果尺寸我们 刚它作为一个巨大的
链表中的一切。
>> 如果我们分发巨额链接 在10个链接列表清单
每个列表将大小的1/10。
就这样，10次快 进行搜索。
因此，让我们再次做到这一点。
现在，让我们凑罗斯。
>> 而我们说罗斯，当我们做到这一点 我们得到的哈希码为2。
现在好了，我们动态地分配 新的节点，我们把罗斯在那个节点，
我们现在说的数组位置 2，而不是指向空，
指向的链接头 名单的唯一节点是罗斯。
我们可以这样做一个更多的时间，我们 可以散列Rachel和获得哈希码4。
malloc的一个新的节点，把瑞秋 节点，并说一个数组位置
4现在指向头部 链表的
唯一的元素恰好是瑞秋。
>> OK，但如果发生了什么 我们有一个碰撞？
让我们来看看我们是如何处理冲突 采用独立链接方法。
让我们凑菲比。
我们得到的哈希码6。
在前面的例子中，我们只是 存储阵列中的字符串。
这是一个问题。
>> 我们不希望给揍 乔伊，我们已经
可见，我们可以得到一些集群 如果我们试图和问题的步骤
通过和探头。
但是，如果我们只是种 这种对待同样的道理，对不对？
这就像将一个元素 到的一个链表的头部。
让菲比的只是malloc的空间。
>> 我们会说菲比的下一个指针指向 到旧头链表，
然后6只指向 链接列表的新掌门人。
而现在看，我们已经在改变了菲比。
现在，我们可以存储两个 与hashCode 6个元素，
我们没有任何问题。
>> 这几乎是所有 还有就是链接。
而且链接是绝对 该方法是
将是最有效的你，如果 你是存储在一个哈希表中的数据。
但这种组合 数组和链表
在一起，以形成一个哈希表真 极大地提高你的能力
来存储大量的数据，和 非常迅速和有效地搜索
通过该数据。
>> 但还有一个更 数据结构在那里
甚至可能会有点 在保障方面更好
我们的插入，缺失，和 仰望倍甚至更快。
我们会看到，在尝试视频。
我是道格·劳埃德，这是CS50。