场景

在可视化搭建平台中有种称为'报告设计'的应用类型，其中可以*地拖拽操作可视化图表、富文本、图片图标等组件。提供对齐线功能，与常见软件中的对齐线交互差不多：在对组件进行拖拽移动的过程中，需要显示当前操作中的的组件同本页画布上其他组件在矩形包围盒的四条边和中心点的水平垂直对齐线，并吸附到对齐线上。
如下：

问题

在拖动组件过程中，在不断触发的Mousemove事件中对组件位置作更新操作；在这个过程中同时也会计算对齐线。先前计算对齐线的逻辑是这样的：

1. 根据事件对象计算当前组件四条边及中心点的水平线和垂直线位置

2. 从redux中取出所有该页面上的的组件数据widgetData

3. 遍历widgetData，计算所有组件的四边及中心点的水平线和垂直线位置

4. 在水平和垂直方向上匹配满足阈值之内的最近的坐标

5. 如果匹配有坐标，则渲染对齐线并做吸附效果再次调整组件位置

这种处理方式相当地简单暴力，很明显是存在问题的：单次计算需要遍历一次所有组件，时间复杂度就是O(n)。一个比较极端但也不算少见的场景是，用户只设置了一页画布并将宽高设置的足够大来容纳大量的组件，虽然单次计算复杂度是O(n)，但在拖拽过程中mousemove的触发频率非常高，性能的代价是很大的。

还有很关键的一点是，由于对齐线是需要在组件移动过程中实时计算的，因此也就不能对该计算方法做防抖和节流处理。

优化

摒弃每次都需要遍历所有组件的方式。看回上面计算对齐线的方式，我们知道要计算出匹配的对齐线，需要到的数据就是每个组件的位置坐标。那么，计算一遍所有组件的位置信息这一O(n)的计算量是一定少不了的，但我们不需要在每次mousemove中都做一次，而是将计算过的组件位置都缓存起来。相当于将每一个组件的四条边和中心点的横纵坐标都“离散”到X轴和Y轴上了。

实现方式分为两个部分：

一、在页面初始化或者组件位置变更后做数据缓存

1. 创建两个分别用于水平方向和垂直方向坐标数据存储的哈希表（可以用ES6中的Map来做存储对象）。key类型为整数；value为List类型，数组或者链表都可以；List中的节点是存放具体坐标和对应组件信息的Object

2. 放置组件后，计算该组件的两条垂直边和中心点的横坐标xl、xr、xc以及两条水平边和中心点的纵坐标yt、yd和yc

3. 将上一步计算出的xl、xr和xc存入水平方向的哈希表中，yt、yd和yc存入垂直方向的哈希表中；如果不是在初始化过程中，则需要先删除该组件先前在这两个哈希表中的数据

4. 坐标值是可以有小数部分的，但存入哈希表中时，使用坐标的整数部分作为key键就行了，value对象中存放有具体的坐标值就行了。后面会讲为什么。

二、实时计算对齐线的过程

1. 以水平方向的对齐线为例（垂直方向对齐线的计算也是一样一样的），先计算出此刻拖拽中的组件其中心点纵坐标yc

2. 因为是优先匹配位于阈值内最接近的坐标作为对齐线，那么又由上面可知，我们是将出现过的所有坐标值以其整数部分作为key存入哈希表中的；所以需要以yc作为中心点，向小于yc和大于yc的整数一个个作为key值取出哈希表里的数据进行遍历匹配。 例如：yc的值是10.70px，对齐线匹配的阈值是3px；那么就以key值为<10,11>,<12,9>,<13,8>这样一对对的顺序依次取出对应哈希表中的数据来匹配。之所以要一对对的判断，是因为key仅代整数部分，小数部分是不可知的，只有一对中的两对key所对应数据都遍历了，才能确定最接近的坐标值

3. 如果某个key键没有对应的value对象，则代表没有整数位为key的坐标，continue。当在某对key中有对应的value的话，遍历出其中的最小坐标值就是结果了，后面的都无需再判断的了直接break

4. 如果用中心点的纵坐标遍历完上述三对key后都无结果，则对组件顶部和底部两条边的纵坐标重复前面的步骤

结尾

经过优化后的实现方式，不管是组件位置变更后对哈希表的维护还是单次计算对齐线的时间复杂度都是常数级的了。当然，如果要考虑这么一种极端情况的话：所有组件的坐标值都很接近，那么它们的整数部分就都相同了。这时候所有数据都会存到同一个key里，在计算对齐线时，去遍历key对应的value就等同于原先遍历所有组件的方式了，时间复杂度退化为O(n)。 针对如此极端的情况，如果非要优化掉，也是可以做滴......