什么是最好的算法,找到一个没有使用从容量为百万行的表中使用的ID

Question

详细说明... a)表(BIGTABLE)具有容纳一百万行的能力,主键作为ID.(随机且唯一的)b)可以使用什么算法来获得到目前为止尚未使用的ID.此数字将用于在表BIGTABLE中插入另一行.

使用更多详细信息更新了问题.C)此表已有大约100 K行,主键不是设置为标识.d)当前,生成一个随机数作为主键,并在该表中插入一行,如果插入失败,则生成另一个随机数.问题是有时它进入一个循环并且生成的随机数非常随机,但不幸的是,它们已经存在于表中.所以,如果我们在一段时间后再尝试使用随机数生成数,它就可以了.e)sybase rand()函数用于生成随机数.

希望这个问题的补充有助于澄清一些观点.

Answer 1

问题当然是:为什么你想要随机ID？

我遇到类似要求的一个案例是webapp的客户端ID:客户端使用他的客户端ID(存储在cookie中)识别自己,因此必须很难强制猜测另一个客户端的ID(因为这样会允许劫持他的数据).

我使用的解决方案是将顺序int32与随机int32组合以获得我用作客户端ID的int64.在PostgreSQL中:

CREATE FUNCTION lift(integer, integer) returns bigint AS $$
SELECT ($1::bigint << 31) + $2
$$ LANGUAGE SQL;

CREATE FUNCTION random_pos_int() RETURNS integer AS $$
select floor((lift(1,0) - 1)*random())::integer
$$ LANGUAGE sql;

ALTER TABLE client ALTER COLUMN id SET DEFAULT
lift((nextval('client_id_seq'::regclass))::integer, random_pos_int());

生成的ID是"一半"随机,而另一半"半"保证您无法两次获得相同的ID:

select lift(1, random_pos_int());  => 3108167398
select lift(2, random_pos_int());  => 4673906795
select lift(3, random_pos_int());  => 7414644984
...

Answer 2

如果 ID 是纯粹随机的，则没有算法能够以类似的随机方式找到未使用的 ID，而无需暴力破解。然而，只要随机唯一 id 的位深度相当大（比如 64 位），就可以避免与一百万行发生冲突。如果它与插入物发生碰撞，请重试。