软件工程访问内存分配

Question

我正在研究这个问题，我在网上找到了一个SDE实习机会。我想知道是否有人能帮我解决这个问题，因为我很失落。我正试图找出一种聪明的方法，将分配的内存地址和起始地址插入到散列表中。我是否需要使用特定的哈希码？最好是在爪哇。提前感谢！

假设您有2^32字节的内存。当程序请求分配内存时，分配一个4kb的内存块。它可以在任何位置分配(例如0，57,8192)。现在假设我们有一个名为lookup()的函数，当输入任意地址时，(1)返回包含请求地址的块的起始地址的值(如果被分配)，或者(2)返回一个值，如果没有分配块，则返回false。查找必须在恒定时间内工作。为了帮助澄清功能，下面是一些预期的行为示例：

Allocate(1) /* allocates bytes 1-4096 */
Allocate(4099) /* allocates bytes 4099-8194 */
Lookup(123) /* returns 1 */
Lookup(4096) /* returns 1 */
Lookup(4098) /* returns -1 or false */
Lookup(6042) /* returns 4099 */
Lookup(8198) /* returns -1 or false */

Answer 1

正如Mikkel K所指出的，这个问题不是很好。我假设他们希望你们提供一个解决方案，使时间保持相当小。以下是我的建议：

分配：

对地址中最重要的20个位进行散列。

如果一个块跨越2个哈希号(对于所有不对齐4096字节的块都是这样)，那么将分配记录添加两次，分别添加到散列X的列表和散列X+1的列表中。

查找：

对地址中最重要的20个位进行散列。获取与哈希值关联的分配记录列表。列表将包含0、1或2个分配记录。

将返回列表中分配记录的起始字节与参数中的地址进行比较，并确定它属于哪个分配记录(如果有的话)。