如何用JavaScript实现双向映射?



本文翻译自 《How to create a Bidirectional Map in JavaScript》

双向映射是指在键值对中建立双向一一对应关系的一种模式。它既可以通过键名(key)去获取值(value),也可以通过值去获取键名。让我们看下如何在JavaScript中实现一个双向映射,以及 TypeScript 中的应用。

双向映射背后的计算机科学与数学

首先看一下双向映射的基本定义:

在计算机科学中,双向映射是由一一对应的键值对组成的数据结构,因此在每个方向都可以建立二元关系:每个值也可以对应唯一的键。

202112200842757.png

百科指路双向映射

计算机科学中的双向映射,源于数学上的双射函数。双射函数是指两个集合中的每个元素,都可以在另一个集合中找到与之匹配的另一个元素,反之也可以通过后者找到匹配的前者,因此也被叫做可逆函数。

202112200840350.png

百科指路: 双射函数

扩展:

  • 单射(injection):每一个x都有唯一的y与之对应;

  • 满射(surjection):每一个y都必有至少一个x与之对应;

  • 双射(又叫一一对应,bijection):每一个x都有y与之对应,每一个y都有x与之对应。

根据上面的说明,一个简单的双射函数就像这样:

f(1) = 'D';
f(C) = 3;

另外,双射函数需要两个集合的长度相等,否则会失败。

初始化双向映射

我们可以在JavaScript 中创建一个类来初始化键值对:

const bimap = new BidirectionalMap({
 a: 'A',
 b: 'B',
 c: 'C',
})

在类里面,我们将会创建两个列表,一个用来处理正向映射,存放初始化对象的副本;另一个用来处理逆向映射,存放的内容是「键」「值」翻转后的初始化对象。

class BidirectionalMap {
 fwdMap = {}
 revMap = {}

 constructor(map) {
     this.fwdMap = { ...map }
     this.revMap = Object.keys(map).reduce(
        (acc, cur) => ({
             ...acc,
            [map[cur]]: cur,
        }),
        {}
    )
}
}

注意,由于初始对象本身的性质,你不能用数字当 key,但可以作为值来使用。

const bimap = new BidirectionalMap({
 a: 42,
 b: 'B',
 c: 'C',
})

如果不满足于此,也有更强大健壮的实现方式,按照 JavaScript 映射数据类型 中允许使用数字、函数甚至NaN来作为 key 的规范来实现,当然这会更加复杂。

通过双向映射获取元素

现在,我们有了一个包含两个对象的数据结构,它们互为键值对的镜像。我们现在需要一个方法来取出元素,让我们来实现一个 get() 函数:

 get( key ) {
   return this.fwdMap[key] || this.revMap[key]
}

这个方法非常简单: 如果正向映射里存在就返回,否则返回逆向映射,都没有就返回 undefined

试一下获取元素:

console.log(bimap.get('a')) // displays A
console.log(bimap.get('A')  // displays a

给双向映射添加元素

目前映射还无法添加元素,我们创建一个添加方法:

add(pair) {
   this.fwdMap[pair[0]] = pair[1]
   this.revMap[pair[1]] = pair[0]
}

add 函数接收一个双元素数组(在TypeScript 中叫做元组),按不同键值顺序加入到相应对象中。

现在我们可以添加和读取映射中的元素了:

bimap.add(['d', 'D'])
console.log( bimap.get('D') ) // displays d

在TypeScript中安全使用双向映射

为了确保数据类型安全,我们可以在 TypeScript 中进行改写,对输入类型进行检查,例如初始化的映射必须为一个通用对象,添加的元素必须为一个 元组

class BidirectionalMap {
 fwdMap = {}
 revMap = {}

 constructor(map: { [key: string]: string }) {
     this.fwdMap = { ...map }
     this.revMap = Object.keys(map).reduce(
        (acc, cur) => ({
             ...acc,
            [map[cur]]: cur,
        }),
        {}
    )
}

 get(key: string): string | undefined {
     return this.fwdMap[key] || this.revMap[key]
}

 add(pair: [string, string]) {
   this.fwdMap[pair[0]] = pair[1]
   this.revMap[pair[1]] = pair[0]
}
}

这样我们的映射就更加安全和完美了。在这里,我们的 key 和 value 都必须使用字符串。


翻译:sherryhe
来源:https://juejin.cn/post/6976797991277428750

0 个评论

要回复文章请先登录注册