为什么在 Smalltalk 中将集合添加到自身会爆炸？

Question

我想知道为什么这在 GNU Smalltalk 中没有终止：

s := Set new. s add: s

理论上，s应该只是一个包含空集的集合。但是执行它只会永远循环，炸毁堆。

有趣的是， ((s := Set with: 4 with: 5 with: 6) add: s) size. 终止并评估为 4。

Answer 1

简介

A Set 是一种HashedCollection 专为快速成员检查而设计的。 Set 内部有一个 HashTable，一个 sparce 数组，其中有许多空槽以最小化碰撞的数量。当我们#add:一个元素到Set，一个index到HashTable计算为(hash \ size) + 1，其中#\是mod运算而size是table的长度。如果 index 处的槽已经被占用，则 index 递增直到找到空闲槽，然后将元素存储在那里 (N.B., + 1 因为 Smalltalk 数组是基于 1 的。） [cf. ]

我们的案例

现在，让我们看看问题的代码会发生什么：

1. s := Set new.
2. s add: s.

如上所述，在第 2 步中，add: s 将计算：

s hash \ p + 1

其中p是s的内部table的初始槽数（质数，设置为5或7时该集合首先创建，然后根据需要增加。）

到目前为止，还不错。但可能会有一些

问题

在哪里？根据 Smalltalk 方言，#printOn: 或元素的下一个 add: 版本可能存在问题。

打印问题

#printOn: 可能发生的一个问题是无限递归。当打印 s 时，人们也想打印它的元素，在我们的例子中，这种方法会递归地尝试在此过程中打印 s，从而产生无限循环。

为了防止这种情况发生，Pharo 使用 LimitedWriteStream 将在一定次数的迭代后停止写入，如果递归存在则破坏递归。

我自己没有检查过，但这似乎是 GNU Smalltalk 中发生的问题（根据问题。）

请注意，仅打印 Set 中的最大元素数是不够的。事实上，我们的集合只包含一个元素（它本身），这足以创建递归。

添加问题

正如@aka.nice 在他的评论中所观察到的，第二次添加 s 时也必须小心。为什么？因为，正如我们在上面的介绍中看到的，消息 add: s 将需要计算 s hash …。 s hash 是如何定义的？这是个有趣的问题。 Smalltalkers 经常面临在某些类中实现良好 #hash 的问题。由于 s 是一个集合，因此很容易将其元素的 hash 考虑到最终结果，对吧？ Pharo采用这种方式，看：

hash
  | hash |
  hash := self species hash.
  self size <= 10 ifTrue:
    [self do: [:elem | hash := hash bitXor: elem hash]].
  ^hash bitXor: self size hash

哪个上钩。为什么？因为集合 s 有 1 个元素（本身），所以条件 self size <= 10 是 true，该方法将尝试再次递归计算 s hash，导致，哦哦, 堆栈溢出.

结论

执行 Collection >> #printOn: 时要小心。即使集合不包含自身，如果存在从其中一个元素到包含它的集合的间接引用，也可能会出现递归。
实施时要小心Collection >> #hash（同理）
给自己加上一个Collection要小心。更一般地说，当集合包含一个元素（可能是间接的）引用时要小心，因为枚举这样的集合可能很棘手。
在数学（科学）中，集合不能是其自身的元素（这是集合论公理明确禁止的）。因此，re-think 你的 model 在违反这条来自极其成熟和进化的科学知识体系的规则之前。

为什么在 Smalltalk 中将集合添加到自身会爆炸？

Why adding a collection to itself blows up in Smalltalk?

collections

smalltalk

gnu-smalltalk

简介

我们的案例

问题

结论