拐角垃圾桶花盆 - 智能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

结尾(之前的)

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

11月的时候确定要加一个轮子项目, 本着自己"只做原创"的原则, 还是决定做这个自制HashMap吧. 大概花一个月时间慢慢磨用来春招是来得及的.

同时也打算加一个标准的参考他人的大项目, 当然还是希望做开源项目, 目前没选好.

更新

V4(确定) 包装类 + 碰撞标记 + 进出检票机制

2025-01-11 因为希望在简历里面加点东西, 最近重新捡起来了. 确定用这个方案进行:

可以说是上面的一些可以实现的妥协, 毕竟真正开发可不是动动嘴皮子就行的事情, 要权衡各种成本和可行性

思路方面

从需求转化到实现的过程

Bucket的2重List域, 第一重就是原本的链表(或者红黑树节点族), 第二重在这个节点的类里面再加一个域, 另一个List(实现用一个变量就行了), 用来存放 "这个节点产生的碰撞标记" .
- 碰撞标记的变化来源于增删
  1. 插入节点的时候, 节点已经有东西了的时候(发生碰撞), 需要往下去遍历插入的次数 (或者红黑树的调整次数) +
  2. 删除节点时, 减少对应的碰撞标记
包装类的使用方面, 在第一次进行hash的情况下进行一次判断: "是不是这个桶里面碰撞太多了(挂了太多节点)", 如果确实是, 就用包装类进行一次包装 (包装类的data指向原本的对象), 用新的对象进行再次hash计算, 到下一个地点 (同时记录包装次数, 一定次数后不包了直接插入, 同时要记录为一个WARN, 多次WARN会自动执行一次扩容操作 -- 这似乎也能防范DDOS啥的) , 正常没人占就插入.
- 同样的, 关于这个包装操作的阈值 (没时间去获取最好的效率了, 交给开源吧), 可以通过全局产生的"垃圾桶", 也就是所谓的标记数量/Hash链表长度计算, 一般按照75%来看, 最坏情况 75%的位子是有人的, 一般按照概率论将近45%的那个参数, 一次ReHash跳跃可以有50%左右的概率到达另外的无人区 (假设此时全局阈值为0, 也就是"位子很多, 找一次找不到就给你这一次机会") ; 之后快要达到75%的上限时候, 阈值随着碰撞次数(也就是产生的标记)而提高, 同时取得的对应位子如果拥挤程度过高也会进行"熔断"
进出检票说的就是刚才这个增删的东西. 进去要登记, 出去要退票, 就是这样很简单 +1 -1 就完事了bro

实现方面

PM做的事情, 评估可行性

包装类
- 每个对象加一个DATA封装类就行, 两个字段, 一个int随机数("产生跳变的数", 原型暂时取2的次方), 一个Data Object泛型
- 在对应的删除和比较时候也要做些小微调
检票机制
- 在重写的hashMap里面增加对应方法, 做可行的改造
碰撞标记
- 加字段的事情
每个HashMap的"区域感知"
- 还是加字段; 就是上面这些智能的判断功能, 直接惰性, 插入的时候也不要全表扫, 在自己字段里面瞅一眼就行