100分讨论一个关于验证IP是否在定义范围内的算法

Question

软件允许用户定义可登录的IP范围，允许多种格式多种定义添加，比如*.*.*.*,192.168.*.*,192.168.125.*这样的格式，在数据库里的对应字段allowableIP为varchar(4000),每个IP之间用分号来分隔。
这样，用户定义的一个allowableIP也许会出现如下形式
192.168.245.*;192.168.125.*;192.168.251.254;192.168.*.*;192.*.*.*;
当用户登录的时候，软件服务端首先要验证来自客户端的IP是否在允许的范围内。
比如这个来自客户端的srcIP为192.168.251.111
1.用indexOf看一下allowableIP是否有*.*.*.*,有的话就一律通过；
2.把allowableIP分解成一个arraylist
3.解析出srcIP的首地址为192，去匹配是否有192或者*打头的字符串，如果有打头就不是192或者*的，直接剔除
3.然后解析出srcIP的第二个地址为168，去匹配第二个地址是否有168，或者*，不是的直接删除
4.然后解析出srcIP的第三个地址，去匹配是否有251，或者*，不是的直接删除
5.然后解析出srcIP的第四个地址，去匹配是否有111，或者*，不是的直接删除
6.剩下的就是匹配的值，只要这个arraylist.size()>0，就是匹配觉得这个算法效率很一般，不知道有没有更好更快的方法？

Answer 1

java里一般不需要考虑算法，一般都有对应的容器实现
建议你
1）先把需要的内容读到hashmap里，做对应关系
2）把hashmap进行缓存
3）根据hashmap寻找对应关系来进行验证

Answer 2

char[] ch=new char[];
char[] cha=new char[];
if(ture){
ch=srcIp.split("\.")
if(ch.length!==3){
for(i=0,i<ch.length,i++){
if(cha[0]==192||cha[0].equals("*")){
   cha=ch[i];
}
  srcIP.delete();
   System.out.println("IP不符合要求");
if(K=0,k<ch.length,k++){
   代码同上
}
}}
   System.out.println("IP不符合要求");
}
      这个代码还得改才能用,写的不好,见笑了

Answer 3

以下观点供参考：
个人感觉楼主的算法在做正则表达式已经实现的工作
这里提供两种方案：
1.正则表达式
从数据库中把这些过滤列表拉出来
先用分号分割成数组
然后挂上４个小的正则
数组中每个元素用\\.分割了
然后依次判断
*就是0-255的正则
其他是啥就是啥
然后来个比对
确保生成的４个小正则没有重复的
比如某个是0-255
那其他的数字啥的就没意义了这些情况
最后把４个小正则用\\.连接起来进行匹配就行了
2.hash的方式
存储方式可以多种多样
hashmap应该就满足需求了
但对应关系比较难找
主是是*的问题
这个得慢慢想

Answer 4

很简单，把你数据库中的IP拼成正则表达式，然后用这个正则去匹配访问的IP
数据库IP——》正则的规则：把*替换成[1-255]
比如，数据库IP为 192.168.*.* ——》正则为192.168.[0-255].[0-255]当然，考虑到.是正则里的特殊符号，需要转移，故正则最后为 "192\\.168\\.[0-255]\\.[0-255]"
然后用访问的IP去匹配
测试程序如下public class Test { public static void main(String []args){
String ipRule = "192.168.*.*";
String ipReg = ipRule.replace(".", "\\.").replace("*", "[0-255]");//把IP规则替换为正则
String []testIps = new String[]{"192.168.1.1","192.168.256.1","192.158.256.1"};
for(String tempIp:testIps){
if(tempIp.matches(ipReg)){
System.out.println("合法IP: "+tempIp);
}
}
}

}

Answer 5

6楼处理的很简单明了。如果有多条匹配规则，在循环内再用个循环就可以了。如果要提高效率，觉得可以先对规则集进行处理（因为规则集的改动频率相比要小得多）：
（1）如果一条规则包含的范围在另一个条规则的内容，就可以删除这条规则。
（2）可以对规则进行排序，这样可以用HASH表来处理;也可以考虑其它办法，如用一个三重数组依次记录IP规则的前三个字节，这样每个字节匹配的复杂度为O（n），n为每个字节不同值的个数，如果规则集不是很多，占用的空间应该是可以接受的。表述的不是很清楚，觉得有价值的话，自己再想想吧。

Answer 6

ip是带十进制界点的，你怎么装换成整数，而且这么做很容易超过int的范围。个人认为6楼用正则很好

Answer 7

先转换成string，然后去掉“.”，再转换成整数。int不行就用long

