﻿[Script Info] Title: [Events] Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text Dialogue: 0,0:00:00.14,0:00:02.59,Default,,0000,0000,0000,,No, it definitely will not always succeed. Dialogue: 0,0:00:02.59,0:00:05.98,Default,,0000,0000,0000,,There are some nice probabilistic guarantees about how often it will succeed Dialogue: 0,0:00:05.98,0:00:08.44,Default,,0000,0000,0000,,depending on the size and number of the hash tables, Dialogue: 0,0:00:08.44,0:00:12.41,Default,,0000,0000,0000,,but the easy counterexample is to say that, well, here we have 2 hash tables. Dialogue: 0,0:00:12.41,0:00:16.72,Default,,0000,0000,0000,,If we had 3 items, each of which had the same H1 and H2-- Dialogue: 0,0:00:16.72,0:00:20.56,Default,,0000,0000,0000,,so for instance if we had 3 items where H1 and H2 were both 0, Dialogue: 0,0:00:20.56,0:00:23.36,Default,,0000,0000,0000,,there's no possible way that we can fit them into the hash table, Dialogue: 0,0:00:23.36,0:00:27.10,Default,,0000,0000,0000,,because we only have 2 slots where any hash function is equal to 0. Dialogue: 0,0:00:27.10,0:00:31.53,Default,,0000,0000,0000,,So in practice we choose a certain number of iterations, and we continue to iterate, Dialogue: 0,0:00:31.53,0:00:35.91,Default,,0000,0000,0000,,trying to fill up this hash table until we decide that we've done too many iterations. Dialogue: 0,0:00:35.91,0:00:40.81,Default,,0000,0000,0000,,And so if that's the case then we just stop, we choose new hash functions, and we start over. Dialogue: 0,0:00:40.81,0:00:44.35,Default,,0000,0000,0000,,And again, there's very nice probabilistic guarantees about how often this is going to finish. Dialogue: 0,0:00:44.35,0:00:47.00,Default,,0000,0000,0000,,So in the research that inspired this work, Dialogue: 0,0:00:47.00,0:00:49.19,Default,,0000,0000,0000,,the guarantee that we tried to use Dialogue: 0,0:00:49.19,0:00:55.02,Default,,0000,0000,0000,,was that we could guarantee that it was going to fail less than 1 out of every million times. Dialogue: 0,0:00:55.02,0:00:58.51,Default,,0000,0000,0000,,So once we construct the hash table, the lookup procedure is really simple. Dialogue: 0,0:00:58.51,0:01:02.01,Default,,0000,0000,0000,,We're going to calculate all the hash functions for the item that we want to look up. Dialogue: 0,0:01:02.01,0:01:07.24,Default,,0000,0000,0000,,So for instance, if I want to look up item B, I calculate item B's hash functions. Dialogue: 0,0:01:07.24,0:01:10.95,Default,,0000,0000,0000,,Here hash function 1 is equal to 0, and hash function 2 is equal to 1. Dialogue: 0,0:01:10.95,0:01:13.31,Default,,0000,0000,0000,,So what I'm going to do is I'm going to look in all tables Dialogue: 0,0:01:13.31,0:01:16.42,Default,,0000,0000,0000,,using the particular hash functions until I find what I'm looking for. Dialogue: 0,0:01:16.42,0:01:20.98,Default,,0000,0000,0000,,So first, I'm going to look in table 1, and I know that I'm going to look in slot 0. Dialogue: 0,0:01:20.98,0:01:24.03,Default,,0000,0000,0000,,Here I look in slot 0, and I say, "Wait a second, that's not B." Dialogue: 0,0:01:24.03,0:01:28.92,Default,,0000,0000,0000,,So then I have to go to table 2, look and see that its hash value is equal to 1, Dialogue: 0,0:01:28.92,0:01:33.02,Default,,0000,0000,0000,,so I'll look in slot 1 in table 2, and I'll say, "Ah, there's B!" Dialogue: 0,0:01:33.02,0:01:35.31,Default,,0000,0000,0000,,I've now found the value that I'm looking for. Dialogue: 0,0:01:35.31,0:01:38.33,Default,,0000,0000,0000,,Now if we don't find it in any of these locations, it's just not in the has table. Dialogue: 0,0:01:38.33,0:01:41.54,Default,,0000,0000,0000,,Now the nice part here is that this is a constant time lookup. Dialogue: 0,0:01:41.54,0:01:44.07,Default,,0000,0000,0000,,It just requires T lookups, and T is a constant. Dialogue: 0,0:01:44.07,0:01:46.38,Default,,0000,0000,0000,,It might be 2, it might be 3, and so on. Dialogue: 0,0:01:46.38,0:01:48.11,Default,,0000,0000,0000,,This is different than chaining. Dialogue: 0,0:01:48.11,0:01:49.95,Default,,0000,0000,0000,,Chaining has a variable time lookup. Dialogue: 0,0:01:49.95,0:01:52.32,Default,,0000,0000,0000,,It depends on how many items are in the bucket, Dialogue: 0,0:01:52.32,0:01:55.12,Default,,0000,0000,0000,,and if we have many items in the bucket, and we have to look all the way to the end, Dialogue: 0,0:01:55.12,0:01:57.17,Default,,0000,0000,0000,,it can potentially take a very long time, Dialogue: 0,0:01:57.17,0:01:59.46,Default,,0000,0000,0000,,whereas we can guarantee exactly how much work, Dialogue: 0,0:01:59.46,0:02:03.00,Default,,0000,0000,0000,,and it's a constant amount of work to look up any item in these hash tables.