大家好， Hello, everyone.
数据结构与算法这一讲我们学习第十章检索。 We take up Chapter 10retrieval to study data structure and algorithms.
散列的最后内容就是我们来实现一个闭散列的字典。 The last part of hash is to implement a dictionary of closed hashing.
我们对散列方法进行效率分析。 The efficiency of hashing will be analyzed.
字典是一种特殊的集合，也就是说有一些元素，这个元素其实是一个key value对。 The dictionary is one special set which contains some elements. Every element is one dyad of key values.
也就是说这个key就是我们待检的这些词或者是关键字，这里我们用一种闭散列的方法来实现字典。 In other word, this “key” is the word for search or the key words. Here, we employ the closed hashing to implement the dictionary.
这个定义就是有这个散列表它其实是一个这样的很大的数组。这个数组，有它的特定的这么一个大小长度。还有就是我们当前里面有效的这个元素个数。另外我们要特别定义一种空槽的一种 值。为我们后面的比较，提供一个基准。还有就是我们要定义散列函数以及相应的这个探测的序列。也就是说探测序列我们采用什么样的步长的这个函数。还有就是对这个字典的一个初始化以及相应的一些插入、删除，还有查找这些的操作。 We identify: first, one hash table which is one large array with certain length; second, the number of valid elements; third, one value set as “empty slot” for further comparison; fourth, hash function and its probe sequence, in other word, we may use a function at what step size; last, the initialization of the dictionary and relevant operations including insertion, deletion and search.
我们来看这个插入算法。 Now we focus on the insertion algorithm.
对于一个闭散列表，插入的过程，首先就是根据我这个散列函数，找到一个基地址， For a closed hashing table, the process of insertion is firstly finding a base address according to my hash function.
我看一下基地址如果是空的，我就可以插入，否则的话，我就沿着这个探测序列，继续往后面找，找到一个空的位置，插入待插入的元素。 If the base address is empty, then I can insert; or I continue searching along the probe sequence until I find one empty position for insertion.
在这个过程中，如果有重复的关键码，我就不允许它插入。 In this process, I will not allow insertion when there are repeated key codes.
我们来看这个插入的算法框架。 We take a look at this insertion algorithm framework.
首先就是我得到这么一个基地址我这么一个position指针，我从基地址出发，开始往后面来看。我这个循环，就是判断一下，这个当前的这个position指针是不是一个空槽？ First, I have one base address and one position indicator. I begin from base address and look forward. By this circulation, I judge whether the current position indicator is one empty slot.
如果不空的情况下，我就是在判断，当前这个position这个位置的值，它是不是跟我待插入的这个key是一样的。 If not, I judge whether the value of this position is equal with the key for insertion.
如果相同的话我就报告说这次插入失败，我不允许重复关键码，否则，我这个步长就往后面加1， If so, I report an insertion failure. I don’t allow repeating key code, or I add one to the step size.
我看这个探测序列里面，下一位是哪一个位置。我根据这个探测函数再加上这个基地址就是我探测序列里面的下一个要查找的这样的一个位置。 In this probe sequence, I look for the next position. This hash function together with the base address is the next position I’m looking for in the probe sequence.
继续这一层的循环，再来一直找，找到一个空的一个可以插入的位置，我们插入这个元素，我就成功地完成了一个插入的操作。 Continue the circulation in this layer and search until we find an empty position where we can insert the element. Thus we complete an operation of insertion.
检索算法跟插入是非常类似的。它的探测序列也是一样的。 Retrieval algorithm is very similar to the insertion. The probe sequence is also the same.
我们这个检索的过程就是在基地址，以及它的探测序列里面去找，有没有这个元素，如果有，就成功返回。 We do the retrieval in the base address and its probe sequence to see whether there is a certain element. If so, we return successfully.
如果是没有的话，一直就找到了我们整个探测序列里面的尾部。这个尾部，其实是用空槽来代替的。我们就表示检索失败， If not, we search until the end of the probe, which is actually replaces by empty slot. Then we claim the retrieval is unsuccessful.
我们来看这个检索算法的框架。前面是类似首先，定位这个基地址，以及起始的这样的一个比较的position。 We now pay attention to the framework of the retrieval algorithm. Similarly, we locate the base address and the original position for comparison.
看一下这个position这个当前的元素，它是不是空？，如果不空的情况下，我再看是不是跟我待查找的这样的一个元素值是相同的。如果是，我们就找到了这个元素而且返回真。 See whether the element in the position is empty. If not, check whether it is equal with the element I’m looking for. If so, we thus find this element and return true.
否则的话，我探测序列再往下面继续去找，我们一直找到这个元素，或者是说找到了某一个空槽，也就是探测序列已经结束了，我们返回假。 If not, I continuing searching along the probe sequence until I find such an element or I come to the empty slot, which means the end of probe sequence, and I return to false.
在这样的一个闭散列表里面，我们不能够直接就删除这个元素。因为这个元素它可能处在很多个探测序列里面。 In a closed hash table, we can’t delete the element directly, because this element may appear in many probe sequences.
你把他删掉了以后，这些探测序列就都是在这个位置，就变成了空。 If you delete it, the probe sequences will become empty in this position.
但其实后面它可能还需要有更多的这个探测的位置。 But actually, the probe sequence may need this position more than once.
这样的话，我们就会在这个地方，断掉。因此删除只能是做一个特殊的标记。 If so, the probe sequence will be cut in this place. So deletion is only marked as a special mark.
我们来看一下这个删除的例子。 We may look at this example.
对这么一个长为13 的散列表，假设这个K1和K2 们的基地址分别是2和6，如果我们采用二次探测的方法，如果我们删除这个位置6所在的这个值，这个时候，我们不能够直接把它删掉，因为这是它的一个基地址。 For a hash table at the length of 13, suppose the base addresses of K1 and K2 are 2 and 6 respectively, if we use quadratic probing, we delete the value in the position 6. But actually at this time, we can’t delete it directly, because it’s a base address.
其实将来要检索，跟这个6的基地址相关的一些其他的值的时候，假设我有另外一个key,比如说 K3 的基地址也是6，它的这样的一个探测序列会是去从这个6，再看7，再看5。 If we need search the values related to the base address 6, suppose I have another key and the base address of K3 is also 6, the probe sequence will be from 6, to 7, then to 5.
这个6被删掉以后变成一个空槽，它就会判断说，哎，我找不到这个元素。其实，这个K3可能在 7 或者在 5 这个位置。 But if 6 is deleted to be an empty slot, the probe sequence will judge that it can’t find the element. In fact, the K3 may be in the position of 7 or 5.
另外就是我也不能够用这个，K2的探测序列里面的最后个元素来代替槽6所在的这样的一个元素。 What’s more, I can’t use the last element in the probe sequence K2 to replace the element in the slot 6.
我们来看这个K2的探测序列是6，7，5，10，2。 See, the probe sequence K2 is 6, 7, 5, 10, 2.
我们假设探测序列里面最后个元素就是在下标为2的个槽里面。 We suppose the last element of the probe sequence is in the slot subscripted as 2.
如果我把这个K2来代替下标6所在的这个位置的值，这个时候，这个K2就变成了一个空槽。我们下次要检K1的时候的基地址就是2检到这儿是个空。 If I replace the value in the subscript position 6 with K2, K2 will become an empty slot. Next time we search for the base address of K1, we get a zero here.
其实，这个K1有可能是放在这个位置3或者是位置1里面，就是说，我原来这样一个K1 的探测序列，因为这个K2的某一个关键码，被移走了，整个这个探测序列就被打断了。 Actually, this K1 may be placed in the position 3 or 1, that is to say, my original probe sequence K1 is cut because of the deletion of one key code in K2.
因此，我们删除的时候，只能够在这个原位置填一个墓碑，不能进行其他的一些移动，或者是直接删除这样的操作。墓碑不同于，空单元，也不同于有效值的情况。 Therefore, we can only leave a headstone in the original place when we delete, rather than other movements or operations like deletion. Headstones are different from both blank cells and valid values.
我们来看删除的算法。当然我们是要基于这个墓碑标记的。 We then look at the deletion algorithm. Of course, it is based on the headstone marks.
首先也还是找到这个基地址，我们从这个基地址出发，来比较这个当前位置是不是空。 First, we also find this base address, from which we compare whether the current position is empty or not.
如果不空的情况下，我们再来看这个当前位置这个元素是不是我们给定的，要删除的这个值。如果是的话，我们就把这个位置，标记为墓碑，我们把这个删除的这个值的结果返回。 If it’s not empty, we see whether the element in the position is to be deleted as we set. If so, we mark this position as a headstone and return with the deleted value.
否者就是如果我们现在当前这个位置的值还不等于我们待删的这个元素，我就继续在这个探测序列里面，往下面找，一直到找到这个待删的元素或者是找到整个这个探测序列里面的一个空位置，就表示这个元素是不存在这个散列表里面的。也就是说，删除是个失败的操作。 If the value in the current position is unequal with the element for deletion, I go on searching in the probe sequence until I find it or an empty position. The latter means the element is not in this hash table—the deletion is an unsuccessful operation.
我们来看这个带墓碑的情况下，它的插入算法也是需要进行一些修改的。 Under the circumstances with headstones, the insertion algorithm needs some modification.
首先就是说，插入的时候，如果是我在整个这个探测链里面，碰到了这个墓碑元素，是不是就可以马上给它放进去？ Above all, after I find the headstone element in the whole probe sequence, can I insert directly?
其实不行，我还是必须在整个探测序列里面找到最后一个空槽的位置。 The answer is “no”. I still need to find the position of the last empty slot in the whole probe sequence.
我们来看这个插入算法这个跟我们前面不考虑删除的时候，是不一样的，有一点改进。 This insertion algorithm, as we see, is different from the former case without considering deletion and has some modification.
还是从这个基地址出发，我们还有一个特殊的就是说，我发现了墓碑，这么一个标记，首先我让这个标记为假。我们从基地址出发，我来比较说如果还没有找到这个空槽,也就是说整个这个探测序列还没有完成的情况下，我看如果是当前这个元素等于我们待插入的这个值，我就返回假。 From the base address, it is special that when I find one headstone with a mark, I first mark it as false. If I compare without finding the empty slot, which means the whole probe sequence is not completed and if the element is equal with the value for insertion, I return to false.
也就是说不允许你插入这样的重复关键码。 In other word, you’re not allowed to insert the repeated key codes.
否则，再来看，当前这个元素是不是一个墓碑？如果是一个墓碑的话，我把这个位置记录下来。 等待着我将来一直找到末尾以后返回来再找这个第一个墓碑的位置来插入。 Or we see whether the current element is a headstone. If so, I record the position, waiting for insertion after I finish searching the last headstone.
我们如果还一直没有找到整个探测序列里面，最后的得个空位置我们就是沿着这个探测序列继续往下面走一步。移到探测序列里面下一个位置，再继续这个循环。 If we don’t search the last empty position in the whole probe sequence, we take one step further along this probe sequence—move to the next position in the probe sequence and continue this circulation.
停止这个循环的时候如果不是说在这里面return to false，这个时候就是说相当于我们是停在一个找到了空位置的情况。就是探测序列里面的这个尾巴位置。 When we stop this circulation, if we don’t return to false, it means we stop where we find an empty position, or the end of the probe sequence.
我们来看，前面是不是曾经有过墓碑？如果是曾经有过墓碑的话？我们这个插入位置就要，插在墓碑上头。 Then we check whether we’ve met headstones before. If so, the insertion needs to be placed where the headstones lie.
否则的话？如果是没有过墓碑，我就是之后找的空巢的位置就是我要插入的这个位置。 If not, then the insertion is placed where the empty position is.
我们来看一下散列方法的效率。 We now turn to the efficiency of hashing.
我们衡量一个数据结构的重要的标志就是它的插入，删除和检索操作是不是非常高效。 One important index for we to evaluate a data structure is to see the efficiency of its insertion, deletion and retrieval operation.
在散列表里面，我们最主要的就是来考虑一下在整个这个散列表中插入或者删除或者检索我总共跟其中的这些元素各进行了多少次的比较。 In hash table, we mainly consider how many times I compare the elements in the process of insertion, deletion or retrieval in the hash table.
可以说散列表的插入和删除它其实都是基于检索进行的。插入，其实就是一次失败的检索，一直减到最后这个探测序列的尾巴。有找到一个空巢，还没有找到与待插入的这个根关键码一样的东西，我才能够插入。 The insertion and deletion actually are both based on retrieval. Insertion, as an unsuccessful retrieval, searches until the end of the probe sequence. Only when I find an empty slot without a value equal with the key code can I insert.
删除就是成功的一次检索。我找到了这么一个跟我待删的关键码一样的纪录，我在这个地方进行删除的操作。 Deletion, on the contrary, is a successful retrieval. I delete after I find one record same with the key code for deletion.
我们来看一下这个影响散列检索的效率的一个重要因素。就是负载因子，这个负载因子就是我整个散列表里面有效的元素个数N, 和整个散列表的大小M的一个比值。 Let’s see one important factor influencing the efficiency of hash retrieval—load factor. It is the ratio of the number of valid element in the hash table N to hash table size M.
可以说，如果是alpha等于 N除M这样的一个负载因子。它如果很小的情况下，我们可以，想象得到这个基地址被占用的这个可能性也更小，不太容易发生冲突碰撞。 We can say, if alpha is the N/M load factor and it is very small, the probability of the occupation of base address is smaller and it is hard for clash to happen.
而且即使发生冲突碰撞的话，后面，这个闭散列方法我要找到一个合适的空巢去解决这个冲突。也是不需要么长的这么一个探测序列就很快找到一个空位置。 Even if the clash happens, I need to further find an appropriate empty slot to settle the clash. In other word, I don’t need so long a probe sequence to find such an empty position.
alpha很大的时候，显然就跟它相反了。 If alpha is large, obviously, the situation is totally different.
所以，这个alpha它的一个大小是我们需要来考量的一个指标。 So the value of alpha is one index we need take into consideration.
我们，来看一下假设我这个负载因子alpha, 也就是说我当前是N个有效元素它的散列表大小是M。我在，下面插入，下一个元素的冲突碰撞的可能性就是N除以M。第二次发生冲突碰撞就是，就是N减1除以M减1我假设待插的这个数据也少了一点。我，整个这个表也小了一点。我第I次冲突的可能性就是这么一个公式。 Let’s see the supposed load factor alpha. I have N valid elements, and the size of hash table is M. Then I insert. Now the probability for the next element clashing is N/M, and for the second clash is (N-1)/(M-1). The data I suppose for insertion is smaller and the table size is smaller as well. The probability for first clash is calculated in this formula.
我假设N和M都很大，这种情况下，我就给它近似的表示为N除M的I次方。他的这个期望值，就是这样的一个概率和。 If the N and M are very large, in this circumstance, I represent approximately （N/M）^I, with the expectation as the sum of probability.
我假设对这个I从1到无穷，来求这么一个渐进的这个值。我就会得到1减alpha分之一这样一个代价。这其实就是一个插入代价，而且它是双散列的这个情况下的一个插入代价。 If I suppose I a value from 1 to infinity to calculate the asymptotic value, I will get a cost at 1-1/alpha. This is actually an insertion cost under double hash.
我们知道，一次这个成功的检索或者是一次删除的这个代价它其实是以前你怎么插进去的，现在我在检索的时候，我可能就是跟他当时插入的这个需要比较的这些次数是一样的。 We know that the cost of a successful retrieval or deletion is how you insert it before. Now when I’m searching, the times I need for comparison may be the same with he did when he inserted.
随着这个散列表里面这个纪录的不断增加，它的负载因子alpha其实是越来越大。 With the records in the hash table increasing, the load factor alpha is larger and larger.
我们就是从0到alpha 把这个，当前值的这个，积分也就是说我们这样的一个，插入的这么代价我进行积分。而且，我再除以alpha,就是导出的是这么一个查找；或者是删除操作它的这么一个代价。 We do integral upon the current value from 0 to alpha, or the insertion cost. In addition, when I divide the value by alpha, I export a search or a cost of deleting it.
就是得到这样的一个值。这一个其实也是针对双散列函数这样的一个，情况。 Yes, it is the value. This is actually a case for double hash.
我们可以看到就是刚才插入是这个值，成功的检索或者是删除是这一个值。相应的我们还可以，得出这个线性探测的这样一个必散列方法它的插入和删除的这个代价，以及开散列方法的这个代价。 As we see, the insertion is this value, and the successful retrieval or deletion is this one. Accordingly, we can get the cost of insertion, deletion and open hashing method from the linear probe.
我们来看一下，这些函数它的图示。可以看到开散列方法它的效率是最高的就是基本上接近于， 1这样的一个值。 Let’s see the graphical representation of the function. It is shown that the efficiency of open hashing is the highest, approximately close to 1.
而且，我们可以看到开散列方法里面的这个插入的这样一个代价，紫色的这个，曲线。它的代价是最低的，因为我们开散列里面我这样的一个空表直接插入，其实是最快捷的。 In addition, look at the insertion cost in the open hashing—the purple curve. It is the lowest cost, because in open hashing, inserting an empty list is the fastest way.
而删除或这是检索，这样的代价是这样的浅蓝色的线。这个线，可以说它的代价比我们的插入要，高一点。 As for deletion or retrieval, its cost is shown by the light blue line, which is a little higher than insertion cost.
我们再来看，双散列探测法它的这两条线。这两条线就是的一个，检索的代价。就是，这样的一个黄色的线，而这个插入的代价，是这个绿色的线。可以看出在双散列，这样的一个情况下，它的这个检索是比插入是要快一些的。 Now see the two curves in double hash probe method. They are the cost of retrieval. See, the insertion cost of the yellow line is the green line. Now we see in the case of double hash, its retrieval is faster than insertion.
线性探测它的这两条线就是蓝绿色的和蓝色的线比，双散列里面的这个，黄色的还有这个绿色的线，值是要高一些的。在上面，所以线性探测它的效率是比双散列是要低一些的。 The two lines for linear probing—the blue-green and blue lines, compared with the yellow and green lines in double hash, are higher, so the efficiency of linear probing is lower than double hash.
我们其实，还可以看到就是散列方法它的这个效率其实它是非常接近于theta 1的这样的一个代价。 它比log n是要好很多。而且刚才这样的一个图示，你可以看到随着alpha的增加这个效率是变得更差一些。 We can also see the efficiency of hash method is very close to the cost of theta 1. It’s much better than log n. What’s more, with the graphical representation, you can see that as alpha increases, the efficiency reduces.
其实我们回到刚才这个图可以看出，当这个，alpha它小于0.5的时候，他们的取值都是小于2。也就是说顶多两次这样的一个平均查找长度就能够完成我们的相应的操作。 Back to the former picture, we can see when alpha is less than 0.5, its value is less than 2. In other word, average search length for two times at most can complete the operation.
因此在设计散列表的时候，这个alpha等于0.5就是一个经验值。就是一定要保持这个散列表起码有一半以上的是空的。 So when we design hash tables, alpha=0.5 is an empirical value. We must be sure that at least half of the hash table is empty.
如果是散列表里面插入和删除比较频繁的时候，插入的话，我们就会使得这个alpha变得越来越大；而删除会使得我们这个墓碑越来越多。虽然整体的元素；有效的元素个数可能并不见得多了很多，但是这个墓碑占位站在儿使得我们探测序列越来越长。 When we have much insertion and deletion in one hash table, insertion will increase alpha while deletion will increase headstones. Though the number of whole elements and valid elements may not increase much, but the positions headstones take up lengthens our probe sequence.
那么这两种情况下都导致散列表的性能会下降。如果下降的话，我们都需要重组这个散列表。这个重组可能是需要申请一个更大的散列表的这个空间。 Under these two circumstances, the performance of hash table will decrease. If so, we need reorganize the hash table. We may apply for a bigger space for it.
另外就是，我们可以，进行一些访问的这个统计计数。就是把这些经常访问的这个元素，在重组的时候我尽量给它放到基地址的地方，使得它在这个探测序列里面比较靠后的位置。当然这个墓碑是需要给它清除掉的。 Or we can count the time of visiting. When I reorganize, I put those elements often visited to the base address as many as possible to place them at the back of probe sequence. Of course the headstones need removing.
最后给大家留几个思考。首先，我们这个墓碑是一种特殊的标记。因此我们散列表里面就是有墓碑、空元素和有效的数据这几种情况。我们是不是能够有一种方法就是把这个墓碑和空元素什么的进行一个合并。使得到我们这个状态变得少一些？ At last, I’d leave you some questions for considering. The headstones are special marks, therefore in our hash table there are several cases including headstones, empty elements and valid values. Can we use a method to combine all of them and decrease the cases?
另外散列方法是一种实现字典的比较有效的方法。其实还可以有其他的一些实现字典的方法。大家可以去调研一下，看看有哪一些。谢谢大家。 Also, hash is only one efficient way to implement dictionaries. You can do some research on other types of methods. Thank you.