我需要自己的Hash map实现而不使用任何库; 我的键是整数,我的散列是%大小。我不知道会添加多少元素,所以我需要能够调整大小(处理碰撞我正在使用二次探测)。但是,如果我调整它的大小,它将使哈希(%size)出错。我一直在看这些,但我仍然不明白这是如何解决这个问题的。
发布于 2019-02-22 11:06:44
我建议使用Paul Larson推广的算法,该算法一次拆分一个桶。它的工作原理如下:
您可以确定平均每个哈希桶的条目数。您可以跟踪您拥有的条目数以及您拥有的存储区数量。
假设你有四个水桶。您将每个元素放在一个桶中,方法是使用散列模式4。
现在说每个哈希桶的条目超出了你想要的平均值。你现在从四个桶增加到五个。你这样做如下:
hash%4
为(hash % 8) % 5
。这会让你的水桶不均匀。铲斗1和铲斗5的铲斗数量将是铲斗2,3和4的一半。但是当你获得第8个铲斗时,它们将会再次出现。
为简单起见,您可以将每个存储桶实现为链接列表。
另一种方法是很少重新进行重新散列,并重新进行每一个条目的重新散列。
https://stackoverflow.com/questions/-100006386
复制相似问题