哈希表是get每一个key的value,而本题没有value,只有key
我们准备两张哈希表,以及一个变量 :size。
一个表存放某 key 的标号,另一个表根据根据标号取某个key
如下图所示:
A是第0个进来的
B是第二个进来的
我们现在先忽略remove行为 。
就这样一直加到25
此时size为26
现在用户让我随机等概率返回一个数,怎么做?
因为我有size,我可以用math.random函数随机出0-25中的等概率的一个,随机出来的是哪个数字,在map2里面把哪个数字的字符串返回
一言以蔽之:用map1来确定size,确定size后,用math.random 来确定map2中返回哪个字符串!
比如,如果返回的是25,那么返回z
代码 如下:
math.random产生0-1之间double类型的数!
乘以size后,得到0-size之间的某个随机数
如果加了remove行为
比如现在加了很多数!
现在用户要求remove一些key
假设我们remove掉map1和map2 中的17
这样就会在两个map 0-999 这个区间产生了一个洞,
如果删掉20,那么又产生了一个洞
如果产生的洞非常多了,接下来用户让我们get random时候,比如要查17,会发现查不到纪录
如果用户删了999个,只有1个index上有东西,产生了999个洞,那我get random 给用户random的话,会非常的慢,肯定不会是O(1)
解决办法:
若此时size 是1000,要删掉17,
我们把最后一条去填补到17那个洞上,然后删掉最后一条,然后size-1
有人说 会把顺序打乱,但是map里面本身就是无序的!所以不存在打乱一说。
(我们维持序的目的,就是为了random,所以可以让其乱序,只要保证其不产生 洞)
这种思路很重要:不想产生洞,那么就拿最后一个位置上的数 往上填!