JavaScript数据结构与算法 - 字典

1. 什么是字典

  • 类似于集合,字典用来存储唯一值
  • 在字典中,存储的是 [键,值] 对,其中键名是用来查询特定元素的
  • 字典也称映射、符号表或关联数组
  • 在计算机科学中,字典常用来保存对象的引用地址
  • 字典的键只能有一个值

2. 字典的类和方法

2.1 创建字典类

字典中,键名最理想的情况是字符串,值可以是任何类型。但是JavaScript不是强类型的语言,所有需要将key转换为字符串。

function defaultToString(item) {
    if (item === null) {
        return 'NULL';
    } else if (item === undefined) {
        return 'UNDEFINED';
    } else if (typeof item === 'string' || item instanceof String) {
        return `${item}`;
    }
    return item.toString();
}

Dictionary类的骨架:

class Dictionary {
    constructor(toStrFn = defaultToString) {
        // 将key转换为字符串
        this.toStrFn = toStrFn;
        // 将[键,值]对保存为 table[key] = {key, value}
        this.table = {};
    }
}

一些常用方法:

  • set(key, value):向字典中添加新元素。如果key已存在,那么已存在的value会被新的值覆盖
  • remove(key):通过使用键值作为参数从字典中移除键值对应的数据值
  • hasKey(key):如果某个键值存在于字典中,返回true,否则返回false
  • get(key):通过以键值作为参数查找特定的数值并返回
  • clear():删除该字典中的所有值
  • size():返回字典所包含值的数量
  • isEmpty():在size等于0的时候返回true,否则返回false
  • keys():将字典所包含的所有键名数组形式返回
  • values():将字典所包含的所有数值数组形式返回
  • keyValues():将字典中所有**[键,值]对**返回
  • forEach(callbackFn):迭代字典中所有的键值对。callbackFn有两个参数:key和value。该方法可以在回调函数返回false时被中止

2.2 检测一个键是否存在于字典中

hasKey(key)方法会被set和remove等方法调用,需要先实现

hasKey(key) {
	// 如果已经存在一个给定键名的键值对,返回true,否则返回false
    return this.table[this.toStrFn(key)] != null;
}

2.3 在字典和ValuePair类中设置键和值

set方法:接收key和value作为参数。可用于添加新的值,或更新已有的值

set(key, value) {
    // 如果key和value不为null或undefined
    if (key != null && value != null) {
        // 获取key的字符串
        const tableKey = this.toStrFn(key);
        // 创建一个新的键值对并将其赋值给table对象上的key属性
        // 此处还需要实例化ValuePair类
        this.table[tableKey] = new ValuePair(key, value);
        return true;
    }
    return false;
}

ValuePair类定义如下:

class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString() {
        return `$[#${this.key}: ${this.value}]`
    }
}

为了保存信息的需要,要保存原始的key。因此,我们不是只将value保存在字典中,而是要保存两个值:原始的key和value


2.4 从字典中移除一个值

实现时要先搜索key,而不是value

remove(key) {
    if (this.hasKey(key)) {
        delete this.table[this.toStrFn(key)];
        return true;
    }
    return false;
}

2.5 从字典中检索一个值

方式一:(消耗比第二种方式少)

get(key) {
    // 检索存储在给定key属性中的对象
    const valuePair = this.table[this.toStrFn(key)];
    return valuePair == null ? undefined : valuePair.value;
}

方式二:
会获取两次key的字符串以及访问两次table对象:第一次是在hasKey方法中,第二次是在if语句内

get(key) {
    if (this.hasKey(key)) {
        return this.table[this.toStrFn(key)];
    }
    return undefined;
}

2.6 keys、values和keyValues方法

返回字典中所有键值对:

// ES2017引入Object的values方法
keyValues() {
    return Object.values(this.table);
}

所有浏览器都支持的方式:

keyValues() {
    const valuePairs = [];
    for (const k in this.table) {
        if (this.hasKey(k)) {
            valuePairs.push(this.table[k]);
        }
    }
    return valuePairs;
}

返回字典中所有(原始)键名:

keys() {
    // 调用所创建的keyValues方法来返回一个包含valuePair实例的数组,然后迭代每个valuePair并只返回它的key。
    return this.keyValues().map(valuePair => valuePair.key);
}

返回字典中包含的所有值构成的数组:

values() {
    return this.keyValues().map(valuePair => valuePair.value);
}

2.7 迭代字典中的每个键值对

forEach(callbackFn) {
    // 获取字典中所有valuePair构成的数组
    const valuePairs = this.keyValues();
    for (let i = 0; i < valuePairs.length; i++) {
        // 执行以参数形式传入forEach方法的callbackFn函数
        const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
        // 如果回调函数返回了false,中断forEach方法的执行,打断正在迭代valuePairs的for循环
        if (result === false) {
            break;
        }
    }
}

2.8 clear、size、isEmpty和toString方法

size() {
    return Object.keys(this.table).length;
    // 或者
    // return this.keyValues().length;
}
isEmpty() {
    return this.size() === 0;
}
clear() {
    this.table = {};
}
toString() {
    if (this.isEmpty()) {
        return '';
    }
    const valuePairs = this.keyValues();
    let objString = `${valuePairs[0].toString()}`;
    for (let i = 1; i < valuePairs.length; i++) {
        objString = `${objString}, ${valuePairs[i].toString()}`;
    }
    return objString;
}

3. 使用Dictionary类

const dictionary = new Dictionary();
dictionary.set('aaa', 'aaa@email.com');
dictionary.set('bbb', 'bbb@email.com');
dictionary.set('ccc', 'ccc@email.com');

console.log(dictionary.hasKey('aaa'));
console.log(dictionary.size());
console.log(dictionary.keys());
console.log(dictionary.values());
console.log(dictionary.get('bbb'));

dictionary.remove('bbb');
console.log(dictionary.keys());
console.log(dictionary.values());
console.log(dictionary.keyValues());

dictionary.forEach((k, v) => {
    console.log('forEach:', `key: ${k}, value: ${v}`);
});

JavaScript数据结构与算法 - 字典

上一篇:Python 数据类型字典(Dictionary)


下一篇:JAVA 数据结构(13):数据结构主要种接口和类