Question

一道东京大学计算机专业研究生入学考试的题目--数据结构

你想要保存从WWW上收集的10亿个的网页。于是你想要制作各种索引系统用来通过URL找到网页的以及各种资源。但是，URL的长度从数10Byte直到超过几KB的都有，直接用URL作索引的key不太方便。于是，首先对所有的URL赋予1，2，3..N的连续的整数作为它的ID。之后建立ID和URL的相互变换的索引系统。

问题1.回答通过O（1）的时间复杂度能实现ID转换URL的索引的数据结构。但是，要求尽量少占用记忆空间，原始数据不需要压缩。

问题2.估算你设计的索引的总占用空间。

问题3.回答通过O（1）的时间复杂度能实现URL转换ID的索引的数据结构。但是，要求尽量少占用记忆空间，原始数据不需要压缩。

问题4.估算你设计的索引的总占用空间。

以上为问题原文的翻译，请不要问我详细的内容，因为题目就是这么含糊。请大家以自己的理解回答并告诉我。

这里提供一个我的拙见：
对于问题1，建立一个指针数组char *a[N]，每个指针指向对应的URL的内存地址。而数组的序号直接等于ID。

对于问题3，使用hash函数(比如MD5或者任意算法）来算出URL对应的值，然后再把hash值除以N求余，使用线性连锁hash来保存。

我的解法的问题在于，问题1和问题3中得到的ID值未必相同。这道题目本身并没有要求ID和URL要有怎样的对应关系。所以对于我的解法，自己感觉到有点疑问，希望听听大家的意见。

Answer 1

我的理解，问题1和问题3是两个独立的问题，即满足问题1要求时不需要满足问题3，同理，满足问题3时不需要满足问题1。比如问题1，你的方案就已经满足题目要求了，虽然反向转换时需要O（n）时间。