java - 将 IP 地址范围映射到国家代码(数据结构 HashMap 或树？)

Question

试图解决我在这里发现的一个难题: http://zcasper.blogspot.com/2005/10/google-phone-interview.html

目标是将 IP 地址范围重新呈现到内存中的国家代码查找表，并使用此数据结构处理 zilloin 行的 ip 地址以识别国家代码。

所以我一开始就想到了使用 HashTable 哈希表效果很好；如果我们有一个国家代码来进行范围查找，因为我们有更少的国家名称映射到 IP 地址范围？

但不确定；我如何使用 ipaddress 转到国家代码。有什么想法吗？ 或者我可以使用树数据结构吗？

Answer 1

输入文件提供了一系列 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;
    }
}