标签: data-structures

我正在寻找哈希表如何工作的解释 - 用像我这样的傻瓜的简单英语!

例如,我知道它需要密钥,计算哈希值(我正在寻找解释如何)然后执行某种模数来计算它存储在存储值的数组中的位置,但这就是我的知识停止的地方.

任何人都可以澄清这个过程吗？

编辑:我没有具体询问如何计算哈希码,而是概述哈希表的工作原理.

假设您在Java中有一个链表结构.它由节点组成:

class Node {
    Node next;
    // some user data
}

每个节点都指向下一个节点,最后一个节点除外.假设列表有可能包含一个循环 - 即最终的节点,而不是具有空值,具有对列表中的一个节点的引用.

什么是最好的写作方式

boolean hasLoop(Node first)

true如果给定的Node是带循环的列表的第一个,它将返回,false否则？你怎么写,这需要一个恒定的空间和合理的时间？

这是一个循环列表的图片:

假设我们有两个堆栈而没有其他临时变量.

是否可以仅使用两个堆栈"构造"队列数据结构？

什么时候使用List vs LinkedList更好？

有没有什么方法可以将项目索引作为每个拆分的分隔符List<SomeObject>分成几个单独的列表SomeObject？

让我举例说明:

我有一个List<SomeObject>,我需要一个List<List<SomeObject>>或List<SomeObject>[],所以这些结果列表中的每一个将包含一组3个原始列表项(顺序).

例如.:

• 原始清单: [a, g, e, w, p, s, q, f, x, y, i, m, c]

• 结果列表: [a, g, e], [w, p, s], [q, f, x], [y, i, m], [c]

我还需要将结果列表大小作为此函数的参数.

我在有序数组上使用LINQ to Objects指令.我不应该做哪些操作来确保数组的顺序没有改变？

正如在这个答案的更新3中所表明的那样,这种表示法:

var hash = {};
hash[X]

实际上并不散列对象X; 它实际上只是转换X为一个字符串(通过.toString()它是一个对象,或者是各种基本类型的一些其他内置转换),然后在" hash"中查找该字符串,而不对其进行散列.也不检查对象相等性 - 如果两个不同的对象具有相同的字符串转换,它们将仅相互覆盖.

鉴于此 - 在JavaScript中是否有任何有效的哈希映射实现？(例如,第二个Google结果javascript hashmap产生一个实现,对于任何操作都是O(n).各种其他结果忽略了具有等效字符串表示的不同对象相互覆盖的事实.

很久以前,我以1.25美元的价格从交易台上买了一本数据结构书.在其中,哈希函数的解释说,由于"数学的本质",它最终应该由质数修改.

你对1.25美元的书有什么期望？

无论如何,我有多年的时间来思考数学的本质,但仍然无法弄明白.

当存在大量的桶时,数字的分布是否真的更均匀？或者这是一个老程序员的故事,每个人都接受,因为其他人都接受它？

任何人都可以用一个例子解释二叉树和二叉搜索树 之间的区别吗？

简要背景:广泛使用的许多(大多数？)当代编程语言至少有一些共同的ADT [抽象数据类型],特别是

• string(由字符组成的序列)

• list(有序的值集合),和

• 基于地图的类型(将键映射到值的无序数组)

在R编程语言中,前两个分别实现为character和vector.

当我开始学习R时,几乎从一开始就有两件事是显而易见的:list是R中最重要的数据类型(因为它是R的父类data.frame),其次,我无法理解它们是如何工作的,至少不能很好地在我的代码中正确使用它们.

首先,在我看来,R的list数据类型是地图ADT的简单实现(dictionary在Python中,NSMutableDictionary在Objective C中,hash在Perl和Ruby中,object literal在Javascript中,等等).

例如,您可以像创建Python字典一样创建它们,方法是将键值对传递给构造函数(在Python中dict不是这样list):

x = list("ev1"=10, "ev2"=15, "rv"="Group 1")

并且您可以像访问Python字典那样访问R List的项目,例如x['ev1'].同样,您可以通过以下方式仅检索"键"或仅检索"值":

names(x)    # fetch just the 'keys' of an R list
# [1] "ev1" "ev2" "rv"

unlist(x)   # fetch just the 'values' of an R list
#   ev1       ev2        rv 
# …