Здравствуйте, Sinclair, Вы писали:

S>Я плохо знаком с миром ФП, и пока что до меня не доходит, каким волшебным образом memoize поможет сделать из мутабельной хеш-таблицы эффективную иммутабельную.

Хеш-таблицы у меня были не иммутабельные, а просто не блокирующие.

Необходимо получить ссылку на пару { хеш, ссылка-на-дочернюю-таблицу } из родительской таблицы и в этой паре через CAS в цикле обновить ссылку для указания на новый экземпляр дочерней хеш-таблицы.

Цикл возникает при неудачном обновлении, т.е. если по данному хеш-коду конкурирующий поток уже внёс изменения в эту же пару в родительcкой таблице, тогда подготовленный сегмент отбрасывается и создаётся заново с заходом на новый cas.

При такой реализации N-арность уменьшает вероятность возникновения конфликтов в каждой отдельной паре.

Но, повторюсь, чем больше арность, тем больше данных копируется при создании копии сегмента, поэтому, подбор N стоит делать для вполне конкретного множества сценариев.