Answer 8

  //将127.0.0.1形式的IP地址转换成十进制整数，这里没有进行任何错误处理  
     public static long ipToLong(String strIp) ...{  
         long[] ip = new long[4];  
         //先找到IP地址字符串中.的位置  
         int position1 = strIp.indexOf(".");  
         int position2 = strIp.indexOf(".", position1 + 1);  
         int position3 = strIp.indexOf(".", position2 + 1);  
         //将每个.之间的字符串转换成整型  
         ip[0] = Long.parseLong(strIp.substring(0, position1));  
         ip[1] = Long.parseLong(strIp.substring(position1+1, position2));  
         ip[2] = Long.parseLong(strIp.substring(position2+1, position3));  
         ip[3] = Long.parseLong(strIp.substring(position3+1));  
         return (ip[0] << 24) + (ip[1] << 16) + (ip[2] << 8) + ip[3];  
     }  
不转整数，就要考虑127.001.001.001的格式

Answer 9

不用那么复杂
package com.saturday.string;public class IPMatcher {
public static void main(String[] args){
String allowIp="192.168.245.*;192.168.125.*;192.168.251.254;192.168.*.*;192.*.*.*;";
String ip="192.168.251.111";

System.out.println(isIPAllow(allowIp,ip));
}

public static boolean isIPAllow(
String allowIp,
String ip){

String 
s1=ip,
s2=ip.replaceAll("\\.\\d+$", ".*"),
s3=ip.replaceAll("\\.\\d+\\.\\d+$", ".*.*"),
s4="*.*.*.*";

if(allowIp.indexOf(s1)>-1) return true;
if(allowIp.indexOf(s2)>-1) return true;
if(allowIp.indexOf(s3)>-1) return true;
if(allowIp.indexOf(s4)>-1) return true;

return false;
}
}

Answer 10

12楼的，没有考虑通配符*的情况，就没有测试13楼的代码我使用不同数据测试了一下，是正确可用的6楼的我测试了一下，当测试数据改成
String []testIps = new String[]{"192.168.1.1","192.168.256.1","192.168.253.1"};
的时候，应该有两个合理地址，即192.168.1.1和192.168.253.1，但是结果只返回了192.168.1.1，我对正则不大懂，不知道错在什么地方

Answer 11

更正6楼的程序，那个匹配0-255的正则我用 [0-255]是错误的，实际上[0-255]是匹配了0-2之间的，5，5也就是能匹配0，1，2，5这4个数，因此要匹配[0-255]应该“(([0-9])|([1-9][0-9])|([1-2][0-5][0-5]))”
测试如下public class Test {    public static void main(String []args){
        String ipRule = "192.168.*.*";
        String ipReg = ipRule.replace(".", "\\.").replace("*", "(([0-9])|([1-9][0-9])|([1-2][0-5][0-5]))");//把IP规则替换为正则
        String []testIps = new String[]{"192.168.1.555","192.168.256.1","192.168.253.10"}; 
        for(String tempIp:testIps){
            if(tempIp.matches(ipReg)){
                System.out.println("合法IP: "+tempIp);
            }
        }
    }}

Answer 12

(2[0-4]\d|25[0-5]|[01]?\d\d?){3}(2[0-4]\d|25[0-5]|[01]?\d\d?)

Answer 13

上面少点了哦((2[0-4]\d|25[0-5]|[01]?\d\d?)\.){3}(2[0-4]\d|25[0-5]|[01]?\d\d?)

Answer 14

