基于JavaScript Map的实体关系查询哈希算法实现问题咨询

问题A答复 #

可以实现，不需要设计特殊的单一哈希算法同时匹配两种查询场景，只要在插入关系数据时同步生成对应两类查询的索引键存入Map即可，查询时根据当前持有的参数生成对应规则的键就能直接命中结果。

问题B答复 #

键生成规则 #

完全可以基于已有的用户ID字符串拼接生成键，不需要额外引入复杂的哈希算法，规则如下：

• 单对象查询场景键：固定前缀person: + 对应用户的id值，该键对应的存储值为所有和该用户相关的关系对象数组
• 双对象定向查询场景键：固定前缀dir_pair: + 发起方id + 接收方id，该键对应的存储值为两个用户之间指定方向的所有关系对象数组
• 双对象无向查询场景键：固定前缀undir_pair: + 两个用户id排序后拼接的字符串，该键对应的存储值为两个用户之间双向的所有关系对象数组

代码实现示例 #

const relationMap = new Map()

// 插入关系数据的方法
function addRelation(relation) {
  const { from, to } = relation
  // 新增单用户索引
  ;[from, to].forEach(userId => {
    const key = `person:${userId}`
    if (!relationMap.has(key)) relationMap.set(key, [])
    relationMap.get(key).push(relation)
  })
  // 新增定向双用户索引
  const dirKey = `dir_pair:${from}:${to}`
  if (!relationMap.has(dirKey)) relationMap.set(dirKey, [])
  relationMap.get(dirKey).push(relation)
  // 新增无向双用户索引
  const undirKey = `undir_pair:${[from, to].sort().join(':')}`
  if (!relationMap.has(undirKey)) relationMap.set(undirKey, [])
  relationMap.get(undirKey).push(relation)
}

// 单用户查询示例：查John的所有关系
const johnRelations = relationMap.get(`person:someUUID-John`) || []

// 定向双用户查询示例：查John打给Sally的所有通话
const johnToSallyCalls = relationMap.get(`dir_pair:someUUID-John:someUUID-Sally`) || []

// 无向双用户查询示例：查John和Sally之间所有双向关系
const johnSallyAllRelations = relationMap.get(`undir_pair:${['someUUID-John', 'someUUID-Sally'].sort().join(':')}`) || []

方案优势 #

所有查询操作的时间复杂度都是O(1)，插入操作的额外开销极低，完全适配你提到的两类查询场景。

内容的提问来源于stack exchange，提问作者foxtrotuniform6969