0

IPアドレス範囲に問題があります

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

10.1.101.270などの場所を見つけたいIPが与えられた場合、Yを与える必要があります。それらを保存および検索するために最適なアルゴリズムを使用しようとしているコードは必要ありませんか? これにアプローチする方法

B+Tree?
4

3 に答える 3

4

use, TreeMap<K, V>: 位置をマッピングする開始範囲を保存できます。 TreeMapエントリの順序付けに Red-Black ツリー データ構造を使用します。挿入や削除を含む主要な検索操作はO(log n). このマップは、次の 2 つの便利な機能を提供します。

higherEntry(K key):指定されたキーよりも厳密に最も大きいキーにkey-value関連付けられたマッピングを返します。または、そのようなキーがない場合は、マッピングを返します。keynull

lowerEntry(K key): 指定されたキーより厳密に小さい最大のキーに関連付けられたキーと値のマッピングを返します。またはnull、そのようなキーがない場合に返します。

特定の ip を として検索しているときに、 キーとして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 に答える