快速查找IP地址所属范围_如何算ip得知那个ip range内

题目描述

10.20.30.0-10.20.30.128101.201.30.0-101.201.40.128102.201.30.0-102.201.40.128202.20.30.1
vector<int> vec1_min;{10,20,30,0}
vector<int> vec1_max;{10,20,30,128}
vector<int> vec2_min;
vector<int> vec2_max;
vector<int> vec3_min;
vector<int> vec3_max;Hash(IP)
vector<vector<int>> ip_vec_2d
sort(ip_vec_2d)[1,5][4,7][1,7]query(string ip){returntrueorfalse}21031009
binary_search
3

参考

代码实现

JAVA工程路径【maven】
E:\CodeRepo\alg\alg\java\interview

实现代码路径

E:\CodeRepo\alg\alg\java\interview\src\main\java\com\shouyanxiang\locateIPRange

工程依赖

E:\CodeRepo\alg\alg\java\interview\pom.xml

<?xml version="1.0" encoding="UTF-8"?><projectxmlns=""xmlns:xsi=""xsi:schemaLocation=""><modelVersion>4.0.0</modelVersion><groupId>com.shouyanxiang</groupId><artifactId>interview</artifactId><version>1.0</version><name>interview</name><!-- FIXME change it to the project's website --><url></url><properties><project.build.sourceEncoding>UTF-8</project.build.sourceEncoding><maven.compiler.source>1.8</maven.compiler.source><maven.compiler.target>1.8</maven.compiler.target></properties><dependencies><dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>4.11</version><scope>test</scope></dependency><dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId><version>1.18.4</version><scope>provided</scope></dependency></dependencies><build><pluginManagement><!-- lock down plugins versions to avoid using Maven defaults (may be moved to parent pom) --><plugins><!-- clean lifecycle, see  --><plugin><artifactId>maven-clean-plugin</artifactId><version>3.1.0</version></plugin><!-- default lifecycle, jar packaging: see  --><plugin><artifactId>maven-resources-plugin</artifactId><version>3.0.2</version></plugin><plugin><artifactId>maven-compiler-plugin</artifactId><version>3.8.0</version></plugin><plugin><artifactId>maven-surefire-plugin</artifactId><version>2.22.1</version></plugin><plugin><artifactId>maven-jar-plugin</artifactId><version>3.0.2</version></plugin><plugin><artifactId>maven-install-plugin</artifactId><version>2.5.2</version></plugin><plugin><artifactId>maven-deploy-plugin</artifactId><version>2.8.2</version></plugin><!-- site lifecycle, see  --><plugin><artifactId>maven-site-plugin</artifactId><version>3.7.1</version></plugin><plugin><artifactId>maven-project-info-reports-plugin</artifactId><version>3.0.0</version></plugin></plugins></pluginManagement></build></project>

注意

maven compiler版本号

<maven.compiler.source>1.8</maven.compiler.source><maven.compiler.target>1.8</maven.compiler.target>

中的版本号需>=1.8，否则不支持

Collections.sort(ipBeanList,Comparator.comparingLong(IPBean::getBegin));

中的lamda表达式

引入lombok依赖

<dependencies><dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>4.11</version><scope>test</scope></dependency><dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId><version>1.18.4</version><scope>provided</scope></dependency></dependencies>

org.projectlombok 为java class提供修饰符
E:\CodeRepo\alg\alg\java\interview\src\main\java\com\shouyanxiang\locateIPRange\IPBean.java

@Data@NoArgsConstructor@AllArgsConstructor

存放IP地址段信息

E:\CodeRepo\alg\alg\java\interview\src\main\java\com\shouyanxiang\locateIPRange\IPBean.java

