Question

实现一个内存上的链式哈希表，用来存储 <key, value> 键值对数据。

1. 实现一个内存上的链式哈希表，用来存储 <key, value> 键值对数据。
【说明】 表的元素个数为N，每个元素分为表头结点和结点。其中表头结点记录了结点的一些相关信息，如结点总数，空闲结点数等；
结点存储key值和value值，结点的大小（node_size）固定，可为64字节，或者128字节等；每一个元素的结点个数固定，为3，5等；
Key值建议为整型（int），Value值建议为字符串类型
链式哈希表需要实现以下操作:
(1) int Init(N) 初始化一个长度为N的哈希表， 返回值： -1 表示初始化失败 0 表示初始化成功；
(2) int Put(key,value) 往哈希表添加<key, value> 键值对数据， 返回值： -1 表示添加失败 0 表示添加成功；
(3) string Get(Key) 获取指定key值的value数据，返回值：value
测试你的Put函数和Get函数。（附录已有一个例子，请参考）
2. 在这个链式哈希表的基础上，实现页面置换算法的模拟。
【说明】
（1）我们在使用Put函数的时候，需要用到哈希函数。哈希函数可能导致冲突的情况，即不同的Key值可能对应到相同的位置。因此，我们每一次存储数据时，如果某个位置发生冲突，我们则将当前数据链接到冲突位置的所在元素的下一个结点。
然而，因为我们的链式哈希表每一个元素的结点个数是有限的，假如只有3个结点。当我们往哈希表某个位置添加的<key, value> 元素超过3个时，那么将产生空闲结点不够的情况，因此需要将非空闲结点置换到磁盘中，从而让内存拥有空闲结点，以便存储当前的数据。
在这种情况下，将什么样的非空闲结点置换到磁盘中，需要一个选择策略。相关的策略算法有FIFO，LRU，LFU，OPT等。请大家实现至少两种置换算法，以便进行对比。
同理，在执行Get函数时，如果发现需要获取的结点不在内存中，而是在磁盘中，则需要将结点从磁盘中取出来，然后返回相应的Value值。
（2）非空闲结点如何置换到磁盘？ 我们可以创建一个文件，用来存储内存中需要置换出来的非空闲结点。文件由固定的块（块的大小等于结点的大小）组成。
一种简单的方案是：创建一个文件，文件由N*disk_node_num（我们可以设disk_node_num为5）个块组成。即文件的大小为N* disk_node_num * node_size，初始化时，文件的数据内容为0。
则Index为k的非空闲结点需要置换到磁盘中，则存到文件中k * disk_node_num * node_size开始对应的空闲位置。
如果磁盘中的所有位置都存储满了（毕竟磁盘中的结点个数只有5个），那么Put函数返回-1，表示添加key、value值失败。

3. 实验模拟：测试你编写的Put函数和Get函数，以及缓存系统的效率等。
4. 置换算法的命中率对比，跟据你所写的缓存系统的不同置换算法，测试不同算法的命中率。
5. 开放题：（1）请考虑一下这样的系统有什么应用（即它能够解决什么问题？）
（2）本系统存在什么样的问题？说出你的改进方案？

Answer 1

这个蛮复杂的