loc*_*boy 14 hashtable pseudocode
有谁知道如何做到这一点以及伪代码会是什么样子？
众所周知,哈希表存储键,值对,并且当一个键被调用时,该函数将返回与该键相关联的值.我想要做的是理解创建映射函数的底层结构.例如,如果我们生活在除了数组之外没有先前定义的函数的世界中,我们怎么能复制我们今天拥有的Hashmaps？
Jos*_*aum 22
实际上,今天的一些Hashmap实现确实是由你提出的数组构成的.让我描绘一下这是如何工作的:
散列函数 散列函数将您的键转换为第一个数组(数组K)的索引.可以使用诸如MD5之类的散列函数或者更简单的散列函数(通常包括模运算符).
存储桶 一个简单的基于数组的Hashmap实现可以使用存储桶来处理冲突.数组K中的每个元素('桶')本身包含一对数组(数组P).添加或查询元素时,哈希函数将指向K中的正确存储桶,其中包含所需的数组P.然后,迭代P中的元素,直到找到匹配的键,或者在此处分配新元素. P.结束
使用哈希将密钥映射到桶 你应该确保桶的数量(即K的大小)是2的幂,比方说2 ^ b.要为某个键找到正确的存储区索引,请计算哈希(键),但只保留前b位.这是转换为整数时的索引.
重新调整 计算密钥的散列并找到正确的存储桶非常快.但是一旦一个桶变得更饱满,你就必须迭代越来越多的物品才能找到合适的物品.因此,有足够的桶来正确分配对象很重要,否则你的Hashmap会变慢.
因为您通常不知道要预先在Hashmap中存储多少对象,所以需要动态增大或缩小地图.您可以保留存储的对象数量的计数,一旦超过某个阈值,您就可以重新创建整个结构,但这次使用更大或更小的数组K.这样K中的一些桶就是非常满的现在将它们的元素分成几个桶,这样性能会更好.
替代方案 您也可以使用二维数组而不是数组数组,或者您可以将数组P替换为链接列表.此外,您可以简单地选择在其中一个存储桶包含多个配置数量的项目时重新创建(即重新调整)哈希映射,而不是保留存储对象的总数.
您要求的变体在哈希表维基百科条目中被描述为"数组哈希表" .
代码 对于代码示例,请看这里.
希望这可以帮助.