实际上就是一个数据结构而已，虽然偶觉得这个数据结构应该已经有人提出过了的说，但是找不到。偶把这个数据结构叫做哈希树，然后偶以哈希树为关键词查找，没找到多少结果。然后偶又以hash tree作为关键词查找，找到了维基百科，但是看上面的解释不太清楚，不过估计应该就是那样子的没错了。
弄出这个数据结构的初衷是想要保存一些FTP已登陆用户的信息，因为查找频繁，所以希望这个数据结构能提供很快的查找速度。于是想到了哈希表，但问题是，同时登陆的用户数是未知的，这样就不知道需要定义多大的哈希表，而且如果同时登陆的用户较多的话，哈希表也会变得比较大才能满足要求。
于是我就想，把平衡树挂在哈希表上，每一个哈希表的值节点都有挂着一颗平衡树。确定一个索引值在这个数据结构中的位置，首先进行哈希得到其位置，如果这个位置已经占用了，那么再进行最多2次哈希，如果在哈希表中找到空位，那么就把数据保存到哈希表中。如果2次哈希后都没有找到空位，就把数据插入到最后一次哈希得到的位置上面挂着的平衡树去。
当同时登陆的用户不多的时候，可以在接近O（1）的时间级上查找到一个用户的数据，而同时登陆的用户数多的时候，也不会占用太多内存空间，虽然查找时间退化成O（logn），但是这个n的增长和用户数的增长并不成一比一的线性。虽然就理论的时间复杂度来看复杂度还是这么多，但是应用到实际中时，也可以在比较大的数据量下实现几乎是O（1）的时间复杂度。因为增加的用户首先要丢到哈希表里面，如果哈希冲突才会丢到平衡树里面，而两个用户被丢到同一个平衡树里面的概率是很小的，仅仅是哈希表长度的倒数。理论上来说，如果哈希表长度是1000的话，平均每增加1000个用户，每一棵平衡树才会增加1个节点。考虑到实际是应用到FTP服务器的，这样算下来，就算同时登陆的用户有8000个，最多也只需要访问6次内存就可以查找到到指定的用户数据了。
想想以前那个反迅雷的Serv-U插件，偶偷工减料用链表来保存用户数据，哎呀如果是8000个用户的话那平均要访问4000次内存啊，那可真是糟糕的说。好吧就算用平衡树，平均也要访问13次内存的说，比哈希树慢了一倍多。
这只是做 libantixunlei 扯出来的数据结构之一，另外为了高效地根据FTP指令序列来判断谁是迅雷，还扯出了另外一个数据结构，下次再说了。
ともたち
网站
F-22's Trace
greensea 的个人主页
sky-city
极夜奁
小樱之町
话说，B树是什么原理？
我也无视，搞ipv6这种东西还不如在地址里支持socks5实际一点
好吧，你可以字长以内hash，字长以外trie
ipv6没有普及所以ip地址是字长以内。。
实际上偶现在对IPv6还是无视的说 = =
因为精打细算之后，大部分的访问最多也就几百一千多个并发，酱子开个几千的哈希表会更快的说，内存也就钉死吃几十KB而已，高效低耗的说
几万的并发情况少……于是就丢到树里面了
啥意思，你可以用和hash一样大的那么多进制搞trie啊。。
虽然不如hash平衡，浪费一点内存
但是和指针有啥关系，hash你咋写的，就用啥方法不就行了？
顺利将 GS_ISAPI_Xunlei_Immune 在2008 X64上加载成功
这个东西。。如果那么肯浪费内存的话为什么不用trie，可以O(1)（按你这种计算方法的话。。）
算法导论上有弄出很多个不同的hash函数的方法，就是为了这种东西准备的
最初的时候想过，但是发现要么是指针是吃了太多内存，要么是查找一个值需要访问太多次内存的说
偶就知道有一次コナン里面有人说爆弾発見
貌似那还不素帮你改东西的
~~
那就更要拍死你了
偶都把号换回来了竟然还可以修改评论
貌似bug発見
要拍就拍波脖子去
其实这是好处，根据小甜饼判断这个留言是不是你留下的
哎亚怎么素你的号
貌似bug発見
总感觉这个hakken用在这里是不对的说
“发现”偶记得是有一个句型的说
而且明明是上次你进后台玩过的说
你才抽了
怎么就只剩下拍死你了呢。。。前面还有一句呢。。。怎么给删了。。。唉唉~~~~肯定有不可告人的秘密~~~
楼下那位抽了，请无视之
咱从来不修改别人的评论
拍死你