1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:01,900 [音乐播放] 3 00:00:01,900 --> 00:00:05,710 4 00:00:05,710 --> 00:00:09,150 >> 道格·劳埃德:现在你 知道了很多关于阵列, 5 00:00:09,150 --> 00:00:11,610 你也知道了很多关于链表。 6 00:00:11,610 --> 00:00:13,650 我们已经讨论 利弊,我们 7 00:00:13,650 --> 00:00:16,620 讨论了链表 可以越做越小, 8 00:00:16,620 --> 00:00:18,630 但他们需要更多的大小。 9 00:00:18,630 --> 00:00:22,359 数组是更直接 用,但他们限制在尽可能多 10 00:00:22,359 --> 00:00:24,900 因为我们要设置的大小 在阵列中,最开始 11 00:00:24,900 --> 00:00:26,910 然后我们坚持了下来。 12 00:00:26,910 --> 00:00:30,470 >> 但是,这是,我们已经差不多 用尽我们所有的主题 13 00:00:30,470 --> 00:00:33,040 有关链接列表和数组。 14 00:00:33,040 --> 00:00:34,950 或者我们? 15 00:00:34,950 --> 00:00:37,720 也许我们可以做一些事情 更具创造性。 16 00:00:37,720 --> 00:00:40,950 而那种贷出的 哈希表的想法。 17 00:00:40,950 --> 00:00:46,680 >> 因此,在哈希表中,我们要尝试 结合的阵列与一个链表。 18 00:00:46,680 --> 00:00:49,520 我们将采取优势 阵列,如随机访问, 19 00:00:49,520 --> 00:00:53,510 能够只是去阵列 单元4或数组元素8 20 00:00:53,510 --> 00:00:55,560 而不必遍历整个。 21 00:00:55,560 --> 00:00:57,260 这是相当快的,对不对? 22 00:00:57,260 --> 00:01:00,714 >> 但是,我们也希望有我们的数据 结构能够增大和缩小。 23 00:01:00,714 --> 00:01:02,630 我们不需要,我们不 要进行限制。 24 00:01:02,630 --> 00:01:04,588 我们希望能够 添加和删​​除的东西 25 00:01:04,588 --> 00:01:08,430 很容易,而如果你还记得, 是与一个阵列很复杂。 26 00:01:08,430 --> 00:01:11,650 我们可以把这种 新事物的哈希表。 27 00:01:11,650 --> 00:01:15,190 >> 如果正确实施, 样的,我们正在做 28 00:01:15,190 --> 00:01:18,150 两个数据的优点 你已经看到了结构, 29 00:01:18,150 --> 00:01:19,880 数组和链表。 30 00:01:19,880 --> 00:01:23,070 插入可以开始 趋向THETA 1。 31 00:01:23,070 --> 00:01:26,207 西塔我们还没有真正讨论过, 但THETA只是平均情况下, 32 00:01:26,207 --> 00:01:27,540 什么实际将要发生。 33 00:01:27,540 --> 00:01:29,680 你不会总是会 有最坏的情况下, 34 00:01:29,680 --> 00:01:32,555 而你并不总是有 在最好的情况下,有啥 35 00:01:32,555 --> 00:01:33,900 一般情况下? 36 00:01:33,900 --> 00:01:36,500 >> 那么平均的插入 为哈希表 37 00:01:36,500 --> 00:01:39,370 可以开始接近恒定的时间。 38 00:01:39,370 --> 00:01:41,570 和删除可以得到 接近恒定的时间。 39 00:01:41,570 --> 00:01:44,440 和查找可以得到 接近恒定的时间。 40 00:01:44,440 --> 00:01:48,600 That's--我们没有一个数据 结构尚未能做到这一点, 41 00:01:48,600 --> 00:01:51,180 所以这已经听上去 像一个非常伟大的事情。 42 00:01:51,180 --> 00:01:57,010 我们真的减轻了 每个自身的缺点。 43 00:01:57,010 --> 00:01:59,160 >> 要达到这种性能 升级虽然,我们 44 00:01:59,160 --> 00:02:03,580 需要重新思考我们如何加入 数据到该结构。 45 00:02:03,580 --> 00:02:07,380 具体来说,我们要的 数据本身告诉我们 46 00:02:07,380 --> 00:02:09,725 它应该在的结构。 47 00:02:09,725 --> 00:02:12,850 如果我们再需要看它是否在 结构,如果我们需要找到它, 48 00:02:12,850 --> 00:02:16,610 我们想看看数据 再次,并能够有效地, 49 00:02:16,610 --> 00:02:18,910 使用数据,随机访问它。 50 00:02:18,910 --> 00:02:20,700 只是通过查看 数据,我们应该有 51 00:02:20,700 --> 00:02:25,890 那里正是我们的想法 会发现它在散列表中。 52 00:02:25,890 --> 00:02:28,770 >> 散列现在的缺点 表是,他们是真的 53 00:02:28,770 --> 00:02:31,770 非常糟糕的订购或排序数据。 54 00:02:31,770 --> 00:02:34,970 而事实上,如果你开始 用它们来订货或排序 55 00:02:34,970 --> 00:02:37,990 数据你失去所有的 优点以前 56 00:02:37,990 --> 00:02:40,710 有在插入和删除的条款。 57 00:02:40,710 --> 00:02:44,060 的时间变得更接近 THETA的n,我们已经基本上 58 00:02:44,060 --> 00:02:45,530 退步成一个链表。 59 00:02:45,530 --> 00:02:48,850 因此,我们只希望使用哈希 如果我们不关心表 60 00:02:48,850 --> 00:02:51,490 数据是否被排序。 61 00:02:51,490 --> 00:02:54,290 对于上下文中 你会使用他们在CS50 62 00:02:54,290 --> 00:02:58,900 你可能不关心 该数据排序。 63 00:02:58,900 --> 00:03:03,170 >> 所以一个哈希表是一个组合 的两个不同的片 64 00:03:03,170 --> 00:03:04,980 与我们熟悉。 65 00:03:04,980 --> 00:03:07,930 第一个是一个函数,它 我们通常所说的哈希函数。 66 00:03:07,930 --> 00:03:11,760 并且散列函数是要 返回一些非负整数,其 67 00:03:11,760 --> 00:03:14,870 我们通常所说的哈希码,好不好? 68 00:03:14,870 --> 00:03:20,230 第二件是一个数组,这是 有能力的类型,我们的存储数据 69 00:03:20,230 --> 00:03:22,190 要放置到数据结构中。 70 00:03:22,190 --> 00:03:24,310 我们将暂缓对 链表元素现在 71 00:03:24,310 --> 00:03:27,810 和刚开始的基本知识 哈希表来让你的头周围, 72 00:03:27,810 --> 00:03:30,210 然后我们将可能打击 你的心一点点,当我们 73 00:03:30,210 --> 00:03:32,920 结合数组和链表在一起。 74 00:03:32,920 --> 00:03:35,590 >> 其基本思路虽然 是我们采取了一些数据。 75 00:03:35,590 --> 00:03:37,860 我们通过运行数据 散列函数。 76 00:03:37,860 --> 00:03:41,980 和因此数据被处理 它吐出一个数字,好不好? 77 00:03:41,980 --> 00:03:44,890 然后用这个数字 我们只存储数据 78 00:03:44,890 --> 00:03:48,930 我们要存储在 阵列在那个位置。 79 00:03:48,930 --> 00:03:53,990 因此,例如,我们有可能 串该哈希表。 80 00:03:53,990 --> 00:03:57,350 它有它10个元素,所以 我们可以在上面安装10串。 81 00:03:57,350 --> 00:03:59,320 >> 比方说,我们要散列约翰。 82 00:03:59,320 --> 00:04:02,979 因此,约翰的数据,我们要插入 这个哈希表的地方。 83 00:04:02,979 --> 00:04:03,770 我们在哪里放呢? 84 00:04:03,770 --> 00:04:05,728 那么通常与 阵列到目前为止,我们可能 85 00:04:05,728 --> 00:04:07,610 将其放在数组位置0。 86 00:04:07,610 --> 00:04:09,960 但是现在我们有了这个新的散列函数。 87 00:04:09,960 --> 00:04:13,180 >> 而且,我们说,我们跑约翰 通过这个哈希函数 88 00:04:13,180 --> 00:04:15,417 并且它吐出4。 89 00:04:15,417 --> 00:04:17,500 那么这就是我们 会希望把约翰。 90 00:04:17,500 --> 00:04:22,050 我们希望把约翰数组位置 4,因为如果我们散列约翰again-- 91 00:04:22,050 --> 00:04:23,810 让我们后来说,我们 要搜索,看看 92 00:04:23,810 --> 00:04:26,960 如果约翰存在于该散列 table--所有我们需要做的 93 00:04:26,960 --> 00:04:30,310 通过相同的散列运行它 功能,让4号出来, 94 00:04:30,310 --> 00:04:33,929 并且能够找到John 立即在我们的数据结构。 95 00:04:33,929 --> 00:04:34,720 这是相当不错的。 96 00:04:34,720 --> 00:04:36,928 >> 比方说,我们现在做的这个 再次,我们要散列保罗。 97 00:04:36,928 --> 00:04:39,446 我们想增加保 到这个哈希表。 98 00:04:39,446 --> 00:04:42,070 比方说,我们这次运行 保罗通过散列函数, 99 00:04:42,070 --> 00:04:44,600 生成的哈希码为6。 100 00:04:44,600 --> 00:04:47,340 现在好了,我们可以把保罗 在阵列位置6。 101 00:04:47,340 --> 00:04:50,040 如果我们需要仰视是否 保罗是该哈希表中, 102 00:04:50,040 --> 00:04:53,900 我们需要做的就是运行保 通过散列函数再次 103 00:04:53,900 --> 00:04:55,830 我们会得到6出来了。 104 00:04:55,830 --> 00:04:57,590 >> 然后我们只要看看 在数组位置6。 105 00:04:57,590 --> 00:04:58,910 保罗吗? 106 00:04:58,910 --> 00:05:00,160 如果是这样,他的哈希表中。 107 00:05:00,160 --> 00:05:01,875 保罗不是吗? 108 00:05:01,875 --> 00:05:03,000 他不是哈希表所示。 109 00:05:03,000 --> 00:05:05,720 这是非常简单的。 110 00:05:05,720 --> 00:05:07,770 >> 现在,你如何定义一个散列函数? 111 00:05:07,770 --> 00:05:11,460 那么真的没有限制的 可能的散列函数的数量。 112 00:05:11,460 --> 00:05:14,350 其实有一些真的, 真正好的在互联网上。 113 00:05:14,350 --> 00:05:17,560 有一些真的, 真正糟糕的在互联网上。 114 00:05:17,560 --> 00:05:21,080 它也很容易 写一个坏的。 115 00:05:21,080 --> 00:05:23,760 >> 是什么让一个很好的 散列函数,对不对? 116 00:05:23,760 --> 00:05:27,280 好一个良好的散列函数应该 只使用被散列数据, 117 00:05:27,280 --> 00:05:29,420 和所有的数据被散列。 118 00:05:29,420 --> 00:05:32,500 所以,我们不希望使用anything-- 我们不会将任何东西 119 00:05:32,500 --> 00:05:35,560 别人比数据等。 120 00:05:35,560 --> 00:05:37,080 我们要使用的所有数据。 121 00:05:37,080 --> 00:05:39,830 我们不希望只使用了一块 这一点,我们要使用它的全部。 122 00:05:39,830 --> 00:05:41,710 哈希函数应该 同样是确定性的。 123 00:05:41,710 --> 00:05:42,550 这意味着什么? 124 00:05:42,550 --> 00:05:46,200 那么这意味着我们每一次 通过完全相同的数据片 125 00:05:46,200 --> 00:05:50,040 到哈希函数,我们总是 得到相同的哈希码了。 126 00:05:50,040 --> 00:05:52,870 如果我通过约翰进入 散列函数,我得到了4。 127 00:05:52,870 --> 00:05:56,110 我应该能够做到一万 次,我会永远得到4。 128 00:05:56,110 --> 00:06:00,810 因此,没有随机数有效 可以参与我们的散列tables-- 129 00:06:00,810 --> 00:06:02,750 在我们的哈希函数。 130 00:06:02,750 --> 00:06:05,750 >> 散列函数也应 均匀地分布数据。 131 00:06:05,750 --> 00:06:09,700 如果每次通过运行数据 哈希函数你得到的哈希码0, 132 00:06:09,700 --> 00:06:11,200 这可能没那么大吧? 133 00:06:11,200 --> 00:06:14,600 你可能想大 一系列的散列码。 134 00:06:14,600 --> 00:06:17,190 同样的事情可以传播 从整个表。 135 00:06:17,190 --> 00:06:23,210 并且也将是巨大的,如果真的 类似的数据,像约翰和乔纳森, 136 00:06:23,210 --> 00:06:26,320 也许被摊开来衡量 在散列表中的不同位置。 137 00:06:26,320 --> 00:06:28,750 这将是一个很好的优势。 138 00:06:28,750 --> 00:06:31,250 >> 这里有一个散列函数的例子。 139 00:06:31,250 --> 00:06:33,150 我前面写了这一个。 140 00:06:33,150 --> 00:06:35,047 这不是一个特别 好的哈希函数 141 00:06:35,047 --> 00:06:37,380 其原因并不真的 熊进入现在。 142 00:06:37,380 --> 00:06:41,040 但是你看这是怎么回事呢? 143 00:06:41,040 --> 00:06:44,420 好像我们在声明一个变量 称为sum并将其设置等于0。 144 00:06:44,420 --> 00:06:50,010 然后,显然我在做什么 只要的strstr [J]不等于 145 00:06:50,010 --> 00:06:52,490 反斜杠0。 146 00:06:52,490 --> 00:06:54,870 我在做什么呢? 147 00:06:54,870 --> 00:06:57,440 >> 这基本上只是一个 实施[的方法是什么? STRL?] 148 00:06:57,440 --> 00:06:59,773 并检测当你 达到串的结尾。 149 00:06:59,773 --> 00:07:02,480 所以我没有真正 计算字符串的长度, 150 00:07:02,480 --> 00:07:05,640 我只是用我的时候我打的 反斜杠字符0我知道 151 00:07:05,640 --> 00:07:07,185 我已经到达字符串的结尾。 152 00:07:07,185 --> 00:07:09,560 然后,我会继续 通过该字符串迭代, 153 00:07:09,560 --> 00:07:15,310 加入的strstr [j]的概括,然后再在 到头来会返回一个总和模 154 00:07:15,310 --> 00:07:16,200 HASH_MAX。 155 00:07:16,200 --> 00:07:18,700 >> 基本上所有该散列 功能正在做的是加入了 156 00:07:18,700 --> 00:07:23,450 所有的ASCII值 我的字符串,然后它的 157 00:07:23,450 --> 00:07:26,390 返回一些哈希码 通过HASH_MAX改装成。 158 00:07:26,390 --> 00:07:29,790 这可能是大小 我的数组,对不对? 159 00:07:29,790 --> 00:07:33,160 我不希望是越来越哈希 如果我的数组大小为10的代码, 160 00:07:33,160 --> 00:07:35,712 我不希望得到 出散列码11,12, 161 00:07:35,712 --> 00:07:38,690 13,我不能把东西放进 阵列的那些位置, 162 00:07:38,690 --> 00:07:39,790 这将是非法的。 163 00:07:39,790 --> 00:07:42,130 我遭受分段错误。 164 00:07:42,130 --> 00:07:45,230 >> 现在,这里是另一种快速的一边。 165 00:07:45,230 --> 00:07:48,470 通常你可能不会 要编写自己的散列函数。 166 00:07:48,470 --> 00:07:50,997 它实际上是一个有点 一门艺术,而不是一门科学。 167 00:07:50,997 --> 00:07:52,580 而且有很多是进入他们。 168 00:07:52,580 --> 00:07:55,288 互联网,就像我说的,是全 真正好的哈希函数, 169 00:07:55,288 --> 00:07:58,470 你应该使用互联网 找到散列函数,因为它是真的 170 00:07:58,470 --> 00:08:03,230 只是一种不必要的 浪费时间来创建自己的。 171 00:08:03,230 --> 00:08:05,490 >> 你可以写简单的人 用于测试目的。 172 00:08:05,490 --> 00:08:08,323 但是,当你真正要 开始散列数据和将其存储 173 00:08:08,323 --> 00:08:10,780 到一个哈希表你 可能会想 174 00:08:10,780 --> 00:08:14,580 使用中生成的一些功能 对你来说,存在于互联网上。 175 00:08:14,580 --> 00:08:17,240 如果你只是确保 举你的源代码。 176 00:08:17,240 --> 00:08:21,740 有没有理由 这里抄袭任何东西。 177 00:08:21,740 --> 00:08:25,370 >> 计算机科学界是 肯定是增长的,真值 178 00:08:25,370 --> 00:08:28,796 开源的,这真的很重要 举你的源代码,使人们 179 00:08:28,796 --> 00:08:30,670 可以归属为 他们是工作 180 00:08:30,670 --> 00:08:32,312 做对社会的利益。 181 00:08:32,312 --> 00:08:34,020 所以,永远是sure-- 而不是只为哈希 182 00:08:34,020 --> 00:08:37,270 功能,但一般当 使用代码从外部源, 183 00:08:37,270 --> 00:08:38,299 始终引用源。 184 00:08:38,299 --> 00:08:43,500 给予信贷是谁做的人 一些工作,所以你不必。 185 00:08:43,500 --> 00:08:46,720 >> 好让我们重温这 哈希表一秒钟。 186 00:08:46,720 --> 00:08:48,780 这是我们离开 我们关闭后插入 187 00:08:48,780 --> 00:08:53,300 约翰和保罗到这个哈希表。 188 00:08:53,300 --> 00:08:55,180 你在这里看到的一个问题? 189 00:08:55,180 --> 00:08:58,410 您可能会看到两个。 190 00:08:58,410 --> 00:09:02,240 但是,在特殊的,你 看到这个可能出现的问题? 191 00:09:02,240 --> 00:09:06,770 >> 如果我凑林戈,它 事实证明,处理后 192 00:09:06,770 --> 00:09:14,000 通过散列函数数据 林戈也产生了哈希码6。 193 00:09:14,000 --> 00:09:16,810 我已经在有数据 hashcode--阵列位置6。 194 00:09:16,810 --> 00:09:22,000 因此,它可能会成为一个位 现在我的问题,对不对? 195 00:09:22,000 --> 00:09:23,060 >> 我们把这种冲突。 196 00:09:23,060 --> 00:09:26,460 和碰撞发生当两个 数据块通过相同的散列运行 197 00:09:26,460 --> 00:09:29,200 函数产生相同的哈希码。 198 00:09:29,200 --> 00:09:32,850 想必大家仍然希望得到既 个数据到哈希表中, 199 00:09:32,850 --> 00:09:36,330 否则我们也不会运行林戈 任意地通过散列函数。 200 00:09:36,330 --> 00:09:40,870 我们大概是想获得 林戈到该阵列。 201 00:09:40,870 --> 00:09:46,070 >> 我们是如何做到的,虽然,如果他 和保罗这两个产量哈希码6? 202 00:09:46,070 --> 00:09:49,520 我们不希望覆盖保罗, 我们希望保罗在那里了。 203 00:09:49,520 --> 00:09:52,790 因此,我们需要找到一种方式来获得 元素融入到哈希表 204 00:09:52,790 --> 00:09:56,550 仍然保留我们的快速 插入和快速查找。 205 00:09:56,550 --> 00:10:01,350 而对付它的方法之一是 做一些所谓的线性探测。 206 00:10:01,350 --> 00:10:04,170 >> 使用这种方法,如果我们有一个 碰撞,好了,我们怎么办? 207 00:10:04,170 --> 00:10:08,580 嗯,我们不能把他放在数组位置 6,或生成任何哈希码, 208 00:10:08,580 --> 00:10:10,820 让我们把他的哈希码加1。 209 00:10:10,820 --> 00:10:13,670 如果这完全让我们 把他放在哈希码加2。 210 00:10:13,670 --> 00:10:17,420 这之中的好处,如果他 不完全是,我们认为他是, 211 00:10:17,420 --> 00:10:20,850 而且我们要开始搜索, 也许我们不必走得太远。 212 00:10:20,850 --> 00:10:23,900 或许我们不必以搜索 哈希表的所有n个元素。 213 00:10:23,900 --> 00:10:25,790 也许我们需要搜索 他们夫妇。 214 00:10:25,790 --> 00:10:30,680 >> 所以我们仍然趋向 即平均情况是接近1比 215 00:10:30,680 --> 00:10:34,280 接近N,所以也许这会工作。 216 00:10:34,280 --> 00:10:38,010 因此,让我们看看这个 可能工作在现实中。 217 00:10:38,010 --> 00:10:41,460 而让我们看看,也许我们可以检测 这里可能出现的问题。 218 00:10:41,460 --> 00:10:42,540 >> 比方说,我们凑巴特。 219 00:10:42,540 --> 00:10:45,581 所以,现在我们要运行一个新的集 通过哈希函数的字符串, 220 00:10:45,581 --> 00:10:48,460 我们通过哈希运行巴特 函数,我们得到哈希码6。 221 00:10:48,460 --> 00:10:52,100 我们来看看,我们看到6 空的,所以我们可以把巴特那里。 222 00:10:52,100 --> 00:10:55,410 >> 现在,我们哈希丽莎和 还生成散列码6。 223 00:10:55,410 --> 00:10:58,330 现在好了,我们正在使用这种 线性探测,我们开始在6方法, 224 00:10:58,330 --> 00:10:59,330 我们看到,6已满。 225 00:10:59,330 --> 00:11:00,990 我们不能把丽莎6。 226 00:11:00,990 --> 00:11:02,090 因此,我们下一步怎么走? 227 00:11:02,090 --> 00:11:03,280 让我们去7。 228 00:11:03,280 --> 00:11:04,610 7的空白,使作品。 229 00:11:04,610 --> 00:11:06,510 所以,让我们把丽莎那里。 230 00:11:06,510 --> 00:11:10,200 >> 现在,我们哈希荷马,我们得到7。 231 00:11:10,200 --> 00:11:13,380 确定好我们知道,7的全 现在,所以我们不能把荷马那里。 232 00:11:13,380 --> 00:11:14,850 因此,让我们去8。 233 00:11:14,850 --> 00:11:15,664 8可用? 234 00:11:15,664 --> 00:11:18,330 是啊,和8的接近7,因此,如果 我们要开始寻找我们 235 00:11:18,330 --> 00:11:20,020 不会有走的太远。 236 00:11:20,020 --> 00:11:22,860 因此,让我们把荷马在8。 237 00:11:22,860 --> 00:11:25,151 >> 现在,我们哈希Maggie和 返回3,谢天谢地 238 00:11:25,151 --> 00:11:26,650 我们能够只把马吉在那里。 239 00:11:26,650 --> 00:11:29,070 我们没有做任何 那种探测的。 240 00:11:29,070 --> 00:11:32,000 现在,我们哈希玛吉,和 玛吉也返回6。 241 00:11:32,000 --> 00:11:39,560 >> 那么6已满,7已满,8已满, 9,没事感谢上帝,9是空的。 242 00:11:39,560 --> 00:11:41,600 我可以把玛吉9。 243 00:11:41,600 --> 00:11:45,280 我们已经能够看到,我们开始 有这样的问题,即现在我们 244 00:11:45,280 --> 00:11:48,780 开始舒展的东西那种 对远离他们的哈希码。 245 00:11:48,780 --> 00:11:52,960 与1的THETA,即平均 案件是恒定的时间, 246 00:11:52,960 --> 00:11:56,560 开始变得有点缓慢 - 开始倾向于多一点 247 00:11:56,560 --> 00:11:58,050 对n个THETA。 248 00:11:58,050 --> 00:12:01,270 我们开始失去 利用哈希表。 249 00:12:01,270 --> 00:12:03,902 >> 这个问题,我们刚才看到 一些所谓的集群。 250 00:12:03,902 --> 00:12:06,360 而什么是真正不好 集群是,一旦你现在 251 00:12:06,360 --> 00:12:09,606 有两个要素是并排 方面,它使得它更容易, 252 00:12:09,606 --> 00:12:11,480 你有双倍的 偶然的机会,你要去 253 00:12:11,480 --> 00:12:13,516 有另一个碰撞 与该集群, 254 00:12:13,516 --> 00:12:14,890 和群集将由一个生长。 255 00:12:14,890 --> 00:12:19,640 你会不断扩张 你具有碰撞可能性。 256 00:12:19,640 --> 00:12:24,470 而最终它只是糟糕 作为不排序的数据在所有。 257 00:12:24,470 --> 00:12:27,590 >> 另一个问题是,虽然我们 不过,到目前为止了这一点, 258 00:12:27,590 --> 00:12:30,336 我们刚刚排序 了解什么是哈希表, 259 00:12:30,336 --> 00:12:31,960 我们仍然只有空间10串。 260 00:12:31,960 --> 00:12:37,030 如果我们想继续哈希 斯普林菲尔德的公民, 261 00:12:37,030 --> 00:12:38,790 我们只能拿到其中10个在那里。 262 00:12:38,790 --> 00:12:42,619 如果我们尝试添加一个11或12, 我们没有地方放了。 263 00:12:42,619 --> 00:12:45,660 我们可能只是在不停的旋转 圈试图找到一个空白点, 264 00:12:45,660 --> 00:12:49,000 我们也许卡住 在无限循环。 265 00:12:49,000 --> 00:12:51,810 >> 因此,这种借给想法 一种叫做链接。 266 00:12:51,810 --> 00:12:55,790 而这正是我们要带给 链表放回图片。 267 00:12:55,790 --> 00:13:01,300 如果有什么,而不是仅仅存储 数据本身的阵列中, 268 00:13:01,300 --> 00:13:04,471 该数组的每个元素可以 持多个数据? 269 00:13:04,471 --> 00:13:05,970 嗯,这是没有意义的,对不对? 270 00:13:05,970 --> 00:13:09,280 我们知道,一个数组只能 hold--一个阵列的每个元素 271 00:13:09,280 --> 00:13:12,930 只能容纳一块 的该数据类型的数据。 272 00:13:12,930 --> 00:13:16,750 >> 但是,如果该数据类型 是一个链表,对吧? 273 00:13:16,750 --> 00:13:19,830 那么,如果每 数组的元素是 274 00:13:19,830 --> 00:13:22,790 的指针的一个链表头? 275 00:13:22,790 --> 00:13:24,680 然后我们可以建立 这些链表 276 00:13:24,680 --> 00:13:27,120 和他们成长随意, 因为链表允许 277 00:13:27,120 --> 00:13:32,090 我们扩大和缩小了很多 灵活不是一个数组一样。 278 00:13:32,090 --> 00:13:34,210 因此,如果我们现在用的是什么, 我们利用这一点,对不对? 279 00:13:34,210 --> 00:13:37,760 我们开始种植这些链 这些阵列单元。 280 00:13:37,760 --> 00:13:40,740 >> 现在我们可以容纳无限 的数据量,或不无限的, 281 00:13:40,740 --> 00:13:44,170 的任意量 数据,到我们的哈希表 282 00:13:44,170 --> 00:13:47,760 而没有运行到 碰撞的问题。 283 00:13:47,760 --> 00:13:50,740 我们还淘汰 集群做这个。 284 00:13:50,740 --> 00:13:54,380 而同时我们知道,当我们插入 成一个链表,如果你还记得 285 00:13:54,380 --> 00:13:57,779 从我们的视频链接列表,单 链表和双向链表, 286 00:13:57,779 --> 00:13:59,070 这是一个固定时间操作。 287 00:13:59,070 --> 00:14:00,710 我们只是增加了前面。 288 00:14:00,710 --> 00:14:04,400 >> 而对于查查,还有我们所知道的 在链表查找 289 00:14:04,400 --> 00:14:05,785 可能是一个问题,对不对? 290 00:14:05,785 --> 00:14:07,910 我们必须通过搜索 它从开始到结束。 291 00:14:07,910 --> 00:14:10,460 有没有随机 访问在一个链表。 292 00:14:10,460 --> 00:14:15,610 但是,如果不是有一个链接 列表,查找会为O n个, 293 00:14:15,610 --> 00:14:19,590 我们现在有10链表, 或1000链表, 294 00:14:19,590 --> 00:14:24,120 现在它除以10,O n的, 或N邻除以1,000。 295 00:14:24,120 --> 00:14:26,940 >> 虽然我们谈论 理论上约复杂性 296 00:14:26,940 --> 00:14:30,061 不顾常数,在现实 世界这些事情实际上很重要, 297 00:14:30,061 --> 00:14:30,560 对? 298 00:14:30,560 --> 00:14:33,080 事实上,我们会发现 这种情况的发生 299 00:14:33,080 --> 00:14:36,610 运行速度快10倍, 或快1000倍, 300 00:14:36,610 --> 00:14:41,570 因为我们分配一个长 链跨越1000小型连锁店。 301 00:14:41,570 --> 00:14:45,090 所以,每次我们有时间来搜索 通过这些链,我们可以之一 302 00:14:45,090 --> 00:14:50,290 无视999链,我们不关心 约,只是寻找一个。 303 00:14:50,290 --> 00:14:53,220 >> 这是对平均 是1000倍更短。 304 00:14:53,220 --> 00:14:56,460 因此,我们仍然有几分 趋向于这种平均情况 305 00:14:56,460 --> 00:15:01,610 的是恒定时间,但 只是因为我们正在利用 306 00:15:01,610 --> 00:15:03,730 由一些巨大的常数因子分。 307 00:15:03,730 --> 00:15:05,804 让我们来看看,这可能 实际上看起来虽然。 308 00:15:05,804 --> 00:15:08,720 因此,这是哈希表,我们有 之前我们宣布一个哈希表 309 00:15:08,720 --> 00:15:10,270 是能够存储10串。 310 00:15:10,270 --> 00:15:11,728 我们不打算这样做了。 311 00:15:11,728 --> 00:15:13,880 我们已经知道了 该方法的局限性。 312 00:15:13,880 --> 00:15:20,170 现在,我们的哈希表将是 10个节点,指针数组 313 00:15:20,170 --> 00:15:22,120 到链表的头。 314 00:15:22,120 --> 00:15:23,830 >> 而现在它是空。 315 00:15:23,830 --> 00:15:26,170 这10个三分球中的每一个为空。 316 00:15:26,170 --> 00:15:29,870 有没有在我们的 哈希表现在。 317 00:15:29,870 --> 00:15:32,690 >> 现在,让我们开始把一些 事情到这个哈希表。 318 00:15:32,690 --> 00:15:35,440 而让我们看看这种方法是 将有利于我们一点点。 319 00:15:35,440 --> 00:15:36,760 现在,让我们凑乔伊。 320 00:15:36,760 --> 00:15:40,210 我们将运行字符串乔伊通过 散列函数和我们返回6。 321 00:15:40,210 --> 00:15:41,200 那么我们现在做什么? 322 00:15:41,200 --> 00:15:44,090 >> 现在好了,正与链表, 我们不是在与阵列。 323 00:15:44,090 --> 00:15:45,881 当我们正在努力 用链表我们 324 00:15:45,881 --> 00:15:49,790 知道我们需要动态地启动 分配空间和建筑链。 325 00:15:49,790 --> 00:15:54,020 这就是那种how--这些都是核心 建立一个链表的元素。 326 00:15:54,020 --> 00:15:57,670 因此,让我们动态 分配空间,容祖儿, 327 00:15:57,670 --> 00:16:00,390 然后让我们把他加为链条。 328 00:16:00,390 --> 00:16:03,170 >> 所以,现在看看我们所做的。 329 00:16:03,170 --> 00:16:06,440 当我们哈希乔伊,我们得到了哈希码6。 330 00:16:06,440 --> 00:16:11,790 现在指针数组位置6 指向的链接的列表的头部, 331 00:16:11,790 --> 00:16:14,900 而现在它是唯一 链表元件。 332 00:16:14,900 --> 00:16:18,350 并且在该节点 链表是乔伊。 333 00:16:18,350 --> 00:16:22,300 >> 因此,如果我们需要仰视乔伊 后来,我们只需再次散列乔伊, 334 00:16:22,300 --> 00:16:26,300 我们再次拿到6,因为我们的 散列函数是确定性的。 335 00:16:26,300 --> 00:16:30,400 然后我们开始在头 链表指出 336 00:16:30,400 --> 00:16:33,360 由数组位置 6,我们可以遍历 337 00:16:33,360 --> 00:16:35,650 跨越,试图找到乔伊。 338 00:16:35,650 --> 00:16:37,780 如果我们建立我们 有效哈希表, 339 00:16:37,780 --> 00:16:41,790 而我们的散列函数有效 很好地分发数据, 340 00:16:41,790 --> 00:16:45,770 平均每个那些链接 在每个数组位置列表 341 00:16:45,770 --> 00:16:50,110 将1/10如果尺寸我们 刚它作为一个巨大的 342 00:16:50,110 --> 00:16:51,650 链表中的一切。 343 00:16:51,650 --> 00:16:55,670 >> 如果我们分发巨额链接 在10个链接列表清单 344 00:16:55,670 --> 00:16:57,760 每个列表将大小的1/10。 345 00:16:57,760 --> 00:17:01,432 就这样,10次快 进行搜索。 346 00:17:01,432 --> 00:17:02,390 因此,让我们再次做到这一点。 347 00:17:02,390 --> 00:17:04,290 现在,让我们凑罗斯。 348 00:17:04,290 --> 00:17:07,540 >> 而我们说罗斯,当我们做到这一点 我们得到的哈希码为2。 349 00:17:07,540 --> 00:17:10,630 现在好了,我们动态地分配 新的节点,我们把罗斯在那个节点, 350 00:17:10,630 --> 00:17:14,900 我们现在说的数组位置 2,而不是指向空, 351 00:17:14,900 --> 00:17:18,579 指向的链接头 名单的唯一节点是罗斯。 352 00:17:18,579 --> 00:17:22,660 我们可以这样做一个更多的时间,我们 可以散列Rachel和获得哈希码4。 353 00:17:22,660 --> 00:17:25,490 malloc的一个新的节点,把瑞秋 节点,并说一个数组位置 354 00:17:25,490 --> 00:17:27,839 4现在指向头部 链表的 355 00:17:27,839 --> 00:17:31,420 唯一的元素恰好是瑞秋。 356 00:17:31,420 --> 00:17:33,470 >> OK,但如果发生了什么 我们有一个碰撞? 357 00:17:33,470 --> 00:17:38,560 让我们来看看我们是如何处理冲突 采用独立链接方法。 358 00:17:38,560 --> 00:17:39,800 让我们凑菲比。 359 00:17:39,800 --> 00:17:41,094 我们得到的哈希码6。 360 00:17:41,094 --> 00:17:44,010 在前面的例子中,我们只是 存储阵列中的字符串。 361 00:17:44,010 --> 00:17:45,980 这是一个问题。 362 00:17:45,980 --> 00:17:48,444 >> 我们不希望给揍 乔伊,我们已经 363 00:17:48,444 --> 00:17:51,110 可见,我们可以得到一些集群 如果我们试图和问题的步骤 364 00:17:51,110 --> 00:17:52,202 通过和探头。 365 00:17:52,202 --> 00:17:54,660 但是,如果我们只是种 这种对待同样的道理,对不对? 366 00:17:54,660 --> 00:17:57,440 这就像将一个元素 到的一个链表的头部。 367 00:17:57,440 --> 00:18:00,220 让菲比的只是malloc的空间。 368 00:18:00,220 --> 00:18:04,764 >> 我们会说菲比的下一个指针指向 到旧头链表, 369 00:18:04,764 --> 00:18:07,180 然后6只指向 链接列表的新掌门人。 370 00:18:07,180 --> 00:18:10,150 而现在看,我们已经在改变了菲比。 371 00:18:10,150 --> 00:18:14,210 现在,我们可以存储两个 与hashCode 6个元素, 372 00:18:14,210 --> 00:18:17,170 我们没有任何问题。 373 00:18:17,170 --> 00:18:20,147 >> 这几乎是所有 还有就是链接。 374 00:18:20,147 --> 00:18:21,980 而且链接是绝对 该方法是 375 00:18:21,980 --> 00:18:27,390 将是最有效的你,如果 你是存储在一个哈希表中的数据。 376 00:18:27,390 --> 00:18:30,890 但这种组合 数组和链表 377 00:18:30,890 --> 00:18:36,080 在一起,以形成一个哈希表真 极大地提高你的能力 378 00:18:36,080 --> 00:18:40,550 来存储大量的数据,和 非常迅速和有效地搜索 379 00:18:40,550 --> 00:18:41,630 通过该数据。 380 00:18:41,630 --> 00:18:44,150 >> 但还有一个更 数据结构在那里 381 00:18:44,150 --> 00:18:48,700 甚至可能会有点 在保障方面更好 382 00:18:48,700 --> 00:18:51,920 我们的插入,缺失,和 仰望倍甚至更快。 383 00:18:51,920 --> 00:18:55,630 我们会看到,在尝试视频。 384 00:18:55,630 --> 00:18:58,930 我是道格·劳埃德,这是CS50。 385 00:18:58,930 --> 00:19:00,214