阿里-蚂蚁金服笔试题目–ip黑/白名单工具接口

群里有朋友参加了蚂蚁金服的笔试,发了一个笔试题目出来。

/**
    * ip黑/白名单工具接口, 请为本interface实现一个基于内存的ip黑/白名单具体实现类
    * 要求’isInList’操作为常数级时间复杂度
    * 要求’isInList’内部操作完全基于内存,不得有网络或文件读取; 对象初始化部分如构造函数则不受此限制(如初始化时可从文件中load ip名单列表)
    * 程序设计上,请在满足上述条件的前提下,让此工具所能支持的ip列表数量尽可能大(甚至能否覆盖整个ipv4地址空间?), 内存占用尽可能小;
    * 此工具可能在多线程环境被使用
    */
public interface IpList
{
    /**
    * 判断指定的ipv4地址是否在当前名单中
    *
    * @param ip
    *            指定的ip地址值(v4)
    * @return true: 在名单中, false: 不在名单中
    */
    boolean isInList(String ip);
}

初看这道题好像并不复杂,但是多读两遍题目就发现其实有很多细节在里面。
不得不说阿里的面试题质量确实非常高,就这一道普通的笔试题,其实就包含了许多考点。

首先说我拿到这道题的想法:虽然传入的ipv4是String,但是其实我们只需要32个bit即一个int就能保存下来,然后使用HashSet判断是否包含了此ip。算了算,加上网络号、广播地址和私有地址,一共有2^32个ip地址,一个地址4字节,算起来一共需要16G内存来存储。
那么用HashSet来实现是这样的:

package ali;

import java.util.HashSet;

public class HashSetIpList implements IpList {

    private HashSet<Integer> ipSet = null;

    public HashSetIpList() {
        ipSet = new HashSet<>();
        ipSet.add(ipToInt("192.168.1.3"));
    }

    @Override
    public boolean isInList(String ip) {
        return ipSet.contains(ipToInt(ip));
    }

    /**
     * 将ip字符串转化为整数
     * @param ip
     * @return
     */
    private int ipToInt(String ip) {
        int ret = 0;
        String[] ipStr = ip.split("\\.");
        for (int i = 0; i < 4; i++) {
            ret <<= 8;
            ret += Integer.valueOf(ipStr[i]);
        }
        return ret;
    }
}

不过这里在load ip列表时最好先获取ip的个数,确定HashSet的大小,防止扩容带来的影响。

但是群里有小伙伴提到应该使用BitMap算法来解决这个问题,想了想,如果说覆盖整个ipv4地址空间的话BitMap确实更加节省内存,因为只需要2^32个bit,即512M。那么我们就用BitMap来试试。

这里我准备用java.util.BitSet来做,但是刚开始就发现了问题。看BitSet的构造函数:

public BitSet(int nbits) {
    // nbits can't be negative; size 0 is OK
    if (nbits < 0)
        throw new NegativeArraySizeException("nbits < 0: " + nbits);

    initWords(nbits);
    sizeIsSticky = true;
}

虽然int有32个bit,但是最高位是符号位,所以这里最终会报NegativeArraySizeException。看来我们需要有针对性的自己来实现一个BitMap了。

public class BitMapIpList implements IpList {
    private IpSet ipSet = null;

    public BitMapIpList() {
        ipSet = new IpSet();
        ipSet.set(ipToLong("192.168.1.1")); // 1100 0000 . 1010 1000 . 0000 0001 . 0000 0001
    }

    @Override
    public boolean isInList(String ip) {
        return ipSet.get(ipToLong(ip));
    }

    /**
     * 将字符串形式的ip地址转换为整数
     * 由于int会出现负数,所以返回long
     * @param ip
     * @return
     */
    private long ipToLong(String ip) {
        long ret = 0;
        String[] ipStrArr = ip.split("\\.");
        for (int i = 0; i < 4; i++) {
            ret <<= 8;
            ret += Long.valueOf(ipStrArr[i]);
        }
        return ret;
    }

    private class IpSet {
        /**
         * 一共有2^32个ip地址,即需要2^32个bit来保存,
         * 那么我们一共需要(2^32)/64 == 2^26个long来保存。
         */
        private long[] words;

        public IpSet() {
            words = new long[1 << 26];
        }

        public void set(long bitIndex) {
            int arrIndex = (int)(bitIndex >> 6);
            words[arrIndex] |= (1L << bitIndex);
        }

        public boolean get(long bitIndex) {
            int arrIndex = (int)(bitIndex >> 6);
            return (words[arrIndex] & (1L << bitIndex)) != 0;
        }

    }
}

简单测试一下:

public class Main {
    public static void main(String[] args) {
        IpList iplist = new BitMapIpList();

        System.out.println(iplist.isInList("192.168.1.1"));
        System.out.println(iplist.isInList("192.168.1.2"));
    }
}
true
false

看上去是通过了,如果有问题请大家评论区告知一下,另外运行的时候看了一下,确实只用了512M内存。
不过顺便说一下,要求中“对象初始化部分如构造函数则不受此限制(如初始化时可从文件中load ip名单列表)”,是不是还顺便考察了一下NIO?这里我就懒得实现了。

看到这里,大家是不是觉得这道题稳了?

Too Young

为什么这么说呢?重点来了,看要求:“程序设计上,请在满足上述条件的前提下,让此工具所能支持的ip列表数量尽可能大(甚至能否覆盖整个ipv4地址空间?), 内存占用尽可能小;”
看上去好像没问题,但是这是阿里的笔试题,总感觉还能再深入。
不知道大家有没有想起HashMap,在jdk1.8版本后,java对HashMap做了改进,在链表长度大于8的时候,将链表转换为红黑树,这也是出于性能考虑。
那么针对这一道题,我们的内存占用是否做到了尽可能小呢?
答案是没有。

我们之前计算的内存占用都是基于“覆盖整个ipv4地址空间”来说的,但是实际场景中我们的黑白名单可能并不会太大,比如我们的黑名单中只有100个ip,如果使用BitMap方法,不论多少ip我们都需要512M内存,但是如果我们使用HashSet,针对这种较少ip的情况,就可以进一步节省内存空间。

首先我们需要计算一下阈值,BitMap方法固定的需要512M内存,那么用HashSet的话,512M内存能存多少ip呢?
512 * 1024 * 1024 / 4 = 134217728个ip。
也就是说,在load进入内存前先获取一下ip的个数,低于这个临界值,那么我们使用HashSet来处理更加节省内存,而超过这个临界值,我们就需使用BitMap。

最后还有一个要求:“此工具可能在多线程环境被使用”。
也许有朋友觉得这个好办,加个锁就行了,但是我不这么认为。针对这道题目,我们只是实现了isInList方法,这里面只是读取,并不存在增删操作,所以肯定不需要加锁的。
我的理解是,这个工具类是比较耗内存的,多线程环境中使用的话,肯定不能说每一个线程都new一个IpList,所以这里需要实现线程安全的单例模式。

后面的这些改进想法,等有时间(基本上就是没时间)的时候再实现吧,先睡觉了。

“阿里-蚂蚁金服笔试题目–ip黑/白名单工具接口”的一个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据