相关疑难解决方法(0)

为什么我一直在哈希表上看到这些函数的不同运行时复杂性？

在wiki上,搜索和删除是O(n)(我认为哈希表的要点是持续查找,所以如果搜索是O(n)则重点是什么).

在不久前的一些课程笔记中,我看到了很多复杂性,具体取决于某些细节,包括所有O(1).如果我可以获得所有O(1),为什么要使用任何其他实现？

如果我在C++或Java等语言中使用标准哈希表,那么我可以期待时间复杂度是多少？

我已经对哈希表进行了一些研究,并且我一直遵循经验法则,当有一定数量的条目(最大或通过75%的加载因子)时,应该扩展哈希表.

几乎总是,建议是将哈希表的大小加倍(或加倍加1,即2n + 1).但是,我没有找到一个很好的理由.

为什么要加倍大小,而不是将其增加25%,或者将其增加到下一个素数或下一个素数(例如三个)？

我已经知道,选择一个初始哈希表大小是一个素数通常是一个好主意,至少如果你的哈希函数使用模数,如通用哈希.我知道这就是为什么通常建议做2n + 1而不是2n(例如,http://www.concentric.net/~Ttwang/tech/hashsize.htm)

然而正如我所说,我没有看到任何真正的解释,为什么加倍或加倍加一个实际上是一个很好的选择,而不是选择新哈希表的大小的其他方法.

(是的,我已经阅读了关于哈希表的维基百科文章:) http://en.wikipedia.org/wiki/Hash_table

我试图基于另一个过滤对象数组.共同属性id id.我不确定过滤器+每个是最好的方法或映射减少.无论如何,下面的代码不能像out空列表一样工作.

var aaa = [
    {name: "AAA", id: 845},
    {name: "BBB", id: 839},
    {name: "CCC", id: 854}
];
var bbb = [
    {id: 839},
    {id: 854}
];

var out = _.filter(aaa, function(val){
    return _.each(this, function(val2){
        return val['id'] === val2['id']
    });
}, bbb);

我正在尝试与朋友做作业,一个问题询问线性探测方法的搜索,添加和删除的平均运行时间.我认为它是O(n)因为它必须检查特定数量的节点,直到它找到一个要添加的开放节点.当搜索它从原始索引开始并向上移动直到找到所需的数字.但我的朋友说这是O(1).哪一个是对的？

给定一个整数数组,编写一个返回所有唯一对的方法,最多可加100.

示例数据:

sample_data = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51]
sample_output = [[1,99], [0,100], [10,90], [51,49], [50,50]]

我本周末解决了这个问题,虽然我的解决方案似乎可扩展且高效,但我想确定解决方案的最坏情况时间复杂度是多少？

这是我的解决方案:

def solution(arr)
  res = []
  h = Hash.new

  # this seems to be O(N)
  arr.each do |elem|
    h[elem] = true
  end

  # how do I determine what Time complexity of this could be?
  arr.each do |elem|
    if h[100-elem]
      h[100-elem] = false
      h[elem] = false
      res << [elem, 100-elem] …

HashMap（或）HashTable 是键控数组的一个示例。这里，索引是用户定义的键而不是通常的索引号。例如，arr["first"]=99是一个哈希映射的示例，其中 b 键为第一个，值为 99。

由于使用了键，因此需要哈希函数将键转换为索引元素，然后在数组中插入/搜索数据。此过程假设不存在冲突。

现在，给定一个要在数组中搜索的键，如果存在，则必须获取数据。因此，每次搜索之前，都必须将键转换为数组的索引号。那么如何花费 O(1) 时间呢？因为，时间复杂度也取决于哈希函数。所以时间复杂度一定是O(哈希函数的时间)。

到目前为止,你们中的许多人一定听说过HashDoS.发现这一点的研究人员在他们的视频中声称Hastable的最坏情况复杂性O(n^2).怎么会这样？

功能的时间复杂度是gethash多少？例如,在用于map搜索的c ++中O(log(n)),虽然unordered_map它是O(1).这两件事都是用描述写的,但我gethash在Lisp中找不到任何这样的参考.

实际上,这扩展到所有标准库函数.哪里可以找到它们的复杂性,或者我可以吗？谈论sbcl,如果重要的话.

我想知道python词典如何在后台运行，尤其是动态方面？创建字典时，其初始大小是多少？如果我们用很多元素更新它，我想我们需要扩大哈希表。我想我们需要重新计算散列函数以适应新的更大的散列表的大小，同时又与先前的散列表保持某种逻辑？

如您所见，我不完全了解此结构的内部。