Введение
A Set - это разновидность HashedCollection, специально разработанная для быстрой проверки членства. Внутренне Set имеет массив HashTable, sparce со множеством пустых слотов, чтобы минимизировать количество коллизий . Когда мы #add: элемент Set, index HashTable вычисляется как (hash \\ size) + 1, где #\\ - операция mod , size - длина стола. Если слот в index уже занят, index увеличивается до тех пор, пока не будет найден свободный слот, и элемент не будет там сохранен ( NB , + 1, поскольку массивы Smalltalk имеют значение 1 - на основании.) [ср. Как на самом деле работает Set ]
Наш кейс
Теперь посмотрим, что происходит с кодом вопроса:
1. s := Set new.
2. s add: s.
Как описано выше, на шаге 2 add: s будет вычислять:
s hash \\ p + 1
, где p - начальное количество слотов внутренней таблицы s (простое число, устанавливается на 5 или 7 при первом создании набора и увеличивается позже при необходимости.)
Пока все хорошо. Но могут быть некоторые
Вопросы
Где? В зависимости от диалекта Smalltalk, может быть проблема с #printOn: или со следующим add: обозначением элемента.
Печатный выпуск
Проблема, которая может возникнуть с #printOn:, заключается в бесконечной рекурсии . При печати s можно также распечатать его элементы, и в нашем случае такой подход рекурсивно попытается напечатать s в процессе, создавая бесконечную округлость.
Чтобы этого не произошло, Pharo использует LimitedWriteStream, который прекратит запись после определенного числа итераций, нарушая рекурсию, если она существует.
Я не проверял это сам, но эта проблема, кажется, происходит в GNU Smalltalk (в зависимости от вопроса).
Обратите внимание, что недостаточно печатать только максимальное количество элементов в Set. На самом деле наш набор содержит только один элемент (сам по себе), которого достаточно для создания рекурсии.
Дополнительный выпуск
Как заметил @ aka.nice в своем комментарии, следует также соблюдать осторожность при добавлении s во второй раз. Зачем? Потому что, как мы видели во введении выше, сообщение add: s должно будет вычислять s hash …. И как определяется s hash? Это интересный вопрос. Маленькие говорящие обычно сталкиваются с проблемой реализации хорошего #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 к себе. В целом, будьте осторожны, когда коллекция содержит элемент с (возможно, косвенной) ссылкой на него, поскольку перечисление такой коллекции может быть сложным.
В математике (естествознании) множество не может быть элементом самого себя (это явно запрещено аксиомами теории множеств). Итак, переосмыслите свою модель, прежде чем нарушать это правило, которое исходит от чрезвычайно зрелой и развитой научной совокупности знаний.