0

I have a problem i have ip address range

IP                                    Location
10.1.100.200- 10.1.100.800              x
10.1.101.200- 10.1.101.800              Y
10.1.102.200- 10.1.102.800              Z etc etc

Now given an ip I want to find location like eg 10.1.101.270 should give Y I dont want the code I am trying to use best algorithm to store and search them? How to approach this

B+Tree?
4

3 回答 3

4

那么区间树或段树呢？如果您的 IP 地址范围“集”是动态的，则间隔树应该更好；如果范围是静态的，Segment Tree 应该会更好，并且据说对于您正在执行的“刺探查询”会更好。

区间树：

在计算机科学中，区间树是用于保存区间的有序树数据结构。具体来说，它允许人们有效地找到与任何给定区间或点重叠的所有区间。它通常用于窗口查询。

O(log n)的查询时间

段树：

在计算机科学中，段树是一种用于存储区间或段的树数据结构。它允许查询哪些存储的段包含给定点。

在 O(log n + k) 中查询一个点，k 是检索到的间隔或段的数量。

实现：

Java 中的段树实现。

Java 中的区间树实现。

于 2013-11-13T17:30:22.640 回答
4

使用，TreeMap<K, V>：您可以存储开始范围以映射位置。 TreeMap使用红黑树数据结构对条目进行排序。包括插入和删除在内的关键查找操作在哪里O(log n)。该地图提供了两个有用的功能：

higherEntry(K key)：返回与给定键的最小严格大于key-value关联的映射，或者如果没有这样的键。keynull

lowerEntry(K key)：返回与严格小于给定键的最大键关联的键值映射，或者null如果没有这样的键。

在使用特定 ip as 搜索时，您可以尝试找到包含as 键及其对应位置作为值key的左右条目。start ip-range将这些 ip-range 与搜索进行比较key 以确定值V（位置）。

于 2013-11-13T17:20:18.563 回答
1

我会按照 Sage 的建议使用 TreeMap。假设不会有重叠。

public class IPSegment implements Comparable<IPSegement>{

    private long start;
    private long end;
    public IPSegement(String startIp, String endIp){
         //convert the ip address to a 32 bit integer. 

    }
    public int compareTo(IPSegement other){

         return this.start - other.start;  //assume no overlap
    }

    public int equals(IPSegement other){
      // check both start and end
    }

    public boolean contains(long ip){
      //check whether 'ip' is in this range
    }
}


public class IPSegmentMap{
     private TreeMap<IPSegement> map = new TreeMap<IPSegement>();
     public void add(String start, String end, String location){
          //...
     }

     public String find(String ipAddress){
         long ip = convertIPtoInt(ipAddress);
         IPSegement request = new IPSegement(ip,ip);
         IPSegement exist = map.floorKey(request);
         if(exist.contains(ip)){
             return map.get(exist);
         }

     }

}
于 2013-11-13T17:46:26.507 回答