IP地址映射归属城市的高效算法咨询：现有方案是否可行

现有思路正确性评估 #

你的整体逻辑是可行的，但存在一个容易引发误判的细节漏洞，修正后即可正常使用：

• 漏洞点：如果直接将区间的起止端点都作为键存入TreeMap，调用floorKey匹配时会出现跨区间误判。比如纽约IP区间为[100,200]，洛杉矶IP区间为[300,400]，存入的键值对为100:纽约、200:纽约、300:洛杉矶、400:洛杉矶，当查询IP对应数值为250时，floorKey会返回200，误判为纽约，实际250不属于任何城市。
• 修正方案：仅将每个IP区间的起始值作为键存入TreeMap，值存储为「城市名 + 区间结束值」的结构体。调用floorKey拿到匹配的起始键后，额外判断查询IP是否小于等于对应区间的结束值，符合则返回对应城市，否则返回无匹配。

修正后的方案时间复杂度为预处理O(n log n)、单次查询O(log n)，n为IP区间总数，对于绝大多数中小规模业务场景已经足够高效。

更优解决方案 #

如果面对百万级以上IP区间、或者十万QPS以上的查询场景，可以选择以下两种优化方案：

1. 有序区间二分法 #

实现简单、无额外依赖，性能比TreeMap方案高30%以上：

• 预处理阶段将所有IP区间转为整型[start, end, city]结构，按start升序排序，合并重叠或相邻的同城市区间
• 查询时直接对区间数组的start字段做二分查找，找到最大的小于等于查询IP的start，再判断查询IP是否小于等于对应end即可

2. 基数树（Radix Tree）方案 #

更适合IPv6场景，性能稳定无波动：
不需要将IP转为整型，直接按IP的二进制位逐位匹配，单次查询固定仅需32次（IPv4）或128次（IPv6）位比较，内存占用也比存储全量整型区间低50%左右。

小优化技巧 #

IP转整型的逻辑可以用位运算替代乘法，计算效率更高：
ipInt = (a << 24) | (b << 16) | (c << 8) | d
其中a、b、c、d为IP地址的四段十进制数值。

内容的提问来源于stack exchange，提问作者Chamming