这是一种开放地址HASH，主要目的是为了提高查询速度。提高查询速度常用的思路是在插入的时候对数据作调整，让数据更紧凑。常用的方法在HASH表比较满的情况下，复杂度都很难保证。这个方法的特点是，它可以保证最坏情况下，查询的复杂度也是个常数。元素X算HASH后，应该存在I节点，则允许它存在【I，I+H)之间第一个空闲的节点，H一般去32，一是H比较小，用一个INT作BITMAP就可以表示它后面哪些元素是HASH到这里的。二是，H太...

    在搜索引擎(SE)里BS一般对结果作CACHE，同时OS也会对倒排拉链作CACHE，也就是系统CACHE。这样可控性不强，可以考虑把两层CACHE都由BS控制，这样又带来一个问题，怎么分配两种CACHE的大小(之前也有这个问题，只是很难控制，所以就不管了)。实践中的做法，是不停地调整两者的比例，然后测试效果。这种方法的问题在于，单次测试代价很大，而解的空间很大，这样很难找到最优解。现在一般是默认，中间有一个最优解，然后向两边递...

    直译是虚拟内存，对于WINDOWS下的用户，直观的感受是，在硬盘上开辟一片区域当内存用。而LINUX下的用户，直观感受是，一个进程的内存占用，分虚拟内存与物理内存。虚拟内存的作用，个人理解，主要有几个：（1）简化开发，每个进程都可以认为自己占有整个内存，这对多任务系统很重要，早期有些系统，甚至需要使用相对地址，再根据代码载入内存的基准地址，算出真正要访问哪个内存地址（2）利用多级存储系统，把硬盘或别的存储介...

    HUFFMAN主要有两个问题，一是需要扫描两遍输入数据，二是树状结构编解码慢。对于第一个问题，基于统计信息的熵编码都很难解决这个问题，可以设计成自适应的，根据统计数据不停地改变调整码树，这会比较麻烦。对于第二个问题，这跟硬件有关系，二叉树的编码、解码都是O(1)的，复杂度上不能更优了，但是计算机硬件的特性，会使得树状结构遍历过程中CACHE MISS比较严重，如果码树比较小的话，可以都放在一级CACHE，性能会好很多，...

    这是一个通用的内存管理库，可以代替new delete之类。内存管理主要关注两点，一是分配、释放的速度，二是内存的利用率，也就是内存碎片问题。这两个目标是冲突的，不同的内存管理算法在两者之间取不同的平衡点为了提高分配、释放的速度，多核计算机上，主要做的工作是避免所有核同时在竞争内存，常用的做法是内存池，简单来说就是批量申请内存，然后切割成各种长度，各种长度都有一个拉链，申请、释放都只要在链表上操作，可以...

    网络协议里关于流量控制、提高交互效率、提高稳定性的部分，个人认为是最难的部分，以致于在LINUX内核里相关的实现都有BUG。前些年在追查一些网络故障的时候，看了些文档，一直想写些总结文章，但是这方面的内容实在太零散了，相关的RFC文档都好几个，把这些内容都说一遍，基本就把TCP/IP协议说了一遍。就只能挑几个CASE说了1、连接耗尽，这一般是短连接造成的。解决方案是，用长连接。这个方法看起来简单，其实很难，长连接会...

    这篇论文讲的是，一个全球的搜索引擎，需要在不同的地区布署一套服务，不同地区的索引不同。注：这也很容易理解，首先是带宽的压力，索引一般都是TB级别的，不能到处拷；其次是性能考虑，不同地区用户关注的网页是不同的，把用户不需要的网页也加进索引里，会使得检索性能很差。但是如果要地区的索引不能满足用户的需求，需要读取别的地区的索引的时候，怎么办？需要解决两个问题，一是是否需要读取别的地区的索引，二是读取哪...