映射ip地址範圍內的國家代碼（數據結構包含HashMap或樹木？）

試圖解決一個難題，我發現在這裏： http://zcasper.blogspot.com/2005/10/google-phone-interview.html 映射ip地址範圍內的國家代碼（數據結構包含HashMap或樹木？）

的目標是重新呈現一個IP地址範圍以國家代碼的樣子在內存中的表和使用這個數據結構來處理一串行ipaddress來識別國家代碼..

所以我開始從臀部的思考使用HashTable 哈希表的作品很棒;如果我們有一個國家代碼範圍查找，因爲我們有更少的國家名稱映射到IP地址範圍？

，但不知道;我如何用ipaddress去國家代碼。有什麼想法嗎？或者我可以使用樹型數據結構嗎？

2009-08-09 Satish

輸入文件提供一個IP地址範圍（而不是1：1名映射），所以你需要某種有序圖結構。

// 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; 
    } 
}

來源

2009-08-09 07:48:38

試過200K條記錄;它是快速的:-)，順便說一下，在Java集合中有什麼編程API來了解Tree的數據結構屬性，如「深度」或「高度」？ – Satish 2009-08-10 00:03:38

沒有我所知道的。 JDK中的TreeMap是紅黑樹，因此它將大致平衡，JDK中的另一個選項是ConcurrentSkipList，如果提前對導入數據進行排序，它將更好地平衡。除了你需要在一些更專業化的結構之外去看看Java Collections庫之外。 – 2009-08-10 18:28:49

你沒有機會存儲所有ip地址。你可以做的是存儲IP地址範圍所在的區間開始 - 結束。

有一個專門的數據結構，稱爲Interval Tree它可以讓你查詢這個。

來源

2009-08-09 07:58:36

是不是存儲一個範圍正是OP說他會做的？ – Fredrik 2009-08-09 16:06:40

這是如果你正在考慮一個SQL解決方案：

，如果你可以添加一些約束你的數據集，你也許可以僥倖逃脫使用非常簡單的SQL。你甚至可以使用簡單的索引。 - 是這樣的話，當你使用GeoCityLite數據集

如果您的IP塊是不重疊的，您可以只需將其插入到數據庫作爲無符號 32位數字的「塊」表，查詢他們像與Hibernate：

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

我把它寫下來的HQL語法，因爲不是所有的數據庫都使用相同的語法膠印+限制

發出最匹配的查詢，假設所有塊不重疊。 - 你甚至不需要結束ip，這是由後繼者自動確定的。

避免查詢它這樣!:

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

我的數據庫是不是能夠充分利用自己的指標，並做了很多表掃描。

來源

2009-08-09 08:20:41

由於網絡路由的工作方式，你的算法需要處理的最長前綴匹配，你想存儲CIDR blocks，而不是地址。

我開發了一種算法來處理這一點，但不能張貼在這裏。 Open Source中最接近的是Linux中的路由表處理代碼。

您還可以檢查出Patricia Trie or Radix Tree算法。這些可以用來解決這個問題。

來源

2009-08-09 16:05:10

映射ip地址範圍內的國家代碼（數據結構包含HashMap或樹木？）

回答

相關問題