Mapping ipaddress Bereich zu Ländercodes (Datenstruktur Hashmaps oder Bäume?)

Question

versucht, ein Rätsel zu lösen, die ich hier gefunden habe: http://zcasper.blogspot.com/2005/10/google-phone-interview.html

das Ziel ist wieder vorhanden, um einen IP-Adressbereich zu Ländercode Look -up Tabelle im Speicher und verwenden Sie diese Datenstruktur, um eine Zilloin-Reihen von ipaddress zu verarbeiten, um den Ländercode zu identifizieren.

so fing ich mit einem Trieb vom Hüftegedanken an, HashTable zu verwenden ein hash-table funktioniert groß; Wenn wir einen Ländercode haben, um Nachschlageliste zu geben, da wir weniger Ländernamen haben, die den IP-Adressbereichen entsprechen?

aber nicht sicher; Wie gehe ich mit IP-Adresse zu Ländercode. irgendwelche Gedanken? oder kann ich eine Baumdatenstruktur verwenden?

Answer 1

Die Eingabedatei bietet eine Reihe von IP-Adressen (nicht 1: 1-Zuordnung), so dass Sie eine geordnete Kartenstruktur benötigen.

// Assuming IPv4, and the inputs are valid (start before end) 
// and no overlapping ranges. 
public class CountyCodeToIPMap { 
    private final TreeMap<Long, CountryCodeEntry> ipMap = 
      new TreeMap<Long, CountryCodeEntry>(); 

    public void addIpRange(long startIp, long endIp, String countryCode) { 
     ipMap.put(startIp, new CountryCodeEntry(endIp, countryCode); 
    } 

    public String getCountryCode(long ip) { 
     Map.Entry<Long, CountryCodeEntry> entry = ipMap.floorEntry(ip); 
     if (entry != null && ip <= entry.getValue().endIpAddress) { 
      return entry.getValue().countryCode; 
     } else { 
      return null; 
     } 
    } 
} 

public class CountryCodeEntry { 
    public final long endIpAddress; 
    public final String countryCode; 
    public CountryCodeEntry (long endIpAddress, String countryCode) { 
     this.endIpAddress = endIpAdddress; 
     this.countryCode = countryCode; 
    } 
} 

Answer 2

Sie haben keine Chance, alle IP-Adressen zu speichern. was Sie tun können, speichert die Intervalle Start-Ende, wo IP-Adresse Bereiche sind.

gibt es eine spezielle Datenstruktur, genannt Interval Tree, die es ermöglicht, dies abzufragen.

Answer 3

ist, wenn Sie eine SQL-Lösung erwägen:

wenn Sie einige Einschränkungen zu Ihrem Datensatz hinzufügen können, können Sie weg eine sehr einfache SQL. wo Sie sogar einfache Indizes verwenden können. - das ist der Fall, wenn Sie die GeoCityLite Dataset

, wenn Ihre IP-Blöcke sind nicht-überlappende, können Sie einfach fügen Sie sie in einer Datenbank als unsigned 32bit Zahlen in einer „Blöcke“ Tabelle und Abfrage, dass sie wie mit Hibernate:

 (GeoipBlocks) getSession() 
      .createQuery("select gb" + 
        " from GeoipBlocks gb" + 
        " where gb.startIpNum <= :ipnumeric " + 
        " order by gb.startIpNum desc"). 
        setMaxResults(1) 
      .setParameter("ipnumeric", ipInLongValue) 
      .uniqueResult() 

ich schrieb es in hql Syntax nach unten, weil nicht alle Datenbanken für die gleiche Syntax verwenden Offset begrenzen +

, die eine Abfrage für die beste Übereinstimmung gibt, vorausgesetzt, alle Blöcke nicht überlappend . - dafür brauchst du nicht einmal das end ip, dies wird automatisch vom Nachfolger bestimmt.

vermeidet es auf diese Weise abfragen !:

select * from blocks where ipstart <= ip and ipend >= ip 

meine Datenbank vollständig nicht in der Lage war, ihre Indizes zu nutzen, und viele Tabellen-Scan tat.

Answer 4

Aufgrund der Art, wie das Internet-Routing funktioniert, muss Ihr Algorithmus Longest Prefix Matching verarbeiten und Sie möchten CIDR blocks anstelle von Adressen speichern.

Ich habe einen Algorithmus entwickelt, um dies zu handhaben, kann ihn aber hier nicht posten. Am nächsten kommt in Open Source der Routingtabellen-Code in Linux.

Sie können auch Patricia Trie or Radix Tree Algorithmen überprüfen. Diese können verwendet werden, um dieses Problem zu lösen.