从虚拟存储器联想的一系列有趣的事

本文是一篇漫谈，不一定都和虚拟存储相关，我只不过从虚拟存储器联想到一些事情，进而随便写写。
总听论坛上的一些朋友问什么哈希表和搜索树那个效率高的问题，其实这个问题根本没有意义，你就看linux内核源码吧，如果说哈希效率高，那么怎么还有n 多棵树，最新的cfs调度器，event-poll，虚存区间等等用到了红黑树；文件缓存用到了radix树；甚至连优先搜索树都可以在文件反向映射的代 码见到；反过来，你要说搜索树效率高，那么linux的招牌--网络当中的路由查找算法就是用的哈希，而且pid，套接字等等都是哈希，哈希的例子更多， 关键是你的应用场合是什么，搜索树包括很多种，各有各的用武之地，avl树，红黑树可以分为一类，splay树分为一类，b树以及b+，b-树分为一类，当然还有选择树等等。
像红黑树，avl树是做查找用的，它们的特定不是效率有多高，而是有保证，仅仅是将最坏情况限制在一定情况，不像哈希，完全依赖你的哈希函数和输入的长度，在哈希函数不好或输入无限增加的情况下性能会急剧下降，但是前面的两颗树不会，另外如果你仅仅做查找，在有比较好的哈希函数的情况下还是哈希好，哈希 是静态的，一切按部就班的按照你的哈希函数来，比较适合仅查找俄情形，如果有了动态数据涉及到频繁的删除插入，那么就要用平衡树，像红黑树和avl树了， 他们自身提供了一套机制来维持自身的平衡性使得自己完美的身材不会坍塌，维持平衡当然需要一定的开销，事实上就是我们日常生活中的扁担原理，一根扁担扛在肩上，一会前面重了往后以东以下，一会再往前一下，这样维持平衡。这体现到数学上就是旋转操作，往往很多教科书上把旋转讲得过于玄乎，而且只和avl，红 黑树关联，实际上只要是数都可以旋转，只不过在那些平衡树里旋转操作比较常用罢了。
spaly几乎每次查询都会调整树的结构，反映到具体动作就是写内存，这样就导致了cpu的cache频繁失效而刷新，影响了性能，实际上splay树本 身就有缓存的性质，将最近访问的置顶，以期望未来再次访问时减少查询时间，但是不巧的是，这种缓存和cpu的缓存是冲突的，那么如何取舍，当然还是舍软而 取硬了，但是spay树实现的软件缓存具有一般性，使得软件更加统一，试想在没有缓存的cpu上，splay树就派上用场了。
选择树其实就是一个分级的模型，将局部的权值全局化的一棵树，特别类似于现实当中的体育比赛，分为很多小组，现在小组内部排名，然后根据排名顺序参赛，最终得到整体排名。
这种问题看别人问多了，自己也就开始思考了，软件是人做的，硬件也是人做的，同样的都是人的思想，涉及思想咋能不同呢？我就觉得它们应该一样的。
现在我们都在用的内存实际上就是一个哈希表，而哈希函数就是硬件的mmu提供的那一套页目录，页表，冲突解决算法其实就是“请求调页”机制，输入域就是我 们写的代码映像成的可执行的抽象的程序--虚拟内存，输出域就是物理内存，你想想，我们一台机器运行那么多的程序竟然能完好，你执行几吉的代码或读写几吉的文件，而物理内存那么小竟然不冲突，这本质上就是硬件和软件提供的类似于哈希的机制，哈希冲突总会有的，但是解决办法也总会有的，当没有物理内存可用的 时候，类似于哈希冲突的事情就发生了，于是靠分页解决之，进一步思考为什么会这样，现代的哈希算法在现代的硬件上的表现就是虚拟内存管理，但是虚拟内存管理才出现不长的时间，而哈希却出现很久了，它们之间到底有什么关系吗？
试想我们现代的计算机体系为什么会是这个样子？前面我转载了一篇《两个世界体系的对话》里面抱怨冯诺依曼说他阻碍了并行计算，不光那篇文章，网上很多朋友都说现在并行计算很难很麻烦，于是出现了很多讲并行计算的天书，很难读懂，我一直都相信世界是简单的，于是我觉得设计那么多复杂的并行算法根本可能就是走 了弯路，我们必须弄清楚每件事情才能继续往前走，在明白了并行计算很困难之后我们真的明白为什么这种不那么困难的，串行的计算，存储结构的计算机体希会统治世界吗？首先说说为什么我们的内存不太适合并行计算，主要就是个顺序问题，这个问题请参见《两个世界体系的对话》；其次说说为什么会有这种内存，我们人 往往希望把不确定的东西往确定的方向靠拢，这就产生了索引，想想高考，考生是不确定的，是复杂的，无序的，无法预料的，但是高考的结果---大学，却是确 定的，接受统一管理的，存在一个规则将这帮鱼龙混杂的高考生分别“散列”到这些规则管理的学校，呵呵，高考本身就是个哈希函数，想想不是吗？
还有很多例子。再比如，这个世界的人口非常无序，非常复杂，但是总会有一些规则将这帮家伙“散列”到不同的国家，公司，甚至监狱...而不管是国家，还是监狱都不是无序的。就着前面索引的概念我们知道索引是有序的，已知的，容易管理的，而被索引的内容则是无序的，未知的。那么设计一种根据索引查找数据的存 储结构应该是人天真地愿望，因为索引是有序的，反过来，设计一种根据数据来找索引的结构应该就属于不正常的行为了，有人可能会问，根据你上面举的例子，人是无序的，学校是有序，按照理论说应该是学校找人方便，而通过人找学校复杂，但是事实上正好相反，这怎么解释呢？这就涉及另一个概念了，之所以学校找人不 方便是因为学校有很多人，如果学校就你一个人，问题就解决了，这个问题涉及到哈希冲突解决方法，学校有名册，找呗！相反，若要从人找学校，直接拿他学生证看不就完了。事实上有这个疑问的人忽略了一个事实，从学校找人，我们必须先找到学校；从人找学校，我们必须先找到这个 人，这下再考虑考虑，想通了吗？呵呵！
所以不要埋怨人家冯诺依曼，人家只是将人们心中的秘密给体现到计算机上了，没有什么不对的，相反地，从内容找索引的存储器也是有的，比如相联存储器，但是别慌，先看看它的实现再说，它内部实现其实是一个一个比较的，只不过这种比较通过设计得相当艺术的硬件进行，速度很快，所以相联存储器内部并没有真正实现 由数据直接定位索引，只是在更高的层面给了人一个假象而已。
事实上，根据数据一次定位索引我认为是不可能实现的，因为数据的未知性，你总不能把世界上的每个数据都留一个拷贝吧，我无语...仔细想想，如果想知道一 个人被“散列”到那些“桶”，那么就要找出他的一大堆证件，开始一个一个查，看来还是现实世界比计算机世界做的更进一步，证件实际上就是一个“反向映射 ”，这样就可以直接找到他被“散列”到哪个“统”，也即是通过数据找到了索引，数据在刚刚被散列到该索引时加入反向映射，这样以后就方便反向查找了，但是计算机里会出现“洛阳纸贵”的现象，玩不起的，具体怎样，看将来了。
由于散列事实上是人的一个本能，那么任何事情可能都和它有关系，至于说数据结构中的查找树等一系列树是怎么回事呢？它们是一种动态的东西，体现一种过程，比如，我高考完了，想看看我的分数能上什么大学，或者解释一下我为什么上了黑龙江科技学院，这就用到查找树的思想了，事实上，intel的虚拟内存的 MMU就是用一颗radix树将虚拟内存转换成物理内存的，今天看了看文件缓存的radix树，发现它的计算方法和页表映射的方法竟然一谜一样。