相关疑难解决方法(0)

哈希表可以实现O(1)似乎是常识,但这对我来说从来没有意义.有人可以解释一下吗？以下是两种情况:

答: 该值是一个小于哈希表大小的int.因此,该值是它自己的哈希值,因此没有哈希表.但如果有,那将是O(1)并且仍然是低效的.

B. 您必须计算值的哈希值.在这种情况下,查找数据大小的顺序为O(n).在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n).

除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目.因此,无论如何,它在某个时刻转变为一个小的线性搜索.

我认为哈希表很棒,但我没有得到O(1)的名称,除非它只是理论上的.

维基百科关于哈希表的文章始终引用常量查找时间并完全忽略哈希函数的成本.这真是一个公平的衡量标准吗？

编辑:总结我学到的东西:

• 这在技术上是正确的,因为哈希函数不需要使用密钥中的所有信息,因此可以是恒定时间,并且因为足够大的表可以将冲突降低到接近恒定的时间.

• 在实践中确实如此,因为随着时间的推移,只要选择散列函数和表大小来最小化冲突,即使这通常意味着不使用常量时间散列函数,它也只会有效.

我真的不明白模数除法是如何工作的.我正在计算27 % 16和结束11,我不明白为什么.

我似乎无法在网上找到外行人的解释.有人可以详细说明这里发生了什么吗？

我正在查看HashMapJava 7 中的源代码,我看到该put方法将检查是否已存在任何条目,如果它存在,那么它将用新值替换旧值.

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

所以,基本上它意味着给定密钥总是只有一个条目,我也通过调试看到了这一点,但如果我错了,那么请纠正我.

现在,由于给定键只有一个条目,为什么该get方法有FOR循环,因为它可以简单地直接返回值？

    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    } …

"存储区条目"在哈希表的上下文中意味着什么？

是什么区别HashTable和HashMap 纯粹(而不是Java或任何其他语言)数据结构的背景下.

我见过人们使用这些术语可以互换使用相同的概念.它纯粹在数据结构的上下文中完全没有区别!

有谁知道如何做到这一点以及伪代码会是什么样子？

众所周知,哈希表存储键,值对,并且当一个键被调用时,该函数将返回与该键相关联的值.我想要做的是理解创建映射函数的底层结构.例如,如果我们生活在除了数组之外没有先前定义的函数的世界中,我们怎么能复制我们今天拥有的Hashmaps？

散列过程如何在Dictionary中工作？我读到使用字典提供更快的查找.但是不明白怎么了？散列和映射到索引的方式如何？找不到任何好的参考.

编辑:如何从散列函数的结果中获取存储对象的实际内存位置？

我一直在阅读一些有关哈希表、字典等的内容。我看过的所有文献和视频都暗示哈希表具有空间/时间权衡属性。

我很难理解为什么哈希表比具有相同总元素（值）数量的数组或列表占用更多的空间？它与实际存储散列密钥有关吗？

据我了解，用基本术语来说，哈希表采用一个键标识符（例如某个字符串），将其传递给某个哈希函数，该函数会生成数组或其他数据结构的索引。除了在数组或表中存储对象（值）时明显使用内存之外，为什么哈希表会占用更多空间？我觉得我错过了一些明显的东西......

如果我有一个Dictionary<char,...>是否可以使方法ContainsKey不区分大小写？

我知道,在Dictionary<string,...>使用StringComparer.InvariantCultureIgnoreCase时,但是当字典中的键是char-type时该怎么办？

std::unordered_map 保证O(1)时间搜索,但它如何管理碰撞？

Cppreference声称

无序映射是一个关联容器,包含具有唯一键的键值对.元素的搜索,插入和删除具有平均的恒定时间复杂度.

假设所有哈希码都相同的情况,内部如何处理冲突？

如果哈希码对每个键都是唯一的,那么我的假设将完全错误.在这种情况下,如何在没有冲突的情况下创建唯一的哈希码？

std::unordered_map哈希函数采用什么方法来保证O(1)搜索？