字典(Map)

回顾

• 集合:元素不重复

引入

请大家思考我们要存储一组值不重复的有序数据，除了集合，还可以用什么数据结构？

内容

字典(重点)

原生Map

WeakMap与WeakSet

任务

字典

字典

• 字典中存储的是[键，值]对，其中键名是用来查询特定元素的
• 字典中键不重复
• 集合以[值，值]的形式存储元素
• 字典以[键，值]的形式存储元素
• 字典也称作映射、符号表或关联数组

字典操作

• 创建
• 查找
• 添加
• 删除
• 清空
• 判空
• 长度
• 辅助方法

算法演示

创建字典

• JavaScript 的对象属性不重复，可保证字典中键是唯一的。
• 使用对象而不是数组来表示字典
• 对象属性名只能是字符串，属性值可以是任何类型
• 属性名：字典键字符串，属性值：{键:值}

创建字典

 
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(); 
}   
class Dictionary {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;  //转字符串方法
        this.table = {};
    }
    set(key,value){} //向字典中添加新元素
    remove(key){}    //移除键值对应的数据值
    hasKey(key){}    //查找存不存在
    get(key){}       //查找
    clear(){}        //清空
    size(){}         //长度
    isEmpty(){}      //判空
    keys(){}         //返回所有键数组
    values(){}       //返回所在值数组
    keyValues(){}    //返回所有{键:值}数组
    forEach(callbackFn){} //迭代
}

存在查找

• 如果元素在字典中，返回true，否则返回false。
• 用来检验某个元素是否存在于字典中

 
hasKey(key) {
    return this.table[this.toStrFn(key)] != null;
}

添加元素

• 该方法接收key 和value 作为参数
• key转成字符串作为属性名
• 为了保存字典原始键值数据，原始的key 和value同时作为属性值

添加元素

 
class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString() {
        return `[#${this.key}: ${this.value}]`;
    }
}
set(key, value) {
    if (key != null && value != null) {
        const tableKey = this.toStrFn(key); 
        this.table[tableKey] = new ValuePair(key, value); 
        return true;
    }
    return false;
}

删除元素

• 首先，验证给定的key 是否存在于字典中
• 如果存在，就从字典中移除，返回true，表示元素被移除；否则返回false

删除元素

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

查找元素

• 如果元素在字典中，返回元素值，否则返回undefined。
• 用来查找某个元素

 
// 方法一
get(key) {
    const valuePair = this.table[this.toStrFn(key)]; 
    return valuePair == null ? undefined : valuePair.value; 
}
 
//方法二
get(key) {
    if (this.hasKey(key)) {
        return this.table[this.toStrFn(key)];
    }
    return undefined;
}

辅助方法

• 返回字典中键值对数组，键数组，值数组

 
//方法一
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() {
    return this.keyValues().map(valuePair => valuePair.key);
}
values() {
    return this.keyValues().map(valuePair => valuePair.value);
}

迭代元素

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

 
forEach(callbackFn) {
    const valuePairs = this.keyValues();
    for (let i = 0; i < valuePairs.length; i++) { 
        const result = callbackFn(valuePairs[i].key, valuePairs[i].value); 
        if (result === false) {
            break; 
        }
    }
}

获取长度

• 返回字典中有多少元素

 
size() {
    return Object.keys(this.table).length;
}

清空

• 清空字典

 
clear() {
    this.table = {};
}

判空

• 判断字典是否为空，为空返回true,否则返回false

 
isEmpty() {
    return this.size() === 0;
}

转字符串

 
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;
}

字典使用

• 用new创建Dictionary对象

 
//创建
const dictionary = new Dictionary();
//添加
dictionary.set('Gandalf', 'gandalf@email.com');
dictionary.set('John', 'johnsnow@email.com');
dictionary.set('Tyrion', 'tyrion@email.com');
//查找
console.log(dictionary.hasKey('Gandalf'));  //true
console.log(dictionary.size()); //3
console.log(dictionary.keys());  //["Gandalf", "John", "Tyrion"]
console.log(dictionary.values()); //["gandalf@email.com", "johnsnow@email.com", "tyrion@email.com"]
console.log(dictionary.get('Tyrion')); //tyrion@email.com
dictionary.remove('John');
dictionary.forEach((k, v) => {
    console.log('forEach: ', `key: ${k}, value: ${v}`);
});

原生Map

• ECMAScript 2015 新增了Map类作为JavaScript API

原生Map

 
const map = new Map();
map.set('Gandalf', 'gandalf@email.com');
map.set('John', 'johnsnow@email.com');
map.set('Tyrion', 'tyrion@email.com');
console.log(map.has('Gandalf')); // true
console.log(map.size); // 3
console.log(map.keys()); // 输出{"Gandalf", "John", "Tyrion"}
console.log(map.values()); // 输出{"gandalf@email.com", "johnsnow@email.com","tyrion@email.com"}
console.log(map.get('Tyrion')); // tyrion@email.com
map.delete('John');

WeakMap与WeakSet

• ES2015 还增加了它们的弱化版本，WeakSet 和WeakMap
• WeakSet 或WeakMap 类没有entries、keys 和values 等方法
• 只能用对象作为键
• 创建和使用这两个类主要是为了性能

WeakMap与WeakSet

 
const map = new WeakMap();
const ob1 = { name: 'Gandalf' }; 
const ob2 = { name: 'John' };
const ob3 = { name: 'Tyrion' };
map.set(ob1, 'gandalf@email.com'); 
map.set(ob2, 'johnsnow@email.com');
map.set(ob3, 'tyrion@email.com');
console.log(map.has(ob1)); 
console.log(map.get(ob3));
map.delete(ob2); 

任务

利用字典结构设计一款通讯录软件，通讯录信息包含姓名、电话、邮箱等信息，可以添加、删除、查找信息。