实现反向DNS查找缓存

【出自BD面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

反向DNS查找指的是使用Internet IP地址查找域名。例如，如果在浏览器中输入74.125.200.106，它会自动重定向到google.in。

如何实现反向DNS查找缓存？

分析与解答：

要想实现反向DNS查找缓存，主要需要完成如下功能：

（1）将IP地址添加到缓存中的URL映射。

（2）根据给定IP地址查找对应的URL。(www.xing528.com)

对于本题，常见的一种解决方案是使用哈希法（使用hashmap来存储IP地址与URL之间的映射关系），由于这种方法相对比较简单，这里不再赘述。下面重点介绍另外一种方法：Trie树。这种方法的主要优点如下：

（1）使用Trie树，在最坏的情况下的时间复杂度为O（1），而哈希方法在平均情况下的时间复杂度为O（1）。

（2）Trie树可以实现前缀搜索（对于有相同前缀的IP地址，可以寻找所有的URL）。

当然，由于树这种数据结构本身的特性，所以使用树结构的一个最大的缺点就是需要耗费更多的内存，但是对于本题而言，这却不是一个问题，因为InternetIP地址只包含有11个字母（0到9和.）。所以，本题实现的主要思路是：在Trie树中存储IP地址，而在最后一个结点中存储对应的域名。实现代码如下：

程序的运行结果如下：

找到了IP对应的URL：

121.57.61.129--＞www.samsung.net

显然，由于上述算法中涉及的IP地址只包含特定的11个字符（数字和.），所以，该算法也有一些异常情况未处理，例如不能处理用户输入的不合理的IP地址，有兴趣的读者可以继续朝着这个思路完善后面的算法。