packagecom.shouyanxiang.locateIPRange;importlombok.AllArgsConstructor;importlombok.Data;importlombok.NoArgsConstructor;@Data@NoArgsConstructor@AllArgsConstructorpublicclassIPBean{// 起始 IPprivatelong begin;// 终止 IPprivatelong end;// 国家privateString country;// 省份privateString region;// 城市privateString city;// 位置编码privateString code;}

二分法查找输入IP地址所属范围

E:\CodeRepo\alg\alg\java\interview\src\main\java\com\shouyanxiang\locateIPRange\IPUtil.java

packagecom.shouyanxiang.locateIPRange;// import com.shouyanxiang.locateIPRange.IPBean;publicclassIPUtil{/**
     * 根据ip地址判断属于哪个ip地址段，返回这个段的ip地址对象
     * 使用二分查找算法来实现
     * 
     * @param ip
     * @return
     */publicstaticIPBeangetIPByHalf(String ip){IPBean[] ipBeans =IpAnalyse.ipBeans;if(ipBeans ==null|| ipBeans.length ==0){returnnull;}long iplong =IPUtil.ipToLong(ip);if(iplong < ipBeans[0].getBegin()|| iplong > ipBeans[ipBeans.length -1].getEnd()){returnnull;}int low =0;int high = ipBeans.length -1;// 不能使用 int mid = (left + right) / 2,如果 low 和 high 比较大的话，两者之和就有可能会溢出int mid = low +((high - low)>>>1);// 当两个指针同时指向同一个数据时,需用 = 判断while(low <= high){if(iplong < ipBeans[mid].getBegin()){
                high = mid -1;}elseif(iplong > ipBeans[mid].getBegin()){
                low = mid +1;}if(iplong >= ipBeans[mid].getBegin()&& iplong <= ipBeans[mid].getEnd()){return ipBeans[mid];}
            mid =(low + high)/2;}returnnull;}/**
     * ip地址转成long型数字
     * 将IP地址转化成整数的方法如下：
     * 1、通过String的split方法按.分隔得到4个长度的数组
     * 2、通过左移位操作（<<）给每一段的数字加权，第一段的权为2的24次方，第二段的权为2的16次方，第三段的权为2的8次方，最后一段的权为1
     * 
     * @param strIp
     * @return
     */publicstaticlongipToLong(String strIp){String[] ip = strIp.split("\\.");return(Long.parseLong(ip[0])<<24)+(Long.parseLong(ip[1])<<16)+(Long.parseLong(ip[2])<<8)+Long.parseLong(ip[3]);}/**
     * 将十进制整数形式转换成127.0.0.1形式的ip地址
     * 将整数形式的IP地址转化成字符串的方法如下：
     * 1、将整数值进行右移位操作（>>>），右移24位，右移时高位补0，得到的数字即为第一段IP。
     * 2、通过与操作符（&）将整数值的高8位设为0，再右移16位，得到的数字即为第二段IP。
     * 3、通过与操作符吧整数值的高16位设为0，再右移8位，得到的数字即为第三段IP。
     * 4、通过与操作符吧整数值的高24位设为0，得到的数字即为第四段IP。
     * 
     * @param longIp
     * @return
     */publicstaticStringlongToIP(long longIp){StringBuffer sb =newStringBuffer();// 直接右移24位
        sb.append((longIp >>>24));
        sb.append(".");// 将高8位置0，然后右移16位
        sb.append(((longIp &0x00FFFFFF)>>>16));
        sb.append(".");// 将高16位置0，然后右移8位
        sb.append(((longIp &0x0000FFFF)>>>8));
        sb.append(".");// 将高24位置0
        sb.append((longIp &0x000000FF));return sb.toString();}}

处理输入输出

E:\CodeRepo\alg\alg\java\interview\src\main\java\com\shouyanxiang\locateIPRange\IpAnalyse.java

