第八章 字典

自我测试

本篇文章的测试用例及调试方法见前言

说明

你已经知道，集合表示一组互不相同的元素（不重复的元素）。在字典中，存储的是键，值]对，其中键名是用来查询特定元素的。字典和集合很相似，集合以[值，值]的形式存储元素，字典则是以[键，值]的形式来存储元素。字典也称作映射。

简单图解

一个字典基本方法

• set(key,value) : 向字典中添加新元素。
• hasKey(key) : 如果某个键值存在于这个字典中，则返回true，反之则返回false。
• get(key) :通过键值查找特定的数值并返回。
• keys()：将字典所包含的所有键名以数组形式返回。
• values()：将字典所包含的所有数值以数组形式返回。
• remove(key) : 通过使用键值来从字典中移除键值对应的数据值。
• keyValues:将字典中所有的[键,值]对返回
• forEach:迭代字典中所有的键值对callBackFn有两个参数(key,value),该方法可以在回调返回false的时候中止回调,类似(every方法)
• clear() : 移除字典中的所有元素
• size() : 返回字典的元素个数
• isEmpty: 字典是空的

class ValuePair<K, V> {
    key: K;
    value: V;


    constructor(key: K, val: V) {
        this.key = key;
        this.value = val;
    }

    toString() {
        return `[#${this.key}: ${this.value}]`
    }
}

function defaultToString(key: any) {
    if (key === null) {
        return "NULL";
    } else if (key === undefined) {
        return "UNDEFINED"
    } else if (typeof key === 'string' || key instanceof String) {
        return key + '';
    } else {
        return key.toString();
    }
}

export default class Dictionary<K, V> {
    table: any;
    count: number;
    toStrFn: any;

    constructor(toStrFn: any = defaultToString) {
        this.table = {};
        this.count = 0;
        this.toStrFn = toStrFn;
    }

    set(key: K, value: V) {
        if (key == null || value == null) {
            return false;
        }
        let newKey = this.toStrFn(key)
        //判断是否存在,存在就是覆盖,并不需要+1
        if (!this.hasKey(key)) {
            this.count++;
        }
        this.table[newKey] = new ValuePair(key, value); 
        return true;
    }

    hasKey(key: K) {
        let newKey = this.toStrFn(key)
        //这里是一个对象,所以不要担心内部是0的特殊情况
        return !!this.table[newKey];
    }

    get(key: K) {
        let newKey = this.toStrFn(key)
        if (this.hasKey(key)) {
            return this.table[newKey].value;
        }
        return undefined;
    }

    keys() {
        return this.keyValues().map(item => item.key);
    }

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

    keyValues(): Array<ValuePair<K, V>> {
        let resultArray = []
        for (let tableKey in this.table) {
            resultArray.push(this.table[tableKey]);
        }
        return resultArray;
    }

    forEach(callBackFn: (key: K, value: V) => any) {
        for (let itemsKey in this.table) {
            let element: ValuePair<K, V> = this.table[itemsKey];
            if(callBackFn(element.key, element.value) === false){
                break;
            };
        }
    }

    remove(key: any): Boolean {
        if (!this.hasKey(key)) {
            return false;
        }
        let newKey = this.toStrFn(key);
        delete this.table[newKey];
        this.count--;
        return true;
    }

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

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

    size() {
        return this.count;
    }

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

书中代码

function defaultToString(item: any): string {
  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 ValuePair<K, V> {
  constructor(public key: K, public value: V) {}

  toString() {
    return `[#${this.key}: ${this.value}]`;
  }
}

export default class Dictionary<K, V> {
  private table: { [key: string]: ValuePair<K, V> };

  constructor(private toStrFn: (key: K) => string = defaultToString) {
    this.table = {};
  }

  set(key: K, value: V) {
    if (key != null && value != null) {
      const tableKey = this.toStrFn(key);
      this.table[tableKey] = new ValuePair(key, value);
      return true;
    }
    return false;
  }

  get(key: K): V {
    const valuePair = this.table[this.toStrFn(key)];
    return valuePair == null ? undefined : valuePair.value;
  }

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

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

  values(): V[] {
    return this.keyValues().map(
      (valuePair: ValuePair<K, V>) => valuePair.value
    );
  }

  keys(): K[] {
    return this.keyValues().map(
      (valuePair: ValuePair<K, V>) => valuePair.key
    );
  }

  keyValues(): ValuePair<K, V>[] {
    return Object.values(this.table);
  }

  forEach(callbackFn: (key: K, value: V) => any) {
    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;
      }
    }
  }

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

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

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

leetcode对应训练