我正在研究 SDE 实习期间在网上找到的这个问题。我想知道是否有人可以帮助解决这个问题，因为我很失落。我试图找出一种聪明的方法来将分配的内存地址和起始地址插入到 HashMap 中。我必须使用特定的哈希码吗？最好用java。提前致谢!
假设您有 2^32 字节的内存。当程序请求分配内存时，会分配 4kb 的内存块。它可以分配在任何位置(例如0、57、8192)。现在假设我们有一个名为lookup()的函数，当输入任意地址时，该函数(1)返回包含所请求地址(如果已分配)的 block 的起始地址的值，或者(2)返回一个指示 false 的值如果没有分配 block 。查找必须在恒定的时间内进行。为了帮助阐明功能，以下是一些预期行为示例:
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 */
最佳答案
正如 Mikkel K 所指出的，这个问题的结构不是很好。我假设他们希望您提供一个解决方案，使时间常数保持在相当小的范围内。 这是我的建议:
分配:
对地址的 20 个最高有效位进行哈希处理。
如果一个 block 跨越 2 个哈希值(对于所有未在偶数 4096 字节上对齐的 block 都是如此)，则将分配记录添加两次，分别添加到哈希 X 的列表和哈希 X+ 的列表中1.
查找:
对地址的 20 个最高有效位进行哈希处理。 获取与哈希值关联的分配记录列表。该列表将包含 0、1 或 2 个分配记录。
将返回列表中分配记录的起始字节与参数中的地址进行比较，确定属于哪条分配记录(如果有)。
关于java - 软件工程面试内存分配，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26402036/