拐角垃圾桶花盆智能HashMap狂想曲

‍

观察走廊拐角垃圾桶和花盆引发的思考 - 智能 HashMap 狂想曲

‍ 上班时候的小脑洞 ‍

# 灵感

某公司在一个大平层, 走道靠近墙角处一定有摆放垃圾桶或者花盆这样的阻碍物, 经过休息时间的实地模拟发现: 这可以降低相向而行的两人在视线盲区发生转角碰撞的概率

‍

“也许可以类似这样设计 HashMap 中哈希冲突的预防方案? 设置一个导流的标志位? 根据当前 HashMap 的部分区块的拥挤程度进行灵活的判断?”

‍

# 场景

那么, 来假设这样的画面: 将一个初始化的全空的 HashMap 平均划分为 8 个区间(设计划分密度为 2³, 可以说设置密度参数为 3) ;当然 HashMap 是会扩容的, 因此这个区间的端点也要每次获得 length 然后计算出来更新

‍


hashMap :    0 |________|________|________|________|________|________|________|________| N

在这个情境下, “转角碰撞” 意味着: 两个实体在致盲效果影响下进入了不好的位置. 也就是可以解释为发生了哈希碰撞 (不知道那里有人, 还是冲过去了, 撞了)


                |________|________|________|________|________|________|________|________|
                 |
                 玄
                 |
                 桃

如图是一般情况(JDK1.8/plus, 前 8(默认)是 Key 蜈蚣链表), 在这时候可以做些小动作了, 在区间摆放"垃圾桶"或者"花盆"?

               [X]      [X]
                |________|________|________|________|________|________|________|________|
                 |
                 玄
                 |
                 桃

这里的意思就是"看到花盆或者垃圾桶, 人会下意识绕开", 假设这个区间已经被打上了"有冲撞"的标记, 那么下次再进来被放进这个区间的概率就会小了.

但是怎么做呢?

我想了几个点子, 抛砖引玉

‍

# 版本

‍

# V1 subList + HashCode 歪把映射

简单想到的是维护一个记录垃圾桶和区间 sub-List, 当生成了 hashCode 的时候额外加一些逻辑: “当我要去的区间已经被摆放了垃圾桶, 我就取一个更新的(加上参数的)哈希码 (当然, 从底层来说哈希码是固定死的, 意味着需要额外封一层), 再判断几次(这个参数可以调)”

当然如果要更加智能的话就要用其他东西来换了, 性能什么的, 再维护一个 subHashMap 也是一样的道理.

‍

可是这个是一个静态的情况, 如何动态的修改这个垃圾桶的摆放呢? 需要加东西了.

               [X]      [X]      [X]      [X]
                |________|________|________|________|________|________|________|________|
                 |                    |
                 玄                   小
                 |                    |
                 桃                   丑

例如同时在多个地方发生了哈希碰撞, 单一层级的垃圾桶显然就不行了, 只能在那里把垃圾桶和花盆倒的到处都是?

‍

# V2 subList + HashCode 歪把映射 + 多级垃圾分类 + 自动垃圾桶生成

               [X]      [X]      [X]      [X]
               [X]      [X]      [X]      [X]      [X]
                |________|________|________|________|________|________|________|________|
                 |                    |           |
                 玄                   小           一
                 |                    |           |
                 桃                   丑           心
                 |                    |
                 K                    先

每次发生冲突了, 就在这个区间旁边叠加一层垃圾桶, 优先把新的 Key 放到垃圾桶数量少的区间去.

‍

可是要是删除了这些产生冲突的对象了之后, 要不要连带把放置的垃圾桶丢出去呢? 如果要, 那怎么做? 扫描一遍? nonono 还是用第二个 subList 存放哈希冲突产生的位置吧, 让其周围的层数减一即可

(这个可以当成是一个特性, 没有作删除的时候就不需要这个插件)

‍

如此看来似乎可行, 但是为什么要这么做呢? 希望尽可能减少哈希冲突的可能性.

