大家好， Hello, everyone.
数据结构与算法这一讲我们继续第十章检索的学习。 We continue to take up chapter 10th retrieval to study data structure and algorithms.
今天我们介绍检索里面最重要的一种方法就是散列表的检索。 And today we introduce hash table, which is the most important method.
散列表的检索，它涉及到的问题特别的多，在这一讲里面我们首先介绍散列表的一些基本概念。 The retrieval of hash table involves many problems and we first introduce some basic concepts of hash table.
介绍一些散列函数。 Now introduce some hash functions.
我们前面介绍的些检索方法，它大致都是要基于关键码的比较的。 The retrieval methods we learned previously were mainly based on the comparison of key code.
有一列，是基于相等和不等，还有一列是基于这个等于和大于小于这样的分支。 One row is based on equal and unequal while another row on such branches of relationship of equal to, greater than and less than.
特别是对于数据规模大的时候，例如搜索引擎这样的搜索系统，用户他是受不了你跟N的规模相关的这么一个检索的代价。 When the data scale is too large such as search engine, the user usually cannot bear the cost of search relative to N.
因此我们就需要有一种检索方法，在1秒之内，能够很快地返回结果给用户。 Therefore we need a search method which can output retrieval results back to the user in one second.
因此，计算机科学家就发明设计了一种叫做散列的方法。 Computer scientist invented an approach called hash.
这个方法，我们把这个关键码k值，就像我们在数组下标里面的下标i值一样， 我通过一个映射，直接地把这个关键码映射到我们一个散列表里面的具体的下标位置。 The K value of key code, which is similar to the subscript I value of array, is mapped to a concrete subscript position of hash table.
我给它存起来。在将来，检索的时候，我们还用这样一个散列函数取到这样的相应的这个位置的值。 We save the hash function and use it to obtain the value of position when searching in future.
最简单的方法，我就是直接取各个这样的关键码它的首字母的这样的一个值，映射到散列表里面的相应的这个下标位。 The simplest way is to map the value of the first letter of the key to the corresponding subscript position of hash table.
如果我修改一下，我取这个首字母还有，它的这个尾字母这两个字母的这样的一个序， 我给它取它们的中间值就是除以2，我们得到一个新的映射表。 If we use the average value of the first letter and the last letter, we can get a new mapping table.
这个新映射表里面可以看到，解决了刚才这样的不同的关键码值它映射到同一个这样的 存储空间的这样问题。 The new mapping table has solved a problem that different key may be mapped to the same storage space if we only use the first letter.
我们整个这个散列表的大小如果是为m，我们填入表中的结点的个数是n，n除以m就是它的一个负载因子。 Use m denotes the scale of hash table and n denotes the amount of nodes we fill in the table, then loading factor can be obtained by dividing n by m.
这个负载因子，我们尽量不能够太大，一般来说应该是小于0.5是比较合适的。 Try to keep the loading factor from being too large, generally less than 0.5 is proper.
还有就是，如果我这个散列函数它把不同的关键码值运算到了同一个散列的这个地址，这就是发生了冲突。 A conflict occur when different key is mapped by the hash function to the same hash space.
在实际的这个应用中，我们设计的散列函数是经常发生冲突的。 In practical application the hash function we designed often triggers such conflicts.
散列函数它的本质就是把这个关键码key映射到一个非负的整数。这个整数是我们散列表里面的一个下标位的这个位置。 The essence of hash function is to map the key to a nonnegative integer, which is in subscript position of the hash table.
我们在选择散列函数的时候首先它的计算不能太繁杂，否则可能所花的时间就非常多了。 There are four points when selecting hash function.
还有就是散列值，我们应该是在我的散列表的这么一个地址空间的范围之内， First, avoid complicated calculation process or it will cost too much time.
另外，我们是尽量使得这样的同义词的情况少出现。 Second, the hash value is bound to be within the range of address space of the hash table.
也就是说如果关键码不同，我们映射的地址尽量的不同。 Third, try to reduce synonyms, that is to say, if the keys are different, the mapped space is better various.
而且尽量地让这些关键码在整个散列表里面能够均匀地分布。 And the last one, try to distribute the key evenly in the whole hash table.
我们要考虑的这些几个问题，首先就是关键码的长度是怎么样的，这个跟我们在设计散列函数的时候也是有关。还有散列表的整个这个大小是什么样的，还有我们关键码的分布情况，另外就是记录的检索频率。如果发生冲突的时候，我们是不是能够让这个 检索的频率比较高的这个同义词能够摆在这个散列表的基地址，检索频率相对较低的，我通过一些冲突碰撞的解决方案给它放到一些其他的地方。 Therefore we need to consider the following several questions. The first one is the length of key, which may influence the hash function we design. The second one is the scale of hash table and the distribution of key. And the third one is recorded retrieval frequency, which means when conflict occur, synonyms in higher retrieval frequency can be showed a basic space in the hash table and ones in comparatively lower frequency can be placed in other space by some solutions to conflict.
下面我们介绍一些散列函数的方法， In the following we introduce some methods to gain hash functions.
首先就是最常见的一个除余法。 A common one is remainder method.
这个除余法，我们把这个关键码x除以某一个M值，这个M值，它可能是散列表的这个长度。其实，有的时候我们是取这个小于散列表长的一个最大的素数。 Remainder method means we divide the key x by value，M. Value M can be the length of the hash table, and sometimes it is the largest prime number among those less than the length of the hash table.
“除余法”非常的简单， 但是，也有一些这个问题就是说 选择这个M值的时候，我们要考虑几个问题。 Then the remainder method get easier, however, we have to consider some problems when selecting the value m.
首先我们应该使得这个函数值 是依赖于我们这个关键码的所有的位数，而不是说它右边的 某几位。 On the one hand, the function value should depend on all digits of the key, not the several digits in the right.
还有就是它需要能够尽量的使得这个关键码 在整个散列表里面尽量均匀地分布。 On the other hand, value m should make the key distribute as even as possible in the whole hash table.
所以我们来看一下这几个情况。 Now let’s look at several questions.
首先就是，我们为什么不能够用偶数来做这个M。 如果是用偶数的话，它会把原来是偶数的我在 散列为偶数的这个地址空间，原来是奇数的也有散列 为奇数的这个空间。显然它的分布就不均匀了。 the first one, why can’t we use an even number as value M. if we use an even number, then the odd key will always be mapped to an odd value while the even key will always be mapped to an even value, which means the distribution is uneven.
另外我们也不能取这个2 的幂次或者10的幂次。例如我们如果是取2的幂次 这里如果M等于2的8次方，我们就是相当于是 取到了这个关键码的最右的 8个bit位。 这样的话，我们就丢失了它的高位的一些其他的这些数值的 信息。如果是把M设置为10的幂次，也有类似的情况。 And we can’t use power of 2 or power of 10. If we take power of 2, take value m equal to 8 power of 2 as an example, it means we only take use of the right 8 bit of the key and miss the information of high digits. The situation is similar when m is designed equal to the power of 10.
我们看到这个除余法，它还有一些问题。 Here are other problems using the remainder method.
首先就是，如果是我这个关键码是连续地给你的，它 在散列了以后它也是把它分布在连续的区间里面。 万一我们有冲突碰撞需要一些相邻的区域来解决这些 冲突碰撞的同义词，就有问题了。 Firstly, if the keys are continuous, the mapping value will distribute in a continuous area and cause inconvenience if adjacent area is needed to solve the conflict of synonyms.
另外就是它整体来说可能会发生这个散列性能的一个下降。 Secondly, the hash performance may decline as a whole.
我们再介绍一种乘余取整的方法。 Then we will introduce another method called ‘multiply the decimal and Rounded down’
我可以设计这么一个函数，首先就是让这个key乘上一个常数A。这个A是小于1的非负的小数，我们提取这个乘积的小数部分，再乘以一个比较大的值，对这个结果我们取下整就是说把这个小数部分全抛掉，只要这个整数部分的这个结果。 We can design a function like this, first multiply this ‘key’ by constant A (A is a non-negative decimal less than 1). Then we multiply the decimal part of the result we just obtained by a larger value. We only want the integer part of the product, so we leave out the decimal part.
我们来看一下这样的一个例子。对这个Key我取的这个A，是，其实就是一个黄金比例的一个相关的数。 Then let us see another example. The A I choose for this key is actually a number related to the golden ratio.
我对这个n的取值，我是取的10000。我们这个计算的这个结果就会是41。这就作为我们原来这个key值它的一个散列到这个散列表里面的这样的一个下标的位置，也就是它的地址的这个位置。我们在用这个乘余取整法的时候，我们如果是地址空间是p个这样的digital位，也就是0,1的这个位，我们有p个。我们取就是n等于2的p次方这样是比较合适的。 Iuse 10000 as the value of n here, so the result of the compute is 41. This result can map one hash of key value with a subscript location in the hash table, which is also the location of key’s address. When using this method, if the address space has p digital place like this, which means we have p bits of 0 and 1, then we’d better use p power of 2 as the value of n.
另外，Knuth他认为，这个A也就是个小于1的非负的这个小数 它尽量取这个黄金分割，这样0.618是比较合适的。 Moreover, Knuth held the view that it is more appropriate to use golden section (0.618) as the value of A, which is the nonnegative decimal less than 1.
第三种方法，平方取中法，这是一个非常好的一个散列的函数。 The third method called middle square method is a very good hash function.
对于这样一组这个二进制的这个关键码,我们对它们分别求平方值， ，根据你这个散列表的大小，我取中间的若干位可以看到，我们原来的这个二进制关键码每一位的这个数值，它都在我们的这个平方的结果里面，它是有所影响或者说有所体现的, 我们在取中间的这样的若干位我们得到的这个结果,它是能够比较均匀的分布在散列表里面。 For such a group of binary key codes, we first compute the squared value of them respectively. Then we choose some bits in the middle according to the size of the hash table. We can see that all the values of bits in the original binary key codes are involved in the square result we got, which means they are meaningful in the result. The result we got from the middle bits can distribute uniformly.
我们介绍了第四种方法是一种数字分析法。 这个数字分析法它的含义,就是说我希望分析我这个带散列的这些数据它们在这些就是数据的这个每一个位它们如果有r种不同的取值的话我们看它对这个r种不同的这个取值它的这个分布是不是尽量的均匀如果是均匀的话么这一个数据位我们就可以采纳它。 The fourth method I introduce is digital analytical method. When we want to analyze the data with hash, if the bit of the data has r different values and these r values distribute uniformly, then we can use such bits in the digital analytical method.
我们这个数字分析法的其中的一种方法我首先就是来看这个数字里面这个符号分布的这个均匀度。 我们把这个它的真实的这个出现的频次以及与它的这个期望频次之间的这个差我们取平方，我们来看在这个k位上这个每一个这个可能的符号r它们分别这个出现的这样的一个分布是什么样的一个值 One method of using the digital analytical method is observing the uniformity of the distribution of symbols in the numbers. We compute the square value of the difference of its real frequency and expected frequency. Then we see the possible distribution value of every symbol r in this k bit.
么-例如对我们这样的一组数据这是有 8个数据，有1、2、3、4、5、6位是上头，它们的 这些number的分布的情况可以看到number 1和number 2是非常大的这个值。 这个number值越大它的分布就越不均匀，我们也可以看到它都是只有一个这个数值是出现的。在这个第三位它的分布也不是很均匀，只有0、1、2出现 4、5、6位它们的分布是比较均匀的。 For example, we have 8 data with bit 1, 2, 3, 4, 5 and 6 in this group. From the distribution of these numbers, we can see that number 1 and 2 are very large. The larger number means non-uniformity of the distribution, so we can see that only this number occurred in the distribution. The distribution of third bit is not uniformity either, only 0, 1 and 2 occurred. While the distribution of bit 4, 5 and 6 is quite uniform.
如果是说你的这个散列函数只能够取三位这个数字其他的要抛掉 So it means if this hash function can only use these three digit then we should leave out the others.
这样的话我们就选择取这个4、5、6 这三位的这样的数字，我们作为这个散列的地址。 这种方法就是我们事前要知道这个表里面这些关键码它的这个分布的情况是什么样的。 你可以通过一些这种分布的这些计算的方法来获得它们这个分布的均匀情况你再做选择。 但是它非常强烈的依赖于我现有的这个数据集是个什么样的我得出的一种结果。 如果我换一套数据你就要重新计算，所以它的适用性不是那么强的。 That means we should select such numbers of bit 4, 5 and 6 as the address of this hash. In using this method we need to know the distribution of key codes in advance. Therefore you can use these methods to compute the distributions before selecting the numbers. However, the result we obtain is strongly relied on the current DS we have. If I change another set of data, you need to re-compute the result, so this method has limited applicability.
我们再来看一种方法就是基数转换。基数转换方法它就是把这个一个关键码 我首先人为的看作是另外一种进制的这个数。我把这个另外一个进制的数我把它计算完了以后回到原来的进制，我再取其中的若干位来作为散列的地址。最好是这两个进制或者说这个基数是互质的。例如对于这么一个十进制的关键码我们把它人为的看作是13进制的这样的数据。我们经过计算以后它在这个十进制里面是相当于是这么一个数值，如果散列表的长度是一万，我们取第四位或者是截取中间某四位也是可以的，我们作为一个它的散列地址。 Let’s see another method called radix conversion. This method takes the key code as a number in a different system. I compute the number using a different system and then choose some bits of this number as the address of the hash in its original system. In this condition it is better when the radixes of the systems are relatively primes. For example, we use this key code in decimal system and consider it as a data in 13-based system. After computing it is equivalent to the number in decimal system. If the length of the hash table is 10 thousand, then we select the fourth bit or four bits in the middle part as the address of the hash.
我们前面介绍过这个平方取中法它是一个非常好的方法。 但是如果位数特别多的话你这个乘法的代价是非常大的。 如果我能够把它变成加法来算也还是不错的，我们有两种方法就是移位相加和分界相加。 我们来看我们这个两种方法它的计算的这个结果。 The middle square method that I introduced before is quite good, but it is a hard work of using multiplicative if it has too many bits. Luckily I can use additions instead of multiplicative. We have two additions including shift addition and demarcation addition.
假设对于这个书的编号是这么一个串，我假设我个散列的这个结果地址只能是四位的，也就是说我最多表示这个一万个槽的这么一个散列的空间。 Suppose this is a set of serial numbers of this book, then I suppose the result address of the hash only have four bits, that is to say, I can only express a hash space of 10 thousand slots utmost.
我的移位相加就是我从这个低位开始四位-四位一节，我把它截成三段，最高位的边我左补0，我得到了这样的一个叠加的计算值，如果有进位我给它舍掉。 The shift addition means I cut the number into three sections from the low bit, each section has four bits. Here I add a zero in the left of the highest bit, and thus I get a superimposedcalculated value. Here I leave out the carries.
可以看到我们这种方法也不错，它所有的这些原来这个关键码里面的这些数值都参与了运算,也就是说它都能够影响到我们的这个散列的这个结果。 This method is not bad, all the original key codes have participated into the computing, which means they all influenced the result of this hash.
还有一种就是分界相叠加的方法就是我也是先从这个低位往高位来看这些数值。 但是我们在转接的时候我都是像这个折纸一样我给它叠一下，因此我们第二次得到的这一组这个四位数，我就是要把它个给它转置一下给它颠倒一下。 Another method is demarcation addition which observes the numbers from low bit to high bit. We use the superposition when commutate them like paper folding, therefore the second group of four bits number should be ‘folded’ and be reversed.
我再接着这个地方我也可以看到还是给它叠加我再转置一下，负负得正 又回到了这个04这样的一个顺序，我们把这个结果给它加起来也是如果有进位我给它舍掉,这个方法也是非常简单有效的。 Here I use the superposition again and then reverse it, so I got the positive result and we come back to the order of 04. Similarly, we leave out the carries when performing the addition. This method is also very simple and efficient.
如果我们散列的这个关键码它不是整数而是字符串的这个情况 当然我们可以有各种处理方法，有一种转换方法我们是在UNIX里面 就是有个ELF hash这样的一个字符串的这个散列方法 If the key codes in the hash are not integers but character strings, then we have different solutions. One solution is that we use ELF hash character string in UNIX.
我们可以看到它对每一个这个字符它都参与了运算，而且通过一些移位 还有等等这些方法使得我们这个每一个字符都能够影响到 散列的这个计算结果，当然最后我们是要根据你的这个散列表的这个大小的空间我们做一个对M取模的操作来取它的一个余数值。 So we can see that it participates in the computing of every character through shifting…..?...and other methods so that every character can influence the result of hash computing. Finally we should make an modular of M to obtain the numerical value according to the space and scale of the hash table.
我们可以看到ELF hash这个函数它对于长串和短串都是非常有效的。而且每个字符都在里面发生了作用，因此它的这个散列结果分布是比较均匀的。 So we can see that ELF hash function is efficient to both long strings and short strings. And all the characters make sense in the computing, thus the result distribution of hash is quite uniform.
我们前面介绍了各种散列函数，在实际应用中我们根据你的一个应用场景来选取不同的这个散列函数. So far I have introduced different hash functions, and we should use different functions according to the applied situation.
有人用这个轮盘赌的方法来统计了这些散列函数它们的这种散列效果的分布的情况，结论就是平方取中法它是一个非常随机化的方法,也就是说它的效果非常好，使得我们整个这个散列函数里面的这些关键码值它的分布是比较均匀的。 Someone use roulette to count the hash result distribution of these hash functions. The conclusion is middle square method is a very randomized and efficient method, and it obtains an uniform distribution of key codes in the hash function.
如果是对于字符串的这个情况除了我们刚才说的ELF hash这样的一个情况我们也可以 把这个字符串当作是个26进制的这样的相应的这些数值，也采用前面所说的些所有的散列的方法. For the condition of character strings, besides the ELF hash just mentioned, we can also take the character string as the equivalent values in the 26-based system using the previous methods.
最后给大家留几个思考，首先就是采用散列的时候我们怎么样构造这种散列函数使得散列的这些数据它能够尽量均匀的分布在散列表里面。 In the end, I have some questions for you to think. First is how to construct the hash function to make the data distribute uniformly in the hash table.
另外就是散列函数如果是发生冲突的时候也就是我们有同一值出现的时候，我们用什么方法来解决它？ The second is when the hash functions conflict, which means there is the same value occurs, what method will you use to solve it?
还有就是散列表本身的组织这也是需要我们考虑的内容。 谢谢大家。 I want to add that the organization of the hash table should also be considered in this condition. Thank you!