昨晚Daniel跟我讲，百度面他了，都保研了，还骗面试，太坏了~
说问道他一道题，题是这样的：
有好多ip，保存在一个文件里面，这些ip是禁止访问的，ip的个数约有10w左右。
给你ip，如何快速判断此ip是不是禁止的ip。
讨论了下，想了几个解决方案，都是比较简单的，有更好的，欢迎网友补充。
1.最笨的方法，每遇到一个ip，就依次从文件开头找，一次查找的复杂度是O(n)
2.先把文本里的ip排序，每遇到一个ip，就用二分方法找，一次查找的复杂度是O(logn)
3.考虑到ip是以a.b.c.d格式表示的，可以做一个四层的trie树，每个父节点有256个子节点，但是这样太占空间，查找也比较慢，可以这样妥协一下：在每个父亲节点里面，加上8个int，共256bit，用bitmap来表示是否有此禁止ip，然后子节点用list记录。每次查找，先去bitmap里找有没有，有的话去list里面找下一层的指针。感觉比较麻烦。
4.用哈希。既然是10w的规模，可以找一个质数M，使得M是第一个大于10w的质数，这是一些 100003 100019 100043 100049 100057 100069 100103 100109 100129 100151 100153 100169 100183 100189 100193 100207 100213 100237 100267...
然后，建一个大小为M的table，然后对每个禁止ip进行哈希，得到一个哈希值，然后对M取模，插入到对应的table位置下。然后对每个判断的ip，进行哈希，到算出的位置找下有没有就可以了。至于哈希函数，我想个最简单的， ip是32bit表示的，可以用unsigned int表示，直接用这个unsigned int %M，就得到一个一个值了。。。
5.这个最直接了，直接 对ip进行bitmap，ip用32位bit表示，那么我们申请一个2^32/32的unsigned int数组，然后用来表示每个ip是禁止就OK了，我在自己电脑上做实验，可以开这么大的uint数组的，占内存这个bitmap占内存有512M。。。
扔个砖，欢迎回砸 呵呵
阅读(780) | 评论(1) | 转发(0) |