从性能上来看, 加装这么一整套逻辑(自己手写 hashMap)肯定在修改这个 HashMap 的时候带来性能上的压力, 需要维护一个 subList, 还要在插入和删除前后都进行维护. 显然, 客户需要的是"少冲突的高性能查询式 HashMap", 这个能否满足需求呢?

应该拿一个空白对照, 1K 条, 10K 条等情况进行插入 HashMap 操作, 最后看看 HashMap 的冲突概率是多少(不知道怎么方便看这个), 多次测量取平均值. 理论上讲肯定加了智能组件的 HashMap 一定比原生的更加平均一些, 碰撞少些.

‍

# V3 区间记录 subListA + HashCode 镜面映射 + 无级权重值 subListB + 插件式 + 优先队列 + 重映射 + 多线程优化 + 缓存优化

‍

还是不够抽象!还是没有跳出花盆-垃圾桶的实质!

我觉得这是一种惩罚机制, 循规蹈矩有奖励, 逾规越矩有惩罚. 那既然都上了一个 subList 了, 不如直接把一整个区间记录下来, 同时记录对应的权重, 其他的思路和上面相同

(当然说是插件, 事实上为了方便写的时候直接自己手写新的好了, 感觉不要去调教已经有的代码比较好罢)

‍

初始化 - 启动初始化插件 区间数量->subList * 2, 还要初始化各个参数等元件
插入 Map - 启动 Add 插件
1. 正常按照 JDK Map 计算 HashCode
2. 提前拿到要插入的位置, 查表找到对应的区间
3. 查表看看"适合不适合"插入 (需要排序)
  
  可以使用优先队列维护, 每次修改区间的权重的时候按照升序排列, 找到一定阈值就不找了, 认为该次插入非法]
  - 适合, 插入
  - 不适合, 更换 HashCode 再尝试 X 次插入 (X 参数也需要设置), 否则摆烂就地掩埋
    - 直接随机加上 33% * 区间个数的区间长度, 到达一个任意区间的"同样"位置
    - 加上区间长度 L’ * N 切换到最适合插入的区间(需要上述优先队列)的"同样"位置. (可选)
4. 插入的时候, 还要判断是不是发生冲突了, 如果发生需要大量惩罚! 没冲突只给少量惩罚 (大概的区分应该是 k 级别的). 判断就用对应位置指针移动次数来判断(造轮子)
5. 如果触发扩容 (size != size_before), 需要更新 subListA 区间范围
开始查询 Map - 启动 Select 插件
1. 正常按照 JDK Map 计算 HashCode
2. 继续查找 “对应位置”
  - 找到
  - 找不到, 按照上面的歪把子方案(重映射方案)发起 多线程查找同一位置在不同区间的所有替身位置, 找到返回对象
    - 缓存优化: 不简单直接返回对象, 而是包装好真实的 KV 到一个歪把子查询缓存, 其大小和更新周期可以自定义, 初步可委托 Redis 实现
开始修改 Map - 启动 Update 插件
1. 找到 | 调用 Select 插件
2. 修改
3. 退出
开始删除 Map - 启动 Delete 插件
1. 找到 | 调用 Select 插件
2. 修改, 更新记录值
  - 如果是一个产生 “垃圾桶” (惩罚值)的对象, 减少大量惩罚 (通过指针移动的次数判断是不是进入冲突区域了)
  - 如果只是基础对象, 减少少量惩罚
3. 退出
余下使用基础实现

‍

Java 没有指针特性, 上面提的指针移动这个概念是 “找到对应 K 之后往下搜寻想要的 V 的过程”

‍

# V4 吃了饭再想, 累了

‍

# 设计

详细的设计

‍

# 实现

代码实现

Github

‍

# 结尾

‍

之前没有接触过相关知识点, 可以说靠自己取得的这个尤里卡, 当然肯定是有大佬想过了

没测试过, 没写, 还在构思阶段. 有无大手子给点建议

此文档持续更新

‍

2024-07-19

在搬砖的玄桃 K

‍