狗家昂赛

duangduangduang 发表于 2018-5-20 05:36
我当时说BST logn找key，不过他说换了思路，比如eplison是 0.1那就以0.1为间隔建bucket, 就是你会有 0.1, ...

没太理解，那map的key如何设置可以实现O（1）的查询呢？求楼主大大解惑~

idatascience 发表于 2018-5-22 01:15
没太理解，那map的key如何设置可以实现O（1）的查询呢？求楼主大大解惑~

我回忆回忆，如果epsilon 是0.1，代表最小精度是0.1, 1/0.1 = 10, 10就是用来计算bucket的multipler

如果put(1.2, "hello") ，那就把 （1.2， "hello")这个pair放到 1.2 x 10 = 12 的bucket里面

如果要查找 get( 1.22) , 那么就去bucket 1.22 * 10 = 12的bucket 和他的两边邻居的bucket里面找（ 11， 13，这个case直接在12就找到了，那么返回hello）
如果查 get(1.12)， 那么就去 bucket 1.12 * 10 = 11的bucket 和他两遍邻居（10, 12）找

因为epsilon是0.1. 如果我们把每个bucket的范围限制在0.1 (方便计算，乘以multipler映射成整数），那么我们知道符合结果的key如果存在，那么一定在他整数映射的bucket或者他两遍的邻居里面。

补充内容 (2018-5-22 05:41):
输入法血崩，两边的邻居，意会下吧

楼主加油!