作为编程课程的一部分,我练习了实现自己的String集合。我当时计划使用ArrayList集合或类似的集合,但其中的限制之一是不允许我们使用任何Java API来实现它,因此只允许使用数组。我本可以使用数组来实现的,但是效率和测试该代码的数据量非常重要。建议我使用哈希表或有序的发束,因为它们比数组更有效。经过一些研究之后,我决定使用哈希表,因为它们似乎易于理解和实现,但是一旦我开始编写代码,我就意识到它并没有我想像的那么直接。
因此,这是我想到的问题,并希望就如何以效率再次解决这些问题的最佳方法提供一些建议:
实际大小:如果我理解正确,则哈希表没有排序(索引),因此这意味着项之间会有空隙,因为哈希函数提供了不同的索引。那么我怎么知道什么时候数组已满,我需要调整它的大小?
调整大小:使用数组创建动态数据结构所需的困难之一。因此,如果我有一个数组String [100],一旦数组变满,我将需要将其调整大小,我决定每次将其增加100,所以一旦这样做,我就需要更改所有现有值的位置,因为它们的位置哈希键将随着密钥的计算而有所不同:
int position = "orange".hashCode() % currentArraySize;
因此,如果我尝试找到某个值,则其哈希键将与数组较小时的哈希键不同。
哈希函数:我还想知道String类中的内置
hashCode()
方法是否高效且适合于我要实现的功能,还是创建自己的方法更好。处理多种事件:要求之一是能够添加相同的多个单词,因为我需要能够计算单词在集合中存储的次数。由于它们将具有相同的哈希码,因此我计划在下一个索引处添加下一个匹配项,希望会有间隙。我不知道这是否是最好的解决方案,但在这里我是如何实现的:
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是要使用的类,因此我猜测性能的差异应该不会太大?
最佳答案
实际大小:内置Java HashMap
仅在元素总数超过存储桶数乘以称为负载因子的数字(默认值为0.75)时才调整大小。它没有考虑到实际上有多少个桶已满。您也不必。
调整大小:是的,调整表大小时,您必须重新哈希所有内容,其中包括重新计算其哈希值。
因此,如果我尝试找到某个值,则其哈希键将与数组较小时的哈希键不同。
对。
哈希函数:是的,您应该使用内置的hashCode()
函数。对于基本目的来说已经足够了。
处理多种情况:这很复杂。一种简单的解决方案是使给定字符串的哈希条目还保持该字符串出现次数的计数。也就是说,不要在哈希表中保留同一字符串的多个副本,而要保留一个int
以及每个String
计数其出现的次数。