大家好！数据结构与算法这一节，我们继续第十章检索的学习。 Hello, everyone. We continue to take up chapter 10th retrieval to study data structure and algorithms.
我们讨论散列表，特别是 We will discuss the hash table, especially
散列表中当发生同义词的冲突碰撞的时候， 我们一些处理方法. how to handle the collisions when some keys are hashed into the same bucket.
这里是两种，开散列和闭散列， 这两种方法。 There are two strategies are described below: open hashing and closed hashing.
开散列方法， 就是我们把这样的代散列的这些元素，我一次来插入到这样的一个散列表。 In the methods known as open hashing, all elements will be inserted into a hash table.
当发生碰撞的时候，我们在这个相应的一个位子，拉出链来。 We’ll pull a chain in the corresponding position when collisions occur.
把这些同义词，存在这个链里面。 We put these synonyms in the chain.
我们可以看到，插入第110的时候， 这边有一个碰撞， 我们会拉出一个链。 We noticed that a collision occurred there when we inserted 110 into the table, so we’ll pull a chain.
然后再插入第62，还有95的时候， 都会在这个标号为7的槽里面， 拉出一个链。 Then, when 62 and 65 are inserted, both of them are in the 7th slot, so we’ll pull a chain again.
我们要注意一下，在这个散列表里面， 我们是把这个有效的元素直接就存在它的这个基地址的位置。 We notice that the effective elements are stored in the base address of their positions directly in this hash table.
因此，对于这样的空槽的元素，一定要做一下标记就是跟我们 这些数值，能够区分开来。 So, we must make marks to distinguish these empty slot element from the actual values.
例如，我们如果是说这些元素都为非负的， 我空槽为-1或者说为一个比较大的一个数叫无穷。 For example, if we suppose that these elements are non-negative, we can use -1 or infinity to represent the empty slots.
拉链法其实在实际应用中，是一种非常有效的一种方法。 Open hashing is a very effective method in practice.
因为对于我们在散列表的大小M 和我散列表里面元素个数n来说， 往往M/n是在两倍以上。 That is because for the hash table size(M) and for the number of elements in the hash table(n), M is two times more than N in most cases.
发生冲突碰撞的情况，是非常少的。 So the collision are rare.
而且我拉出了这个同义词表，也不会很长。 And the list we pull to store the synonyms won’t be long.
平均情况下，散列方法的代价就是θ （1）的。 这个同义词表，我们还非常好操作处理。 So the average cost is θ (1), and we can handle the Synonym list well.
但是，在散列的这些相关的讨论里面，我们往往讨论闭散列方法 比较多。时因为闭散列方法，我们有更多的一些情况须要讨论。 However, we often discuss closed hashing methods in the discussion about hash. That is because more cases need discussing in the closed hashing methods.
但是在大家实际应用中，可以尽量的使用开散列方法。 However, we’d better use open hashing in practice.
我们来看这个闭散列方法， 它的思想就是说， 我们发生冲突碰撞的时候，我不要在外面拉链。 Let’s look at the closing hashing. The idea is we don’t pull a chain outside when collisions occur.
我这个散列表本身就是很空的。刚才我们说基本上有一半以上的是空。 We can see that the hash table is quite empty。Basically, more than half is empty as mentioned before.
一旦发生碰撞，我能不能够用这个碰撞的 地址附近的一些，这种空的槽，来陈放这个同义词？ Once collision occurs, can we use some of empty slots near the collision address to store the synonyms?
而且，这个查找的策略，跟我们当时插入的时候，这样的一个探测的， 策略是一样的，这样就保证我们能合理的放进去， 而且有效的找出来。 And the search strategy is same as insert strategy to ensure that we can reasonably fit, but also effectively find out.
因此，如果这个K，它的基地址为d0。 Supposed that the base address of this key is d0,
我们后面， 就有么一系列的探测的这个位置。这个 探测位置，我们也可以说是它的探测序列。 We’ll probe a series of positions which can also be regarded as the probe sequence near this address.
根据这个探测序列，我 当我存的时候是在先试探 d0，如果碰撞就在试探d1，再看d2等等，这些位置。 If I want to store the elements, I probe address d0, next d1 if collision occurs before, next d2… and so on.
查找的时候，我们也是这么一个序列。 The same sequence will be probed when searching.
当然在处理这个闭散列的时候，往往我们要求在这个散列表里面要有足够的空槽。这个空槽其实很多时候是作为我们 来探测的时候，说明这个探测序列结束的 这么一个标记。 Of course enough empty slots are required when we handle closing hash. In fact, slots are often used to be marks of the end of the probe sequence while searching.
就是我插入的时候，如果有空槽， 我就可以在这个位置插。 It means that I can insert the element if there is a slot.
如果在查找的时候，后面还有这个空槽，而且我前面还一直没 找到我这个关键码。就是说明整个这个同义词值表都找过了，都找不到。 就是不存在这个记录。， But if I haven’t found the key before I meet a slot, it shows that the key isn’t in the synonym list. In other words, the record doesn’t exist.
因此，我们是有一些策略的。而且对这个探测序列， 也是有长度的限制。，如果我在这个整个散列表里面， 整个给它翻一遍，就是成了一个θ（M）的代价。 Hence, we have some strategies and limitation on the length of a probe sequence. Because it will cost θ(M) if we travel all elements in a hash table.
这个M往往都大于n，就不能够达到我们 散列函数一个θ（1）的这么一个有效代价。 M is more than n in most cases, so effective cost θ(1) won’t be achieved.
闭散列里面一个重要的问题就是聚集。 An important issue about closed hash is clustering.
这个聚集，它最主要的就是说不同的这个关键值。 么它，会有一些这样的查找的这么一个探测序列。 这些探测序列，它慢慢慢慢的就缠在一起了， ，就会产生聚集。 Clustering means that some different probe sequences will be wrapped together.
聚集里面，其实有两类。 一类，是基本聚集，也就是说基地址，是不同的。 但是，因为你的探测序列，它有规律，大家慢慢就聚在一起。 There are two types of clustering. One is the primary clustering, which means the basic addresses of keys are different. Elements coalesce with others because probe sequences are regular.
另外还有一种就是二次聚集。这个二次聚集就是 它的基地址是相同的，也就是说是同义词值表。 我后面，如果你这个探测序列，跟这个关键码是 无，无关的，而只是跟这个位置有关的这个函数，它必然会聚在一起。 The other type is secondary clustering. Secondary clustering means that different keys have the same basic address. In other words, they are in a synonym list. Hence, if the probe sequence is just associated with the basic address and has nothing to do with the keys, they will gather together.
我们来看下面几种，这种闭散列的方法。 它们都会有这样的聚集的问题。 Let’s have a look at some closing hashing methods below. They all have clustering problems.
线性探测，这是一种最简单的一个探测的方法。 Linear probing is the simplest methods.
这个方法就是从我这个基地址之后， 我在以步长为1，来看后续的这个存储单元是不是空。是的话，我就可以插进去。 如果不是，我就不能插进去。 We’ll see the follow-up of the storage unit is empty or not in step 1. The element can be inserted if the unit is empty, otherwise it can’t.
第i个这样一个um, 步长， 它就是i这个值，因此，我们在基地址是d， 我下面再加d+1,d+2，逐个的往下面去看。 The value of the ith step um is i. so the base address is d, and then d+1,d+2, one after another.
线性探测，它的优点是我明显的可以便利整个散列表的空间， 但是，我们前面也说到过，我其实没有拿一个 同义词表， 我也能够达到这么一个在整个 这个散列表里面是到处个都看一遍才找到。 The advantage of linear probing is to use the whole space of the hash table conveniently. But as mentioned before, we may travel the whole hash table even if the element isn’t in a synonym list.
这样的话，它的效率会非常的低的。 Its efficiency is very low in that case.
因此，这个其实也没有什么特别多的关系。 Hence, it doesn’t matter.
我们看在线性探测的这样的一个情况下， ，对于这么一个空间每15的这么一个散列表，然后我们的 散列函数，是，对key,除13取余数。 Let’s take a look at linear probing in such a situation where the size of the hash table is 15 and the hash function is key % 13.
我们看到这样的一个表，我当前的情况下，对每一个槽， 假设它接受一个新的这个元素的概率，是 均等的，已经都是1/15。 In this case, for each slot, assuming that the probability of accepting a new element is 1/15.
，对于我们这样的一个标号为11的槽， 它除了接受它自己占了一个位置，基地址的这个关键码以外， 它有可能这个标号为10的这个槽，如果它有一个元素来插入的话， 因为这里已经有36占据了所以它的这个 探测的下一个位置就是11。 For slot 11 , besides accepting its own base address, it can accepting an element whose base address is 10 because number 36 has taken up slot 10 and its next probe position is slot 11.
因此这两个累加起来， ，下一条记录放在标号为11的槽里面的这个概率就是2/15。 而比较夸张的就是标号为7的占了一个槽， 它，除了自己占了一个基地址，可以 存着这样的一个关键码以外，它前面的这些元素 槽12，13，14，然后还有0，1，2，3，4，5，6。 这些槽里面它如果是这个关键码， 运送到相应的槽。 So, the two adding up, the probability of next record put in slot 11 is 2/15. Exaggeratedly, besides taken up by the keys whose base address is 7, slot 7 can be taken up by those elements whose base addresses are 12, 13, 14, 0, 1, 2, 3, 4, 5 and 6, in case of their slot have had elements already.
然后当它们去看的时候就是这个基地址，都已经被占了。 然后它以一个线性探测逐个往下找， 最后都是找到这样的标号为7的槽。 When we looked at the base address, it has been taken up. Then we searched for the empty slot by linear probing one by one. Finally, we found slot 7.
因此， 它的这个累积起来有可能存入数据的这样的概率就是 11/15。 So, gathering up all results, the probability of store an element in this slot is 11/15.
其实刚才我们也 看到了这些基地址槽，它们的这个探测序列 就被扭在了一起，都是缠在一起分不开的。 As we can see, the probe sequences of these base address slots were wrapped together and inseparable.
我们想如果你别样的一个一个这样步长去试探，我给它跳得 远一点，我就是，以一个常数c 来乘于这个i就是我探测的这样的一个位置。 这样的话， 就会使得它们能够分散一些。 If we probe the location stepped by a constant c multiple i instead of 1, the elements will be scattered open.
这里大家注意就是c跟M，尽量取一个互素的一个值。其实就是取c 为一个比较小的一个素数就可以了，3到5，这些。 Noting that try to make c and M are relatively prime. In fact, taking the c a relatively small prime, such as 3 and 5, is OK.
我们来看这个，改进了以后的这个线性探测。 ，这个改进的话，假设k1和k2，它们的基地址，分别是3和5。 我c取2，。 Let’s look at the improved linear probing. Assuming that the base addresses of k1 and k2 is 3 and 5. Let c = 2.
你可以看到，恩，这个，3,5,7,9，然后，这个5,7,9， 它们在5这个地方会后以后，还是缠在一起，因此，它的改进并不是很理想 我还有一种改进的，我让它跳的更远一些，我可能就是 让它是i的平方，这样的一个探测，这就是2 次探测，这个2次探测，而且，不光是往后面，我往前面也可以试 这样的话，我就是1的平方，-1的平方，2的平方，-2的 平方，这样的就是i平方和-i的平方这样交错，来 进行， ，我们再来看一个例子， 对于这个表长为13的这么一个表，K1的基地址是3，k2的基地址，是2， 我们采用这种方法可以看到，K1的探测序列，和K2的探测 序列，虽然在2这个位置，它们是有 所重叠的，但是在之后，它还是能够分开 OK, let’s look at another example. For a list which size is 13, assuming that the base addresses of K1 and K2 are 3 and 2, the probe sequences of K1 and K2 are overlapping in slot 2, but they are able to separate since then in this way.
所以，2次探测它对于这种基本序列，它还是能够很好的解决的，我们再来看， 还有一种方法也非常好，而且，它能够避免，我们这个2次探测，它每次还要来，一个i的平方这么一个计算 So, quadratic probing can handle these basic sequences well. However, there is another good method and it can avoid calculating the square of i in quadratic probing.
这个方法就是伪随机的探测序列，产生一个随机 序列，这个随机序列的这个值，我就放到一个数组里 头，而且我这个随机序列的长度理论上我是可以，为M-1 ，这样的一个序列， The method is pseudo random probe sequence. We generate a random sequence and put it in an array. The length of the random sequence is M – 1 theoretically.
但是，其实我们用不了么长，我们应该限制这样的探测序列的长度，产生这个n个数的伪随机序列 But we doesn’t need to use such a long sequence in fact. We should limit the length of the sequence and generate a pseudo random sequence of n numbers.
我们可以用这么一个函数，就是，首先把这个1到n这几个数，存到数组 里面，然后，我对这个数组里面的 每一位，我都去跟我产生的一个随机的一个下标位的数据，去交换，总共交换n 次， We can use a function to store 1 to n in an array first and for each number swap it and a subscript generated randomly.
我来看这么一个例子长度还是为 13，然后，我的这个伪随机序列的前3个值 ，是2,3,7，然后，我两个关键码，它的基地址 映射到4和 2，根据你这个伪随机序列，我产生的探测序列 就是4,6,7,11,还有这个2,4,5,9 Let’s look at an example in which the length of the hash table is still 13. Assuming that the first three numbers of the pseudo random sequence is 2, 3 and 7 and there are two keys of which the base addresses is 4 and 2 respectively. So, according to the pseudo random sequence, the two probe sequences are 4, 6, 7, 11 and 2, 4, 5, 9.
我们可以看到，虽然它们在4 这个位置有所重叠，但是后面都分开了，因为这个伪随机序列 的话它是没有规律的，我们可以打破 这样的线性探测的这样的就是挨个挨个往下的 这个规律，它能达到，很好的消除基本聚集的效果， We can see that they overlap in slot 4, but they are separate since then because the pseudo random sequence is irregular. It can eliminate primary clustering effectively.
我们再来看2级， 聚集，这个基本聚集，是基地址不同的这样的位置，我的这样的探测序列， 我如果是聚在一起，这是基本 的聚集，但是有一种情况就是我的基地址也一样， 也就是，同义词表， The basic aggregation is for Different base address location. The probe sequence gathered together is the basic aggregation. But another situation is that the base address is the same, that is, Synonymy thesaurus.
我这个散列函数，把我们映射到同一个基地址，但其实我是不同的 关键码，我如果是这个探测序列，像，我们前面介绍的这些探测序列， 它都是跟我这个基地址相关的，这样一个函数， 而跟我们的这样的key本身，没有 关系， The hash function map different keys to the same base address. The probe sequences we talked before are all relative to the base address instead of the key.
这样的话，它如果采用前面的方法， 我们不能够避免这两个同义词表，它们的探测序列， 它会完全纠在一起了， 这样的话，会导致我们的检索性能，下降 So, if we use the old methods, we can’t avoid the tangle of two synonym lists’ probe sequences, which can lead to the decrease of the retrieval performance.
这种情况，我们就是要采用一种，叫做 双散列的方法，来处理，双散列函数，其实很简单就是，对这个key， 我再应用一下这个H2这个散列 函数，而，我每一个这个 探测的这样的一个步长，也就是第i次的这个探测 我就乘以i这个系数，我们的探测序列函数就是我d，是H1 计算出来的基地址，第i这样的一个探测的位置就是d+i*H2(Key) 然后再对这个M取模 We use a method called double hashing to handle this situation. To put it simply, for each key, we use another hash function H2 again. In other words, the step of the ith probing is i multiples. Assuming the base address calculated by hash function H1 is d, the ith probing location will be (d+i*H2(Key))%M.
，来看一下双散列的一些性质，首先就是 ，我们在这样的一个探测的过程，其实， 刚才有个，探测的这么一个函数，我们看一看 Then，let’s have a look at the properties of double hashing. In the process of detecting，we use the probing function mentioned before.
可以看到，如果是d它的基地址H1 (Key)=d，这个基地址发生冲突，我们在试的时候就是d+H2(key) d+2*H2(key)等等，一直往下的去 As we can see, if the base address of a key and the H1(Key) = d, it is in conflict. So, when we try for the second time, we try d+H2(key) ,d+2*H2(key)…until no conflict existed any more.
，来探测，我们这里注意，H2 (key)，尽量跟M互素，这样是会比较好的， By the way, if H2(key) and M are relatively prime，it will be much better.
然后，这样使得它的这个 ，整个这个探测序列在散列表里面分布的 比较均匀，有了这个双散列的这样的一个方法，我们就 可以避免这样的二次聚集的情况的发生， In this case, the probing sequence is relatively even and linear distributed. With the method of double hash list, we can avoid the occurrence of secondary clustering
但是，因为这个双散列，我每次对这个Key，都要进行一个计算就是比我们原 来的些散列方法，它的计算量其实是要大一倍的， However, if we use double hashing, we have to calculate the ‘key’ every time, which doubles computation cost.
我们看一下这个H2(key)的选择方法，当然有各种各样的， 选择方法了大家也可以去发明自己的方法，例如，我如果是这个M，也就是散列表 的大小，它是一个任意的一个数，我如果是H1(key)，我 是用的除余法就是Key模以一个P,这个P， 是小于M的一个最大的素数，这个时候，我就取 H2让它是模 q而且加1，q，是小于p的最大素数， The way to choose ‘H2(key)’ varies. You can either choose the current functions or invent your own solutions. For example, assuming that the M(size of hash list) is known, which can be any number. We can use Divide-and-mod method to generate H1(key).We calculate Key % P, where P is the largest prime under M. Then, we choose H2 as ‘H2(x) = x % q + 1’, where q is the largest prime under p.
我们加1的目的是什么？因为，如果你只是取这个 你可能得到这个H2是0，加1，我们就避免它是0的情况， 也就说，我必然这个探测序列，是往后面能够继续移动的， Why did we add 1? Because with 1 added, you avoid the case H2 equal to 0. That is to say, our probing sequence can move forward all the way.
最后，给大家留两个思考 ，首先就是，插入同义词的时候，如果用开散列的方法， 我们会拉出一个同义词表，这个同义词表 你怎么去组织，你是用栈式的方法来组织，还是用链的方法来组织，还是用 普通的这个线性表，你随便插或者是说，你还进行排序 In the end of class, I leave two questions for you to think. First one, when inserting synonyms, we will stretch out a synonym-list. How to organize the list? By stack? By linked list? By simple linear table? Random inserting or sorting firstly?
还有就是双散列函数，这里面，有一个H1(key)，然后还有一个 H2(key),这个H1(key)就是它的一个计算基地址的这么一个函数，H2 (key)就是我们在用来计算步长的这个函数，这两个东西 之间有什么关系，你能不能够设计，一套比较好的这个 双散列的方法？谢谢大家 Second one, in double hashing, H1(key) is used for base address calculation, while H2(key) for step calculation. Can you figure out the relationship between them? In advance, can you design a better solution for double hashing? Thank you for listening.