java - 仅使用数组实现高效的数据结构

Question

作为我的编程类(class)的一部分，我进行了一个练习来实现我自己的字符串集合。我原本计划使用 ArrayList 集合或类似的集合，但限制之一是我们不允许使用任何 Java API 来实现它，因此只允许使用数组。我可以使用数组来实现这一点，但是效率以及测试该代码的数据量非常重要。建议我使用哈希表或有序树，因为它们比数组更有效。经过一些研究后，我决定使用哈希表，因为它们似乎很容易理解和实现，但一旦我开始编写代码，我意识到它并不像我想象的那么简单。

以下是我遇到的问题，希望得到一些建议，以了解在考虑效率的情况下再次解决这些问题的最佳方法:

1. 实际大小:如果我理解正确的话，哈希表没有排序(索引)，这意味着项目之间会有间隙，因为哈希函数给出了不同的索引。那么我如何知道数组何时已满并且需要调整其大小？
2. 调整大小:我需要使用数组创建动态数据结构的困难之一。因此，如果我有一个数组 String[100]，一旦它变满，我将需要通过某种因素调整它的大小，我决定每次将其增加 100，所以一旦我这样做，我将需要更改所有现有值的位置，因为它们哈希键在计算时会有所不同:

int position = "orange".hashCode() % currentArraySize;

因此，如果我尝试查找某个值，其哈希键将与数组较小时的哈希键不同。

哈希函数:我还想知道是否内置 hashCode() String 类中的方法非常高效并且适合我想要实现的内容，或者创建我自己的方法更好。

处理多次出现:要求之一是能够添加多个相同的单词，因为我需要能够计算该单词在我的集合中存储了多少次。由于它们将具有相同的哈希码，因此我计划在下一个索引处添加下一个出现的位置，希望会有一个间隙。我不知道这是否是最好的解决方案，但我是如何实现它的:

public int count(String word) {
    int count = 0;
    while (collection[(word.hashCode() % size) + count] != null && collection[(word.hashCode() % size) + count].equals(word))
        count++;
    return count;
}

预先感谢您的建议。有什么需要澄清的地方请询问。

附注单词的长度不固定，变化很大。

更新感谢您的建议，我知道我确实犯了一些愚蠢的错误，我会尽力做得更好。因此，我采纳了您的所有建议，并很快提出了以下结构，它并不优雅，但我希望这就是您的大致意思。我确实必须做出一些判断，例如存储桶大小，现在我将元素的大小减半，但是有没有办法计算或一些通用值？另一个不确定性是按什么因子来增加我的数组，我应该乘以某个 n 数还是添加固定数也适用？另外我想知道一般效率，因为我实际上是在创建类的实例，但 String 是一个类，所以我猜测性能差异应该不会太大？

Answer 1

实际大小:当元素总数超过桶数乘以负载因子(默认值为 0.75)时，内置 Java HashMap 才会调整大小。它没有考虑有多少个桶实际上是满的。您也不必这样做。

调整大小:是的，调整表大小时，您必须重新散列所有内容，其中包括重新计算其散列。

So if I try to find a certain value it's hash key will be different from what it was when array was smaller.

是的。

哈希函数:是的，您应该使用内置的 hashCode() 函数。对于基本目的来说已经足够了。

处理多次发生的情况:这很复杂。一种简单的解决方案是让给定字符串的哈希条目也记录该字符串出现的次数。也就是说，不要在哈希表中保留同一字符串的多个副本，而是保留一个 int 以及每个 String 来计算其出现次数。