有人知道有效支持这两种操作的数据结构吗？

1. 在数据结构中插入一个值。
2. 从数据结构中出队并以统一随机概率返回条目。

这有点像总是在介绍性概率类中出现的规范的“大理石袋”。您可以将任意弹珠放入袋中，然后可以有效地随机去除弹珠。

我拥有的最佳解决方案如下-使用自平衡二进制搜索树（AVL，AA，红色/黑色等）存储元素。这给出了O（lg
n）插入时间。要删除随机元素，请选择一个随机索引i，然后从树中定位并删除第ith个元素。如果适当地扩充了结构，则也可以使其在O（lg n）时间内运行。

这个运行时当然还不错，但是我很好奇是否可以做得更好-也许O（1）用于插入，O（lg n）用于出队？还是可以使用哈希函数在 预期的
O（1）插入和删除操作中运行？还是更强的摊销范围？

有谁对如何使它渐近更快有任何想法？