基于Ip过滤功能分析集合及String的contains实现

文章目录

1. 概要：
2. 正文：
3. 总结：

概要：

本文主要通过对比集合及String的contains实现的不同及各自的特点，解决了ip过滤功能开发时的效率及准确性问题。

正文：

需求很明确，在下单操作之前进行用户的ip判断，如果用户申请了ip白名单机制，那么在数据库会保存有一条ip列表记录，通过英文半角逗号分割。类似如下的格式

192.168.22.01,192.168.22.01,192.168.22.03

通过用户的id可以查到这个lp列表，并将用户传来的ip值与该列表中的元素进行比对，符合则放行否则认为请求不合法。
如果该数据表中没有记录，则认为用户没有申请ip白名单机制，则走默认的逻辑。

我刚开始的想法是通过id取出记录ipList之后直接将用户的远程remoteIp与这个列表进行比对，通过java.lang.String的contains方法判断ipList.contains(remoteIp)是否为true。

原始代码如下

if (ipList.contains(remoteIp)) {
    return true;
}
return false;

在测试中执行正常，但总感觉那里不对劲。和高手讨论了之后，确实觉得不妥。原因如下

IPV4地址的格式默认是xxx.xxx.xxx.xxx，当对列表进行截取的时候要保证不会跨“逗号”(,)，即保证至少有三个连续的点(.)都被包含，那么就有如下的情况出现（中间的不受影响）

xx.xxx.xxx.xxx
xx.xxx.xxx.xx
xx.xxx.xxx.x
x.xxx.xxx.xxx
x.xxx.xxx.xx
x.xxx.xxx.x

就会有这样的场景出现：

用户的远程ip列表是116.213.22.555,153.34.232.11
合法用户使用116.213.22.555或153.34.232.11是可以正常的走程序的逻辑，而不法用户如果使用

116.213.22.55，
116.213.22.5，
16.213.22.555，
6.213.22.555,
或者153.34.232.1，
53.34.232.11，
3.34.232.11

就可以通过验证进入正常的下单逻辑，造成损失。

在这里我也考虑了一下ip地址的类型，简单的补充一下

1.A类地址
A类地址的表示范围为：0.0.0.0~126.255.255.255，默认网络掩码为：255.0.0.0；
A类地址分配给规模特别大的网络使用。A类网络用第一组数字表示网络本身的地址，
后面三组数字作为连接于网络上的主机的地址。分配给具有大量主机（直接个人用户）
而局域网络个数较少的大型网络。例如IBM公司的网络。
2.B类地址
B类地址的表示范围为：128.0.0.0~191.255.255.255，默认网络掩码为：255.255.0.0；
B类地址分配给一般的中型网络。B类网络用第一、二组数字表示网络的地址，
后面两组数字代表网络上的主机地址。
3.C类地址
  C类地址的表示范围为：192.0.0.0~223.255.255.255，默认网络掩码为：255.255.255.0；
  C类地址分配给小型网络，如一般的局域网和校园网，它可连接的主机数量是最少的，
  采用把所属的用户分为若干的网段进行管理。C类网络用前三组数字表示网络的地址，
  最后一组数字作为网络上的主机地址。

习惯上A类地址已经消费的差不多了，因此前8位的十进制在0-126的可以认为是可忽略的，但是如果出现在B类地址中进行截取的情况也是不可忽略的，因此简单的使用String.contains方法进行判断是不合理的。

String的contains方法的实现如下

public boolean contains(CharSequence s) {
    return indexOf(s.toString()) > -1;
}

可见内部是调用了indexOf方法

public int indexOf (String str) {
    return indexOf(str, 0);
}

文档介绍如下

返回指定子字符串在此字符串中第一次出现处的索引，从指定的索引开始。返回的整数是满足下式的最小 k 值： 
     k >= Math.min(fromIndex, this.length()) && this.startsWith(str, k)

如果不存在这样的 k 值，则返回 -1。 
参数： 
str - 要搜索的子字符串。 
fromIndex - 开始搜索的索引位置。 
返回： 
指定子字符串在此字符串中第一次出现处的索引，从指定的索引开始。

分析得知是通过循环的方式从前往后匹配，因此我们之前的分析是正确的。

于是考虑采用较为稳妥的方式。
由于用户的ip白名单是静态配置的，因此可以对这个列表字符串进行以“，”为标记的分割，将其分割为若干个ip串，并放入一个集合，再调用集合的contains进行判断。
List的contains方法的介绍如下：

contains
public boolean contains(Object o)
如果此列表中包含指定的元素，则返回 true。更确切地讲，当且仅当此列表包含至少一个满足 (o==null ? e==null : o.equals(e)) 的元素 e 时，则返回 true。 
指定者： 
接口 Collection<E> 中的 contains 
指定者： 
接口 List<E> 中的 contains 
覆盖： 
类 AbstractCollection<E> 中的 contains
参数： 
o - 测试此列表中是否存在的元素 
返回： 
如果此列表包含特定的元素，则返回 true

简单分析可以发现是将集合元素与来源元素逐个对比，因此可行。为了进一步确认可行性，查看一下源码实现。
ArrayList的contains实现如下

public boolean contains(Object o) {return indexOf(o) >= 0; }

内部调用了indexOf方法如下

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
        if (elementData[i]==null)
            return i;
    } else {
        for (int i = 0; i < size; i++)
        if (o.equals(elementData[i]))
            return i;
    }
    return -1;
}

可见其是通过循环遍历的方式逐个比较，返回匹配的元素下标是可行的。因为来源ip不会是null，数据库中原则上也不会保存为null的ip列表。

这里又多想了一步，如果ip列表变得很大，ArrayList的contains查找到目标的时间会变得很长，最坏的情况是匹配到了列表的最后，时间复杂度为O(n)影响用户体验。考虑将其转换为Set使用set的contains方法。
HashSet的contains实现如下

public boolean contains(Object o) {
    return map.containsKey(o);
}

可见其内部是调用了map的containsKey进行查找的，而map的containsKey内部是通过getEntry实现查找匹配的，通过hashcode查找对应的元素，时间复杂度为O(1)，查找效率很快。因此考虑最终的实现是

String merchantIpList = "xxx.xxx.xx.xxx,xxx.xxx.xxx.xx";
List<String> ipArrayList = Arrays.asList(merchantIpList.split(","));
Set<String> ipSet = new HashSet<String>();
ipSet.addAll(ipArrayList);
if (ipSet.contains(merchantRemoteIp)) {
    return true;
}
return false;

简单解释就是

通过逗号分割ip列表为ip数组，每个元素为一个标准的ip字符串
将ip数组转为List并放入一个HashSet中
通过HashSet的contains方法进行匹配得出是否匹配成功

总结：

本文主要对String以及ArrayList和HashSet的内部原理结合一个实例进行了比对，在开发中采用合理的方式能够提高业务的准确性和易用性，这对我们来讲是很必要的。

朝·闻·道

SnoWalker's Blog

基于Ip过滤功能分析集合及String的contains实现

概要：

正文：

总结：