唯一的标识符，基数尽可能小，不会在新旧数据集上发生碰撞。

Question

我收到一个或多个节点树。

节点上可能有，也可能没有ID属性。

目前，我正在通过树进行迭代，并在没有ID属性的节点上随机添加8位数。由于我不希望树上的节点超过1万个，所以发生碰撞的机会非常小。

但我仍在考虑如何最好地将ID的长度减少到4位数，同时确保在一棵树上没有碰撞。我想到的是在树上迭代一次，将现有的ID收集到一个Set中，然后再次添加新的ID，同时检查Set中是否有碰撞。每一棵树的Set都必须重新设置。

如果有更有效的方法可以实现这个目标，我将感谢你的意见和建议。

附录A:

我正在考虑以下（简化的0-9）问题。如果我有一组现有的ID [0, 1, 2, 5, 8, 9] 我必须生成随机数，直到我得到例如4（没有碰撞），我担心这在一个更大的Set上会有点慢，而且肯定不是最佳路线。

Answer 1

在这里，你有一个非常简单的方法，它将为你生成一个给定MAX范围的未使用的数字数组。

const MAX = 30;
const usedNumbers = [3, 4, 12, 13, 14, 16, 23, 27];

// https://stackoverflow.com/questions/3746725/how-to-create-an-array-containing-1-n
const notUsedNumbers = Array.from(Array(MAX), (_, i) => i+1).filter(i => !usedNumbers.includes(i));

console.log(notUsedNumbers);

并链接到fiddle。https:/jsfiddle.netL9r6anq1。

Answer 2

随机选择的10^8种可能性意味着你有50%的机会与只有10^4个物体发生碰撞（见生日悖论）；这不是 "很小 "的几率。将其降低到只有10^4种可能性与10^4个物体，意味着当你接近终点时，碰撞将接近100%，并且，如果你有一天有10k+1个物体，将永远不会终止。

一般来说，如果你想使用一个相对较短的ID空间，你就需要一个非常高效的冲突检测系统，比如将所有分配（或不分配）的值保存在一个划痕板中，或者干脆放弃随机分配值，按顺序进行。