學(xué)習(xí)github地址

今天來(lái)學(xué)習(xí)使用字典和散列表來(lái)存儲(chǔ)唯一值（不重復(fù)的值）的數(shù)據(jù)結(jié)構(gòu)

字典

在字典中申屹，存儲(chǔ)的是[鍵衡查，值]對(duì)兆旬，其中鍵名是用來(lái)查詢特定元素的, 字典也稱作映射、符號(hào)表或關(guān)聯(lián)數(shù)組, 在計(jì)算機(jī)科學(xué)中, 字典經(jīng)常用來(lái)保存對(duì)象的引用地址

1. 創(chuàng)建字典類

與 Set 類相似朵栖，ECMAScript6 同樣包含了一個(gè) Map 類的實(shí)現(xiàn)，即我們所說(shuō)的字典

今天要實(shí)現(xiàn)的類就是以 ES6 中 Map 類的實(shí)現(xiàn)為基礎(chǔ)的柴梆。你會(huì)發(fā)現(xiàn)它和 Set 類很相似陨溅，但不同于存儲(chǔ)[值，值]對(duì)的形式绍在，我們將要存儲(chǔ)的是[鍵门扇，值]對(duì)

在字典中，理想的情況是用字符串作為鍵名揣苏，值可以是任何類型, 但是悯嗓，由于 JavaScript 不是強(qiáng)類型的語(yǔ)言，我們不能保證鍵一定是字符串卸察。我們需要把所有作為鍵名傳入的對(duì)象轉(zhuǎn)化為字符串

// 轉(zhuǎn)化為字符串
const 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;
};

// 打一個(gè)骨架
class Dictionary {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  }
}

// 不是只將 value 保存在字典中脯厨，而是要保存兩個(gè)值：原始的key 和 value
class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
  toString() {
    return `[#${this.key}: ${this.value}]`;
  }
}

2. 聲明一些字典所使用的方法

   • set(key,value):向字典中添加新元素。如果 key 已經(jīng)存在坑质，那么已存在的 value 會(huì)被新的值覆蓋
   • remove(key):通過(guò)使用鍵值作為參數(shù)來(lái)從字典中移除鍵值對(duì)應(yīng)的數(shù)據(jù)值
   • hasKey(key):如果某個(gè)鍵存在與字典中, 返回 true, 否則返回 false
   • get(key):通過(guò)鍵值為參數(shù)查找特定的值返回
   • clear():刪除字典中的所有值
   • size():返回字典包含值的數(shù)量
   • isEmpty():在 size 等于 0 的時(shí)候?yàn)?true
   • keys():將字典所包含的所有鍵名以數(shù)組形式返回
   • values():將字典所包含的所有數(shù)值以數(shù)組形式返回
   • keyValues():將字典中所有[鍵,值]以數(shù)組形式返回
   • forEach(callbackFn):迭代字典所有的鍵值對(duì), callbackFn有兩個(gè)參數(shù): key 和 value. 該方法可以在回調(diào)函數(shù)返回 false 時(shí)被中止

3. 實(shí)現(xiàn)上面的方法

// 字典的實(shí)現(xiàn)
class Dictionary {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  }

  // 已經(jīng)存在一個(gè)給定鍵名的鍵值對(duì)（表中的位置不是 null 或 undefined）合武，那么返回 true
  hasKey(key) {
    return this.table[this.toStrFn(key)] != null;
  }

  set(key, value) {
    if (key != null && value != null) {
      const tableKey = this.toStrFn(key); // 獲取 key 的字符串
      this.table[tableKey] = new ValuePair(key, value); // 創(chuàng)建一個(gè)新的鍵值對(duì)并將其賦值給 table 對(duì)象上的 key屬性（tableKey）
      return true;
    }
    return false;
  }

  // 檢索一個(gè)值
  get(key) {
    // 首先檢索存儲(chǔ)在給定key 屬性中的對(duì)象,
    const valuePair = this.table[this.toStrFn(key)];
    return valuePair == null ? undefined : valuePair.value;
  }

  // 這個(gè)也可以檢索一個(gè)值: 獲取兩次key的字符串以及訪問(wèn)兩次 table 對(duì)象
  get2(key) {
    if (this.hasKey(key)) {
      return this.table[this.toStrFn(key)].value;
    }
    return undefined;
  }

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

  keyValues() {
    return Object.values(this.table);
  }

  // 兼容版
  keyValues2() {
    const valuePairs = [];
    for (const key in this.table) {
      if (this.hasKey(key)) {
        valuePairs.push(this.table[key]);
      }
    }
    return valuePairs;
  }

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

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

  // 迭代字典中的每個(gè)鍵值對(duì)
  forEach(callbackFn) {
    const valuePairs = this.keyValues();
    for (let i = 0; i < valuePairs.length; i++) {
      // 執(zhí)行以參數(shù)形式傳入 forEach 方法的 callbackFn 函數(shù), 保存結(jié)果,
      const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
      // 回調(diào)函數(shù)返回了 false，我們會(huì)中斷 forEach 方法的執(zhí)行
      if (result === false) {
        break;
      }
    }
  }

  size() {
    return Object.keys(this.table).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;
  }
}

散列表

HashTable 類涡扼，也叫 HashMap 類稼跳，它是 Dictionary 類的一種散列表實(shí)現(xiàn)方式, 散列算法的作用是盡可能快地在數(shù)據(jù)結(jié)構(gòu)中找到一個(gè)值, 散列函數(shù)的作用是給定一個(gè)鍵值，然后返回值在表中的地址