这样的表结构设计得就不是很好，如果改成这样的话会更好一些1. ID              NUMBER(9)      PK
2. START_IP        VARCHAR2(15)
3. END_IP          VARCHAR2(15)
4. START_IP_VALUE  NUMBER(10)     根据 START_IP 转成的数值
5. END_IP_VALUE    NUMBER(10)     根据 END_IP 转成的数值192.168.245.*;192.168.125.*;192.168.251.254;192.168.*.*;192.*.*.*;  存为ID  START_IP         END_IP           START_IP_VALUE  END_IP_VALUE 
------------------------------------------------------------------
 1  192.168.245.0    192.168.245.255  3232298240      3232298495
 2  192.168.125.0    192.168.125.255  3232267520      3232267775
 3  192.168.251.254  192.168.251.254  3232300030      3232300030
 4  192.168.0.0      192.168.255.255  3232235520      3232301055
 5  192.0.0.0        192.255.255.255  3221225472      3238002687如果数据存储不能更改的话，那么可以这样做：public class IpTest {    public static void main(String[] args) {
        String ips = "192.*.*.*;192.168.125.*;192.168.251.254;192.168.245.*;192.168.*.*";
        IpContent content = new IpContent(ips);
        System.out.println(content.contains("193.173.0.1"));
    }
}import java.util.Arrays;
import java.util.regex.Pattern;public class IpContent {
    
    private final static String DEFAULT_SEPARATOR = ";";    private IpScope[] ipScopes;    
    
    public IpContent(String ips) {
        this( ips, DEFAULT_SEPARATOR);
    }
    
    public IpContent(String ips, String separator) {
        this( ips.split(Pattern.quote(separator)) );
    }
    
    public IpContent(String[] ipsArray) {
        init(ipsArray);
    }
    
    public boolean contains(String ip) {
        if(ipScopes == null || ipScopes.length == 0) {
            return false;
        }
        long ipValue = IpUtil.ip2Number(ip);
        for(int i = 0; i < ipScopes.length; i++) {
            if(ipScopes[i].contains(ipValue)) {
                return true;
            }
        }
        return false;
    }
    
    private void init(String[] ipsArray) {
        if(ipsArray == null || ipsArray.length == 0) {
            return;
        }
        ipScopes = new IpScope[ipsArray.length];
        for(int i = 0; i < ipsArray.length; i++) {
            ipScopes[i] = new IpScope(ipsArray[i]);
        }
        Arrays.sort(ipScopes);
    }
    
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < ipScopes.length; i++) {
            sb.append(ipScopes[i]).append("\n");
        }
        return sb.toString();
    }
}public class IpScope implements Comparable<IpScope> {    public final static String FUZZY_PLACEHOLDER = "*";
    public final static String IP_MIN_VALUE = "0";
    public final static String IP_MAX_VALUE = "255";    private String ip;    private long startIpValue;
    private long endIpValue;    IpScope(String ip) {
        this.ip = ip;
        processIpValue();
    }    public String getIp() {
        return ip;
    }
    public String getStartIp() {
        return IpUtil.number2Ip(startIpValue);
    }
    public String getEndIp() {
        return IpUtil.number2Ip(endIpValue);
    }
    public long getStartIpValue() {
        return startIpValue;
    }
    public long getEndIpValue() {
        return endIpValue;
    }    public boolean contains(long ipValue) {
        return (ipValue >= startIpValue) && (ipValue <= endIpValue);
    }    private long diff() {
        return endIpValue - startIpValue;
    }    private void processIpValue() {
        String[] ips = ip.split("\\.");
        startIpValue = toNumber(ips.clone(), IP_MIN_VALUE);
        endIpValue = toNumber(ips.clone(), IP_MAX_VALUE);
    }    private long toNumber(String[] ips, String defaultValue) {
        for(int i = 0; i < ips.length; i++) {
            ips[i] = ips[i].trim();
            if(FUZZY_PLACEHOLDER.equals(ips[i])) {
                ips[i] = defaultValue;
            }
        }
        return IpUtil.ip2Number(ips);
    }    public int compareTo(IpScope o) {
        long diff = this.diff() - o.diff();
        if(diff > Integer.MAX_VALUE) {
            return Integer.MIN_VALUE;
        }
        return -(int)diff;
    }    public String toString() {
        return "IP pattern: " + ip + ", start: " + getStartIp() + ", end: " + getEndIp();
    }
}public class IpUtil {    /**
     * 将 IP 字符串转为  long 数据
     * @param ip
     * @return
     * @author frankiegao123
     * 2010-2-26 下午03:47:14
     */
    public static long ip2Number(String ip) {
        String[] s = ip.split("\\.");
        return ip2Number(s);
    }    public static long ip2Number(String[] ips) {
        long ipn = 0L;
        for (int i = 0; i < ips.length; i++) {
            ipn = (ipn << 8) | Long.parseLong(ips[i]);
        }
        return ipn;
    }    /**
     * 以字符串形式表示的 IP 地址
     * @param number
     * @return
     * @author frankiegao123
     * 2010-2-26 下午03:47:35
     */
    public static String number2Ip(long number) {
        char[] chs = new char[15];
        int offset = 0;
        for (int i = 1; i <= 4; i++) {
            if(i > 1) {
                chs[offset++] = '.';
            }
            int shift = (4 - i) * 8;
            int n = (int) ((number & (0xff << shift)) >>> shift);
            offset = putChar(chs, offset, n);
        }
        return new String(chs, 0, offset);
    }    private static int putChar(char[] chs, int offset, int number) {
        int len = length(number);
        int t = len;
        while(t > 0) {
            chs[--t + offset] = (char)('0' + number % 10);
            number /= 10;
        }
        return offset + len;
    }    private static int length(int number) {
        int len = 1;
        while(number > 9) {
            number /= 10;
            len++;
        }
        return len;
    }
}

Answer 15

实际上也没多少代码，IpUtil 只是一个工具类是一次工作，大多数的代码都在这里，都是一些 IP 字符串与 IP 值之间的转换。其他两个类的代码也不是很多呀。

Answer 16

如果存 数据库的话。那你可以把 192.168.125.*，存进4个int字段，192-168-125-（-1）
然后select count(id) from table where (a1=192 or a1=-1) and (a2=163 or a2=-1) ...
（不过速度未知，有待测试）