packagecom.shouyanxiang.locateIPRange;importjava.util.Arrays;importjava.util.List;importjava.io.BufferedReader;importjava.io.File;importjava.io.FileInputStream;importjava.io.IOException;importjava.io.InputStreamReader;importjava.nio.charset.StandardCharsets;importjava.util.Collections;importjava.util.LinkedList;importjava.util.logging.Logger;importjava.util.stream.Collectors;importjava.util.Comparator;// import com.shouyanxiang.locateIPRange.IPBean;// import java.lang.System.Logger;importlombok.AllArgsConstructor;importlombok.Data;importlombok.NoArgsConstructor;publicclassIpAnalyse{privatestaticLogger logger =Logger.getLogger(IpAnalyse.class.getName());publicstaticIPBean[] ipBeans;/**
     * 读取ipdb.txt文件，按行读取，并转成IPBean对象数组
     * 
     * @param filePath
     * @throws IOException
     */publicstaticvoidload(String filePath)throwsIOException{
        logger.info("load ip db,path:"+ filePath);InputStreamReader inputStreamReader =null;BufferedReader reader =null;try{File file =newFile(filePath);// 判断文件是否存在if(file.isFile()&& file.exists()){
                inputStreamReader =newInputStreamReader(newFileInputStream(file),StandardCharsets.UTF_8);
                reader =newBufferedReader(inputStreamReader);String line;LinkedList<IPBean> ipBeanList =newLinkedList<>();// List<IPBean> ipBeanList = new LinkedList<>();while((line = reader.readLine())!=null){// String[] tmp = line.split("\t");String[] tmp = line.split(" ");IPBean ipBean =newIPBean(IPUtil.ipToLong(tmp[0]),IPUtil.ipToLong(tmp[1]), tmp[2], tmp[3], tmp[4],
                            tmp[5]);
                    ipBeanList.add(ipBean);}Collections.sort(ipBeanList,Comparator.comparingLong(IPBean::getBegin));/*
                 * acs
                 * .stream()
                 * .sorted(Comparator.comparingLong(AC::getId)) //sorted by id here
                 * .collect(Collectors.toList());
                 */// ipBeanList// .stream()// .sorted((a, b) -> Long.compare(a.getBegin(), b.getBegin())) // sorted by id// here// .collect(Collectors.toList());// ipBeanList.sort(Comparator.comparingLong(IPBean::getBegin));
                ipBeans = ipBeanList.toArray(newIPBean[]{});}else{
                logger.info("找不到指定的文件");}}catch(Exception ex){
            logger.info("读取文件内容出错");
            ex.printStackTrace();}finally{
            inputStreamReader.close();
            reader.close();}}publicstaticIPBeanfind(String ip){returnIPUtil.getIPByHalf(ip);}publicstaticvoidmain(String[] args){try{// "E:\\CodeRepo\\alg\\alg\\java\\interview\\input_text\\ip.txt"IpAnalyse.load("E:\\CodeRepo\\alg\\alg\\java\\interview\\input_text\\ip.txt");System.out.println("查询前时间"+System.currentTimeMillis());String ip ="223.255.204.100";IPBean ipBean =find(ip);System.out.println(ipBean);System.out.println("查询后时间"+System.currentTimeMillis());}catch(Exception e){
            e.printStackTrace();}}}

debug 代码

IP地址范围存储文件

E:\CodeRepo\alg\alg\java\interview\input_text\ip.txt
各字段以空格，即 " " 隔开

223.255.36.0 223.255.36.255 中国 北京 北京 156001000000223.255.37.0 223.255.37.255 中国 吉林 长春 156021000001223.255.38.0 223.255.41.255 中国 北京 北京 156001000000223.255.42.0 223.255.43.255 中国 湖北 武汉 156013000001223.255.44.0 223.255.127.255 中国 北京 北京 156001000000223.255.128.0 223.255.191.255 中国 香港 * 344033000000223.255.192.0 223.255.202.255 韩国 韩国 * 410000000000223.255.203.0 223.255.203.255 日本 日本 * 392000000000223.255.204.0 223.255.205.255 韩国 韩国 * 410000000000223.255.206.0 223.255.206.255 日本 日本 * 392000000000

终端输出

PS E:\CodeRepo\alg\alg\java\interview>  e:;cd'e:\CodeRepo\alg\alg\java\interview';&'E:\jdk17\bin\java.exe''-agentlib:jdwp=transport=dt_socket,server=n,suspend=y,address=localhost:56518''-XX:+ShowCodeDetailsInExceptionMessages''@C:\Users\SHOUYA~1\AppData\Local\Temp\cp_c4pdat27xhl3i66ovgn9p4dav.argfile''com.shouyanxiang.locateIPRange.IpAnalyse'11月 26, 20224:22:52 上午 com.shouyanxiang.locateIPRange.IpAnalyse load
信息: load ip db,path:E:\CodeRepo\alg\alg\java\interview\input_text\ip.txt
查询前时间1669407772680
IPBean(begin=3758083072, end=3758083583, country=韩国, region=韩国, city=*, code=410000000000)
查询后时间1669407772680