关于二分法和HASH表效率比较的问题

ouiki

问题从这个帖子引出来的:"关于将IP替换为国家地区的问题"(http://bbs.chinaunix.net/thread-4075374-1-1.html)。
那个帖子里，楼主想从 "IP范围-国家编码" 列表中查找一个IP属于哪个国家。
不少人推荐二分法查找。

关于这个，我有一个思路：
IP范围不计算成数字，就直接用IP段来表示。
比如说，如果是10.254.64.0/18的话，把这个IP段展开，每个IP作为KEY,CN作为Value，构建一个HASH表（字典？）：hash1。这么建表：
hash1={10.254.65 -> CN,
10.254.66 -> CN,
10.254.67 -> CN,
...
}

如果是10.254.10.0/24 CN。
hash1={10.254.10 -> CN} # 这一段刚刚写错了，改一下。

(大概是这么个意思，不用全部展开，只最小限展开就行)

对于一个IP：1.2.3.4
if (exists $hash1{"1"}) or exists $hash1{"1.2"})  or exists $hash1{"1.2.3"})  or exists $hash1{"1.2.3.4"}) {
       IP范围属于CN
}

个人觉得这种方法应该比二分法快（HASH决定的），但实际上效果并不理想（大概试了下，没太研究）。
想向各位请教，这种方法从根本上来说就是不如2分法，还是可以有优化的可能？

wenhq

个人认为，如果数据量足够大。比如说20000000000的话。hash的优势就出来了。

ouiki

IP列表太大的话，用这种方法，会不会有hash1过大(因为需要把IP段一定程度的分解)，从而导致效率变坏的问题？

rucypli

这个不是和数据库的B+树索引和hash索引的区别吗   速度上hash快些  内存占用肯定hash占用多  hash不支持范围查找

ouiki

rucypli 发表于 2013-04-10 10:33
这个不是和数据库的B+树索引和hash索引的区别吗   速度上hash快些  内存占用肯定hash占用多  hash不支持范围 ...

关于范围查找这个事，我是这么想的。
例如IP列表里有这么一条：10.10.0.0/12,我这么建HASH
hash1 = { 10.10 -> CN,
                10.11 -> CN
                ...
              }
如果是：10.10.0.0/17，这么建
hash1 = { 10.10.1 -> CN,
                10.10.2 -> CN
                ...
              }

所以对应一个要比较的IP:1.2.3.4
我只需要分四次看"1","1.2","1.2.3","1.2.3.4"是否存在于hash1中就行了，也就是范围比较。

seesea2517

厉害。关键是建表。
另外ＩＰ与地域的关系不是那么严肃，可以一大段ＩＰ做为一个 key。
随便说的，好像不大对。

ouiki

我心里没谱，来向大家请教这方法可行不。

wenhq

回复 4# rucypli


二分法的内存呢占用不多？相比hash？

   

手眼通天

一句话，hash是用空间换时间

ljwd1000

个人感觉，在mysql里建两张表，一条sql语句，是不是更快一些呢？