16boke - 一路博客

java版ip地址段的查找

在工作中经常会遇到将ip地址段进行按地域或者时区进行归类,再给定一个ip地址判断此ip属于哪个城市或者哪个时区,这时就需要对ip地址段进行指定值的查找,现在有这样一个ipcode.txt文本文件,输入一个ip地址得到对应的code。

1、ipcode.txt文件内容

用逗号分隔,第一位为起始ip,第二位为结束ip,第三位为编码,也可以为时区、地域等。

注意:ip地址段提前已经排序过的

1.1.1.1,1.2.1.1,a
1.2.1.2,1.5.1.1,b
1.5.1.2,3.1.1.1,c
3.1.1.2,5.1.1.1,d
5.1.1.2,11.1.1.1,e
11.1.1.2,20.1.1.1,f
20.1.1.2,50.1.1.1,g
50.1.1.2,100.1.1.1,h

2、ip地址转整数

由于需要对ip地址进行比较以确定在哪个段中,所以需要将ip地址转为整数。如果不转也可以自己实现将ip地址按点来分隔,每位进行比较,但是这样会比较麻烦,所以最好的办法还是将ip地址转为整数。关于如何将ip地址转为整数请参考:java版ip地址与整数的互相转换

3、顺序查找

第一解决办法大家肯定会想到顺序查找,将文件按行读取,对每行进行逗号分隔,判断目标值是否在第一位和第二位之间,然后输出code。现在我就提供顺序查找的代码:

