哈希表可以实现O(1)似乎是常识,但这对我来说从来没有意义.有人可以解释一下吗？以下是两种情况:
答: 该值是一个小于哈希表大小的int.因此,该值是它自己的哈希值,因此没有哈希表.但如果有,那将是O(1)并且仍然是低效的.
B. 您必须计算值的哈希值.在这种情况下,查找数据大小的顺序为O(n).在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n).
除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目.因此,无论如何,它在某个时刻转变为一个小的线性搜索.
我认为哈希表很棒,但我没有得到O(1)的名称,除非它只是理论上的.
维基百科关于哈希表的文章始终引用常量查找时间并完全忽略哈希函数的成本.这真是一个公平的衡量标准吗？
编辑:总结我学到的东西:
这在技术上是正确的,因为哈希函数不需要使用密钥中的所有信息,因此可以是恒定时间,并且因为足够大的表可以将冲突降低到接近恒定的时间.
在实践中确实如此,因为随着时间的推移,只要选择散列函数和表大小来最小化冲突,即使这通常意味着不使用常量时间散列函数,它也只会有效.
我看到这个问题给出了一个字符串"smith; rodgers; McCalne"你怎么能产生一个集合.答案是使用String.Split.
如果我们没有内置的Split()代替你做什么？
更新:
我承认编写分割函数相当容易.以下是我写的内容.使用IndexOf循环遍历字符串并使用Substring进行提取.
string s = "smith;rodgers;McCalne";
string seperator = ";";
int currentPosition = 0;
int lastPosition = 0;
List<string> values = new List<string>();
do
{
currentPosition = s.IndexOf(seperator, currentPosition + 1);
if (currentPosition == -1)
currentPosition = s.Length;
values.Add(s.Substring(lastPosition, currentPosition - lastPosition));
lastPosition = currentPosition+1;
} while (currentPosition < s.Length);
我看了一下SSCLI的实现和上面的类似,除了它处理更多的用例,并且在进行子字符串提取之前使用不安全的方法来确定分隔符的索引.
其他人提出以下建议.
是这个吗？
以下为回应此,我很好奇,想知道什么是String.Split的运行时间()
string source = "source string;this,"; //length n
string[] splitted = source.Split(' ',',',';'); //delimiter array of length m
是O(m*n)？