performance - 将IP映射到城市的数据结构

Question

我正在阅读来自不同公司的面试问题，我遇到了这个问题:

You are given a fixed file. The format of each line is city name, ip address
range. Construct a data structure and design algorithm to achieve efficient
mapping from an ip address to city name.

我认为可行的一种方法是使用一个简单的链表，尽管在线性时间内是可行的，其中您拥有给定范围的起始 IP，在节点内您拥有该范围内的城市和最终 IP。

因此，在查找内容时，您会遍历列表并检查开始和结束 IP 地址，以查看给定 IP 是否在任何范围内。

这假设 IP 范围不重叠。

有人对此有更好的解决方案吗？

Answer 1

您可以在 32 位上存储 IP 地址，因此只需将它们转换为整数，然后将 (IP, City) 对存储在任何 balanced BST 中或 hash table关键是IP。这样，查找复杂度将是对数或常量。