/**
	 * 读取ipcode.txt文件,按行读取,并转成IPBean对象数组
	 * @return
	 */
	public static IPBean[] getIpBeans() {
		InputStreamReader inputStreamReader = null;
		BufferedReader reader = null;
		try {
			File file = new File(TestHalf.class.getResource("ipcode.txt").getPath());
			inputStreamReader = new InputStreamReader(new FileInputStream(file), "UTF-8");
			reader = new BufferedReader(inputStreamReader);
			String line;
			LinkedList<IPBean> ipBeanList = new LinkedList<IPBean>();
			while ((line = reader.readLine()) != null) {
				String[] tmp = line.split(",");
				ipBeanList.add(new IPBean(IPUtil.ipToLong(tmp[0]), IPUtil.ipToLong(tmp[1]), tmp[2]));
			}
			IPBean[] ipBeans = ipBeanList.toArray(new IPBean[] {});
			return ipBeans;
		} catch (Exception ex) {
			ex.printStackTrace();
		} finally {
			try {
				reader.close();
				inputStreamReader.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return null;
	}
/**
	 * 根据ip地址判断属于哪个ip地址段,返回这个段的ip地址对象
	 * 使用顺序查找来实现
	 * @param ip
	 * @param ipBeans
	 * @return
	 */
	public static IPBean getIP(String ip) {
		IPBean[] ipBeans = getIpBeans();
		if (ipBeans == null || ipBeans.length == 0)
			return null;
		long iplong = IPUtil.ipToLong(ip);
		if (iplong < ipBeans[0].getBegin() || iplong > ipBeans[ipBeans.length - 1].getEnd())
			return null;
		for(IPBean ipBean:ipBeans){
			if(ipBean.getBegin()<=iplong && ipBean.getEnd()>=iplong)
				return ipBean;
		}
		return null;
	}

这种解决办法在ipcode.txt文件很小或者条数很少的情况下还是有不错的性能的,但是当条数达到十万级别的时候就会很慢,那有没有效率更好的算法呢?这时就引出我们常用的二分查找算法

4、二分查找

由于ipcode.txt中的ip地址段已经排序过的,所以非常符合二分查找的必要条件,之前的二分查找是只有一个值组成的数组,而现在这个是由两个数组成的,如何来实现呢?

/**
	 * 根据ip地址判断属于哪个ip地址段,返回这个段的ip地址对象
	 * 使用二分查找算法来实现
	 * @param ip
	 * @param ipBeans
	 * @return
	 */
	public static IPBean getIPByHalf(String ip) {
		IPBean[] ipBeans = getIpBeans();
		if (ipBeans == null || ipBeans.length == 0)
			return null;
		long iplong = IPUtil.ipToLong(ip);
		if (iplong < ipBeans[0].getBegin() || iplong > ipBeans[ipBeans.length - 1].getEnd())
			return null;
		int left = 0;
		int right = ipBeans.length - 1;
		int mid = (left + right) / 2;
		while (left <= right) {
			if (iplong < ipBeans[mid].getBegin())
				right = mid - 1;
			if (iplong > ipBeans[mid].getBegin())
				left = mid + 1;
			if (iplong >= ipBeans[mid].getBegin() && iplong <= ipBeans[mid].getEnd())
				return ipBeans[mid];
			mid = (left + right) / 2;
		}
		return null;
	}

其中getIpBeans()与上面方法一样。

5、完整的代码如下:

package com;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class TestHalf {
	/**
	 * 根据ip地址判断属于哪个ip地址段,返回这个段的ip地址对象
	 * 使用顺序查找来实现
	 * @param ip
	 * @param ipBeans
	 * @return
	 */
	public static IPBean getIP(String ip) {
		IPBean[] ipBeans = getIpBeans();
		if (ipBeans == null || ipBeans.length == 0)
			return null;
		long iplong = IPUtil.ipToLong(ip);
		if (iplong < ipBeans[0].getBegin() || iplong > ipBeans[ipBeans.length - 1].getEnd())
			return null;
		for(IPBean ipBean:ipBeans){
			if(ipBean.getBegin()<=iplong && ipBean.getEnd()>=iplong)
				return ipBean;
		}
		return null;
	}
	/**
	 * 根据ip地址判断属于哪个ip地址段,返回这个段的ip地址对象
	 * 使用二分查找算法来实现
	 * @param ip
	 * @param ipBeans
	 * @return
	 */
	public static IPBean getIPByHalf(String ip) {
		IPBean[] ipBeans = getIpBeans();
		if (ipBeans == null || ipBeans.length == 0)
			return null;
		long iplong = IPUtil.ipToLong(ip);
		if (iplong < ipBeans[0].getBegin() || iplong > ipBeans[ipBeans.length - 1].getEnd())
			return null;
		int left = 0;
		int right = ipBeans.length - 1;
		int mid = (left + right) / 2;
		while (left <= right) {
			if (iplong < ipBeans[mid].getBegin())
				right = mid - 1;
			if (iplong > ipBeans[mid].getBegin())
				left = mid + 1;
			if (iplong >= ipBeans[mid].getBegin() && iplong <= ipBeans[mid].getEnd())
				return ipBeans[mid];
			mid = (left + right) / 2;
		}
		return null;
	}

	/**
	 * 读取ipcode.txt文件,按行读取,并转成IPBean对象数组
	 * @return
	 */
	public static IPBean[] getIpBeans() {
		InputStreamReader inputStreamReader = null;
		BufferedReader reader = null;
		try {
			File file = new File(TestHalf.class.getResource("ipcode.txt").getPath());
			inputStreamReader = new InputStreamReader(new FileInputStream(file), "UTF-8");
			reader = new BufferedReader(inputStreamReader);
			String line;
			LinkedList<IPBean> ipBeanList = new LinkedList<IPBean>();
			while ((line = reader.readLine()) != null) {
				String[] tmp = line.split(",");
				ipBeanList.add(new IPBean(IPUtil.ipToLong(tmp[0]), IPUtil.ipToLong(tmp[1]), tmp[2]));
			}
			IPBean[] ipBeans = ipBeanList.toArray(new IPBean[] {});
			return ipBeans;
		} catch (Exception ex) {
			ex.printStackTrace();
		} finally {
			try {
				reader.close();
				inputStreamReader.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return null;
	}

	public static void main(String[] args) {
		IPBean ipBean = getIPByHalf("20.1.1.255");
		IPBean ipBean1 = getIP("20.1.1.255");
		System.out.println(ipBean);
		System.out.println(ipBean1);
	}
}

class IPBean {
	private long begin;
	private long end;
	private String code;

	public long getBegin() {
		return begin;
	}

	public void setBegin(long begin) {
		this.begin = begin;
	}

	public long getEnd() {
		return end;
	}

	public void setEnd(long end) {
		this.end = end;
	}

	public String getCode() {
		return code;
	}

	public void setCode(String code) {
		this.code = code;
	}

	public IPBean(long begin, long end, String code) {
		this.begin = begin;
		this.end = end;
		this.code = code;
	}

	@Override
	public String toString() {
		return "IPBean [begin=" + begin + ", end=" + end + ", code=" + code + "]";
	}

	public IPBean() {
	}
}

6、总结

二分查找是数据结构中使用频率很高的一个算法,在大文件或大数据中应用非常广泛,并且各种企业的面试题中都会出现,所以是我们程序员必须要掌握的。但是二分查找有一个很大的限制条件就是必须是排序好的,如果是一个非排序的数组是无法用的,所以就需要我们先做一个排序,这样就有牵扯出排序算法来,所以数据结构是一门非常有用的知识,是一个程序员进阶必备的。