在一个解决方案的复杂性之中理论或者概念的部分通常只占有限的一小部分。理论无法做实际的工作——否则它也不成其为理论了。从理论到实用需要经过一系列的发明。从实用到更加实用、更加通用往往需要增加更多的复杂性。有时这一过程远远超越科学的范畴成为艺术家的乐园。有时这一过程引入了过多不必要的复杂性只是因为人类的自私、愚蠢和目光短浅。科学不会也不能处理奇迹。科学只能处理重复的事件艺术却不同。艺术是“就是如此”。在一个创作诞生以前它是 Nothing——它没有来由、毫无征兆诞生之后它就是存在是合理是自然和美。我们所谈论的算法作为一门实用的科学既有科学的一面也有艺术的一面。作为科学它的结构可以分析它的行为可以预测它的属性可以量化它的正确性可以证明。作为艺术在一个算法诞生之后有时我们只能说“它能工作”仅此而已对于它是如何来到这个世界上的我们一无所知——这里没有“因为……所以……”也不是简单的从一般到特殊。创造似乎和生命一般神秘。我们可以给造物穿上漂亮的科学外衣欣赏它内在的一致性但是最让人着迷的创造性的那一部分却完全无法加以描述。所以当我们进行散列表的从理论到实用之旅时如果你察觉到一些没有解释的跨越请不要见怪吧。如果没有这些跨越我们就完全可以设计一个程序发明这些算法我们所要学习的算法也就完全会是另外一个样子了。O(n) 查找和 O(1) 查找两个模型如果想知道在《伊利亚随笔选》这本书里是否有一个“囿”字该怎么做呢我们只有从第一页的第一行开始一个字一个字地向后看去直到找到这个字为止。如果直到最后一页的最后一个字都没有找到它我们就知道这本书里根本没有这个字。所以这项工作的复杂度是 O(n)。再假设有这样一本《会计专用字帖》它只有9页每一页上有一个大写的数字当会计想要练习“柒”字时只要她事先知道页码和内容的对应关系就可以直接翻到第7页实现 O(1) 复杂度的查找。通过这个模型我们知道要想达成 O(1) 复杂度的查找必须满足3个条件1. 存储单元例如一页纸中存储的内容例如大写数字与存储单元的地址例如页码必须是一一对应的。2. 这种一一对应的关系例如大写数字“柒”在第7页必须是可以预先知道的。3. 存储单元是可以随机读取的。这里“随机读取”的意思是可以以任意的顺序读取每个存储单元并且每次读取所需时间都是相同的。与此相对的读取磁带里的一首歌就不是随机的——想听第5首歌就不如听第一首歌来得那么方便。在计算机上实现 O(1) 查找先来看计算机的硬件设备。计算机的内存支持随机存取从它的名字 RAM(random-access memory) 可以看得出对于这一点它还真有一点引以为傲呢。既然硬件支持我们就可以准备在计算机上模拟会计专业字帖了。第一项任务是向操作系统申请9个存储单元。这里有个小问题我们得到的存储单元的地址很可能并不是从1到9而是从134456开始的。好在我们并不需要直接跟操作系统打交道高级语言会为我们搞定这些琐事。当我们使用高级语言创建一个数组时相当于申请了一块连续的存储空间数组的下标是每个存储单元抽象的地址。这样我们第一个 O(1) 复杂度的容器 SingleIntSet 很容易就可以完成了它只能存储 09 这10个数字1234567891011121314151617181920publicclassSingleIntSet{privateobject[] _values newobject[10];publicvoidAdd(intitem){_values[item] item;}publicvoidRemove(intitem){_values[item] null;}publicboolContains(intitem){if(_values[item] null)returnfalse;elsereturn(int)_values[item] item;}}测试一下12345678staticvoidMain(string[] args){SingleIntSetsetnewSingleIntSet();set.Add(3);set.Add(7);Console.WriteLine(set.Contains(3));// 输出 trueConsole.WriteLine(set.Contains(5));// 输出 false}新术语使用高级语言创建了一个整型数组时例如 int[] values new int[10]我们不再把 values[7] 称为“一个存储单元”因为存储单元的大小是一个字节在32位操作系统上values[7] 的大小是4字节所以我们要使用一个新术语把 values[7] 称为 values 数组的一个槽(slot)。SingleIntSet2说实话我真不喜欢这个名字谁会喜欢新需求同样只需要保存10个数字只不过这次不是保存09而是需要保存1019怎么办很简单实现一个槽里的值与地址的映射函数 H() 即可12345678910111213141516171819202122232425publicclassSingleIntSet2{privateobject[] _values newobject[10];privateintH(intvalue){returnvalue - 10;}publicvoidAdd(intitem){_values[H(item)] item;}publicvoidRemove(intitem){_values[H(item)] null;}publicboolContains(intitem){if(_values[H(item)] null)returnfalse;elsereturn(int)_values[H(item)] item;}}测试的时候使用1019范围内的数字12345678staticvoidMain(string[] args){SingleIntSet2setnewSingleIntSet2();set.Add(13);set.Add(17);Console.WriteLine(set.Contains(13));// 输出 trueConsole.WriteLine(set.Contains(15));// 输出 false}房子不够住难道睡马路这次还是存储10个数字只不过数字的范围是019。如何把20个数字存放到10个槽里还能怎么办2人住1间咯。略微修改一下 H() 函数其它代码不变12345678910111213publicclassSingleIntSet3{privateobject[] _values newobject[10];privateintH(intvalue){if(value 0 value 9)returnvalue;elsereturnvalue - 10;}// ...}测试一下123456789101112staticvoidMain(string[] args){SingleIntSet3setnewSingleIntSet3();set.Add(3);set.Add(17);Console.WriteLine(set.Contains(3));// 输出 trueConsole.WriteLine(set.Contains(17));// 输出 trueConsole.WriteLine(set.Contains(13));// 输出 falseset.Add(13);Console.WriteLine(set.Contains(13));// 输出 trueConsole.WriteLine(set.Contains(3));// 输出 false. 但是应该输出 true 才对}最后一行的结果不对2人住1间是行不通的数据受不了这委屈。但是米有办法除非 1) 我们预先知道所有的10个输入2) 这10个输入一旦决定就不再更改否则无论怎么设计 H() 函数都无法避免2人住一间的情况这时我们就说发生了碰撞collision。用链接法处理碰撞
散列表(Hash Table)从理论到实用（上）
在一个解决方案的复杂性之中理论或者概念的部分通常只占有限的一小部分。理论无法做实际的工作——否则它也不成其为理论了。从理论到实用需要经过一系列的发明。从实用到更加实用、更加通用往往需要增加更多的复杂性。有时这一过程远远超越科学的范畴成为艺术家的乐园。有时这一过程引入了过多不必要的复杂性只是因为人类的自私、愚蠢和目光短浅。科学不会也不能处理奇迹。科学只能处理重复的事件艺术却不同。艺术是“就是如此”。在一个创作诞生以前它是 Nothing——它没有来由、毫无征兆诞生之后它就是存在是合理是自然和美。我们所谈论的算法作为一门实用的科学既有科学的一面也有艺术的一面。作为科学它的结构可以分析它的行为可以预测它的属性可以量化它的正确性可以证明。作为艺术在一个算法诞生之后有时我们只能说“它能工作”仅此而已对于它是如何来到这个世界上的我们一无所知——这里没有“因为……所以……”也不是简单的从一般到特殊。创造似乎和生命一般神秘。我们可以给造物穿上漂亮的科学外衣欣赏它内在的一致性但是最让人着迷的创造性的那一部分却完全无法加以描述。所以当我们进行散列表的从理论到实用之旅时如果你察觉到一些没有解释的跨越请不要见怪吧。如果没有这些跨越我们就完全可以设计一个程序发明这些算法我们所要学习的算法也就完全会是另外一个样子了。O(n) 查找和 O(1) 查找两个模型如果想知道在《伊利亚随笔选》这本书里是否有一个“囿”字该怎么做呢我们只有从第一页的第一行开始一个字一个字地向后看去直到找到这个字为止。如果直到最后一页的最后一个字都没有找到它我们就知道这本书里根本没有这个字。所以这项工作的复杂度是 O(n)。再假设有这样一本《会计专用字帖》它只有9页每一页上有一个大写的数字当会计想要练习“柒”字时只要她事先知道页码和内容的对应关系就可以直接翻到第7页实现 O(1) 复杂度的查找。通过这个模型我们知道要想达成 O(1) 复杂度的查找必须满足3个条件1. 存储单元例如一页纸中存储的内容例如大写数字与存储单元的地址例如页码必须是一一对应的。2. 这种一一对应的关系例如大写数字“柒”在第7页必须是可以预先知道的。3. 存储单元是可以随机读取的。这里“随机读取”的意思是可以以任意的顺序读取每个存储单元并且每次读取所需时间都是相同的。与此相对的读取磁带里的一首歌就不是随机的——想听第5首歌就不如听第一首歌来得那么方便。在计算机上实现 O(1) 查找先来看计算机的硬件设备。计算机的内存支持随机存取从它的名字 RAM(random-access memory) 可以看得出对于这一点它还真有一点引以为傲呢。既然硬件支持我们就可以准备在计算机上模拟会计专业字帖了。第一项任务是向操作系统申请9个存储单元。这里有个小问题我们得到的存储单元的地址很可能并不是从1到9而是从134456开始的。好在我们并不需要直接跟操作系统打交道高级语言会为我们搞定这些琐事。当我们使用高级语言创建一个数组时相当于申请了一块连续的存储空间数组的下标是每个存储单元抽象的地址。这样我们第一个 O(1) 复杂度的容器 SingleIntSet 很容易就可以完成了它只能存储 09 这10个数字1234567891011121314151617181920publicclassSingleIntSet{privateobject[] _values newobject[10];publicvoidAdd(intitem){_values[item] item;}publicvoidRemove(intitem){_values[item] null;}publicboolContains(intitem){if(_values[item] null)returnfalse;elsereturn(int)_values[item] item;}}测试一下12345678staticvoidMain(string[] args){SingleIntSetsetnewSingleIntSet();set.Add(3);set.Add(7);Console.WriteLine(set.Contains(3));// 输出 trueConsole.WriteLine(set.Contains(5));// 输出 false}新术语使用高级语言创建了一个整型数组时例如 int[] values new int[10]我们不再把 values[7] 称为“一个存储单元”因为存储单元的大小是一个字节在32位操作系统上values[7] 的大小是4字节所以我们要使用一个新术语把 values[7] 称为 values 数组的一个槽(slot)。SingleIntSet2说实话我真不喜欢这个名字谁会喜欢新需求同样只需要保存10个数字只不过这次不是保存09而是需要保存1019怎么办很简单实现一个槽里的值与地址的映射函数 H() 即可12345678910111213141516171819202122232425publicclassSingleIntSet2{privateobject[] _values newobject[10];privateintH(intvalue){returnvalue - 10;}publicvoidAdd(intitem){_values[H(item)] item;}publicvoidRemove(intitem){_values[H(item)] null;}publicboolContains(intitem){if(_values[H(item)] null)returnfalse;elsereturn(int)_values[H(item)] item;}}测试的时候使用1019范围内的数字12345678staticvoidMain(string[] args){SingleIntSet2setnewSingleIntSet2();set.Add(13);set.Add(17);Console.WriteLine(set.Contains(13));// 输出 trueConsole.WriteLine(set.Contains(15));// 输出 false}房子不够住难道睡马路这次还是存储10个数字只不过数字的范围是019。如何把20个数字存放到10个槽里还能怎么办2人住1间咯。略微修改一下 H() 函数其它代码不变12345678910111213publicclassSingleIntSet3{privateobject[] _values newobject[10];privateintH(intvalue){if(value 0 value 9)returnvalue;elsereturnvalue - 10;}// ...}测试一下123456789101112staticvoidMain(string[] args){SingleIntSet3setnewSingleIntSet3();set.Add(3);set.Add(17);Console.WriteLine(set.Contains(3));// 输出 trueConsole.WriteLine(set.Contains(17));// 输出 trueConsole.WriteLine(set.Contains(13));// 输出 falseset.Add(13);Console.WriteLine(set.Contains(13));// 输出 trueConsole.WriteLine(set.Contains(3));// 输出 false. 但是应该输出 true 才对}最后一行的结果不对2人住1间是行不通的数据受不了这委屈。但是米有办法除非 1) 我们预先知道所有的10个输入2) 这10个输入一旦决定就不再更改否则无论怎么设计 H() 函数都无法避免2人住一间的情况这时我们就说发生了碰撞collision。用链接法处理碰撞
