1

作为数据结构和算法实验问题之一的一部分，我尝试创建我的 Customhashtable，将 CustomLinkedList[] 作为底层数据结构以避免串通（单独链接）。但是当负载因子超过 75 时，我被困在如何将以前的内容映射到大小增加的新数组，以便返回的索引与新大小相同，用于散列的代码大小 = 100

public int arrayIndex(String key)
{
   int index = key.charAt(0);

   for(int j = 1;j<key.length;j++)
     {
        int temp = key.charAt(j);
         index = ((index*27)+temp)%100;
     }
}
4

2 回答 2

1

基本上，您构建一个新的哈希表，并将所有数据从旧的迁移到新的。加载因子是一个触发器，告诉您何时构造更新（更大）的表，这意味着新的哈希表将具有更大的起始数组。

您可以（为了好玩）还添加一个“最小负载因子”设置，这将构建一个更小的哈希表。使用具有最小和最大负载因子的解决方案，初始后备数组（这是散列选择形式的唯一部分）在概念上将根据存储项目的数量调整其大小。由于大小与性能有关，这可以让哈希表始终保持可接受的性能范围（通过增加和缩小它的内存占用）。

至于负载率的计算

  (in the store routines)

  if (array[index] == null) {
    loadCount++;
  }
  if (loadCount / arraySize > maxLoad) {
    resizeUp(...);
  }

  (in the remove routines)
  if (array[index] is cleared to null) {
    loadCount--;
  }
  if (loadCount / arraySize < minLoad) {
    resizeDown(...);
  }
于 2013-07-11T18:00:37.397 回答
0

在一个直接的实现中，当您增加哈希表中支持数组的大小时，所有存储元素的索引都会改变，您需要从链表中删除元素，因为元素不太可能继续共享新地图中的相同存储桶。

例如，最初我们有支持数组：

0: [ A ]
1: [ ]
2: [ B, C ]
3: [ D ]

然后我们增加后备数组，我们可能会得到：

0: [ ]
1: [ ]
2: [ C ]
3: [ ]
4: [ D ]
5: [ A ]
6: [ ]
7: [ B ]

后备数组中的每个项目都需要重新计算其哈希和模数，因为它现在属于一个新的存储桶。如果您使用特定的后备数组大小，则可能有一种更优化的方法来执行此重新计算或映射，并且您可以查看现有的哈希表实现以了解它们的作用（即 java.util.HashMap 的源代码很容易获得），但总的来说，您需要将所有元素移动到正确的存储桶中。

于 2013-07-11T18:12:01.577 回答