[音乐播放] 道格·劳埃德：现在你 知道了很多关于阵列， 你也知道了很多关于链表。 我们已经讨论 利弊，我们 讨论了链表 可以越做越小， 但他们需要更多的大小。 数组是更直接 用，但他们限制在尽可能多 因为我们要设置的大小 在阵列中，最开始 然后我们坚持了下来。 

但是，这是，我们已经差不多 用尽我们所有的主题 有关链接列表和数组。 或者我们？ 也许我们可以做一些事情 更具创造性。 而那种贷出的 哈希表的想法。 

因此，在哈希表中，我们要尝试 结合的阵列与一个链表。 我们将采取优势 阵列，如随机访问， 能够只是去阵列 单元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。