1. 應(yīng)用

   • 它是字典的一種實(shí)現(xiàn)吃沪，所以可以用作關(guān)聯(lián)數(shù)組
   • 也可以用來(lái)對(duì)數(shù)據(jù)庫(kù)進(jìn)行索引, 創(chuàng)建一個(gè)索引來(lái)更快地查詢到記錄的 key
   • 使用散列表來(lái)表示對(duì)象, JavaScript 語(yǔ)言內(nèi)部就是使用散列表來(lái)表示每個(gè)對(duì)象

2. 創(chuàng)建散列表

使用一個(gè)關(guān)聯(lián)數(shù)組（對(duì)象）來(lái)表示我們的數(shù)據(jù)結(jié)構(gòu)汤善，和我們?cè)?Dictionary 類中所做的一樣

// 打一個(gè)骨架, 和字典差不多
class HashTable {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  }
}

3. 給類添加方法

   • put(key, value):向散列表增加一個(gè)新的項(xiàng)（也能更新散列表）
   • remove(key):根據(jù)鍵值從散列表中移除值
   • get(key):返回根據(jù)鍵值檢索到的特定的值

class HashTable {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  }

  // 散列函數(shù)
  loseloseHashCode(key) {
    if (typeof key === "number") {
      return key;
    }
    const tableKey = this.toStrFn(key);

    let hash = 0; // 防止 key 是一個(gè)對(duì)象而不是字符串。我們需要一個(gè) hash 變量來(lái)存儲(chǔ)這個(gè)總和

    // charCodeAt() 方法可返回指定位置的字符的 Unicode 編碼票彪，返回值是 0 - 65535 之間的整數(shù)
    // 遍歷 key 并將從 ASCII表中查到的每個(gè)字符對(duì)應(yīng)的 ASCII 值加到 hash 變量中
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }

    // 為了得到比較小的數(shù)值红淡，我們會(huì)使用 hash 值和一個(gè)任意數(shù)做除法的余數(shù)（%)——這可以規(guī)避操作數(shù)超過(guò)數(shù)值變量最大表示范圍的風(fēng)險(xiǎn)。
    return hash % 37;
  }

  hashCode(key) {
    return this.loseloseHashCode(key);
  }

  // 將鍵和值加入散列表
  put(key, value) {
    if (key != null && value != null) {
      //對(duì)于給出的 key 參數(shù)降铸，我們需要用所創(chuàng)建的 hashCode 函數(shù)在表中找到一個(gè)位置
      const position = this.hashCode(key);
      // 為了信息備份將原始的 key 保存下來(lái)
      this.table[position] = new ValuePair(key, value);
    }
  }

  // 從散列表中獲取一個(gè)值
  get(key) {
    const valuePair = this.table[this.hashCode(key)];
    return valuePair == null ? undefined : valuePair.value;
  }

  // 移除一個(gè)值
  remove(key) {
    const hash = this.hashCode(key);
    const valuePair = this.table[hash];
    if (valuePair != null) {
      delete this.table[hash];
      return true;
    }
    return false;
  }

  toString() {
    if (this.isEmpty()) {
      return "";
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
      ].toString()}}`;
    }
    return objString;
  }
}

// 使用 HashTable
const hash = new HashTable();
hash.put("Gandalf", "gandalf@email.com");
hash.put("John", "johnsnow@email.com");
hash.put("Tyrion", "tyrion@email.com");

console.log(hash.hashCode("Gandalf") + " - Gandalf"); // 19 - Gandalf
console.log(hash.hashCode("John") + " - John"); // 29 - John
console.log(hash.hashCode("Tyrion") + " - Tyrion"); // 16 - Tyrion

數(shù)據(jù)結(jié)構(gòu)

4. 散列表和散列集合

在一些編程語(yǔ)言中在旱，還有一種叫作散列集合的實(shí)現(xiàn)。散列集合由一個(gè)集合構(gòu)成推掸，但是插入桶蝎、移除或獲取元素時(shí)，使用的是 hashCode 函數(shù), 可以使用散列集合來(lái)存儲(chǔ)所有的英語(yǔ)單詞（不包括它們的定義）谅畅。和集合相似登渣，散列集合只存儲(chǔ)不重復(fù)的唯一值

5. 處理散列表中的沖突

有時(shí)候，一些鍵會(huì)有相同的散列值毡泻。不同的值在散列表中對(duì)應(yīng)相同位置的時(shí)候胜茧，我們稱其為沖突

const hash = new HashTable();
hash.put("Ygritte", "ygritte@email.com"); // 4
hash.put("Jonathan", "jonathan@email.com"); // 5
hash.put("Jamie", "jamie@email.com"); // 5
hash.put("Jack", "jack@email.com"); // 7
hash.put("Jasmine", "jasmine@email.com"); // 8
hash.put("Jake", "jake@email.com"); // 9
hash.put("Nathan", "nathan@email.com"); // 10
hash.put("Athelstan", "athelstan@email.com"); //7
hash.put("Sue", "sue@email.com"); // 5
hash.put("Aethelwulf", "aethelwulf@email.com"); // 5
hash.put("Sargeras", "sargeras@email.com"); // 10

• 處理沖突有幾種方法：分離鏈接、線性探查和雙散列法 (了解為主, 后續(xù)補(bǔ)充)

ES6 Map 類

ECMAScript 2015 新增了 Map 類牙捉≈褡幔可以基于 ES2015 的 Map 類開發(fā)我們的 Dictionary 類

ES6 WeakMap 和 WeakSet 類

1. Map 和 Set 與其弱化版本之間僅有的區(qū)別是:
   • WeakSet 或 WeakMap 類沒(méi)有 entries、keys 和 values 等方法
   • 只能用對(duì)象作為鍵

ES6 的 Set Map WeakMap WeakSet 數(shù)據(jù)結(jié)構(gòu) => 阮一峰文檔