字典和散列表

1. 字典

• 在字典中，存储的是键值对，通过键进行查询。
• 字典也称作映射，符号表或关联数组。

1.1 自定义字典类

Dictionary 类：

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 转为字符串的函数，同样的逻辑也可以应用在自定义 Set 中。

字典所需方法：

• set(key, value)：向字典中添加新元素。如果 key 已存在，则 value 会被覆盖。
• remove(key)：从字典中移除键值对应的数据。
• hasKey(key)：如果某个键存在于该字典中，返回 true，否则返回 false。
• get(key)：根据 key 获取值。
• clear()：清空字典。
• size()：返回字典包含的数据量。
• isEmpty()：字典为空返回 true，否则返回 false。
• keys()：将字典包含的所有键名以数组形式返回。
• values()：将字典包含的所有值以数组形式返回。
• keyValues()：将字典中所有 [key, value] 对返回。
• forEach(callbackFn)：迭代字典中所有的键值对。回调函数有两个参数：key 和 value。该方法可以在回调函数返回 false 时被终止。

1.2 自定义字典方法

1.2.1 hasKey()

JavaScript 中只允许字符串或符号作为对象键，如果传入一个复杂对象，需要先转为字符串。

class Dictionary {
  hasKey(key) {
    return Object.prototype.hasOwnProperty.call(this.table, this.toStrFn(key));
  }
}

1.2.2 set(key, value)

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

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

说明

为了在字典中保存 value，将 key 转为了字符串，而为了保存信息，同样要保存原始的 key。因此不仅将 value 保存在字典中，而是通过 ValuePair 对象将原始的 key 和 value 都保持。

1.2.3 remove(key)

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

1.2.4 get(key)

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

1.2.5 keys()、values()、keyValues()

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

  // ES2017之前，更通用的方法
  keyValues() {
    const valuePairs = [];
    for(const k in this.table) {
      if(this.hasKey(k)) {
        valuePair.push(this.table[k])
      }
    }
    return valuePair;
  }

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

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

1.2.6 forEach()

class Dictionary {
  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;
      }
    }
  }
}

1.2.7 clear()、size()、isEmpty()、toString()

class Dictionary {
  clear() {
    this.table = {}
  }

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

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

  toString() {
    if(this.isEmpty()) {
      return '';
    } 
    const valuePairs = this.keyValues();
    let res = `${valuePairs[0].toString()}`;
    for(let i = 1; i < valuePairs.length; i++) {
      res = `${res}, ${valuePairs[i].toString()}`
    }
    return res;
  }
}

2. 散列表

• 散列算法的作用是尽可能快地在数据结构中找到一个值。给定一个键，通过散列函数计算出值在表中的位置。
• 散列表可以用来对数据库进行索引，也可以用作关联数组，JavaScript 中对象就是用散列表表示的。

2.1 创建散列表

使用一个关联数组来表示散列表：

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

2.1.1 散列函数

散列函数可以根据 key 计算出一个地址，这里简单对每个字符 ASCII 码的和取余：

class HashTable {
  loseloseHashCode(key) {
    if(typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for(let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  }

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

• 为了规避数值太大超过变量最大表示范围，使用 hash 值和一个数取余。

2.1.2 将键和值加入哈希表

class HashTable {
  put(key, value) {
    if(key != null && value != null) {
      const position = this.hashCode(key);
      this.table[position] = new ValuePair(key, value);
      return true;
    }
    return false;
  }
}

2.1.3 从散列表获取值

class HashTable {
  get(key) {
    const valuePair = this.table[this.hashCode(key)]
    return valuePair == null ? undefined : valuePair.value;
  }
}

说明

HashTable 和 Dictionary 类很相似。不同之处在于在 Dictionary 类中，直接以转为字符串的 key 作为属性保存数据，而 HashTable 会计算哈希值，以哈希值为属性保存数据。

2.1.4 从散列表中移除一个值

class HashTable {
  remove(key) {
    const position = this.hashCode(key);
    const valuePair = this.table[position];
    if(valuePair != null) {
      delete this.table[position];
      return true;
    }
    return false;
  }
}

2.2 散列表和散列集合

在某些编程语言中，有一种散列集合的实现。散列集合是一个集合，但插入、移除或获取元素时，使用 hashCode 函数计算哈希值，再根据哈希值查找数据。

2.3 处理哈希表中的冲突

有时候，有些键会计算出相同的散列值，称其为冲突。处理冲突的方法有：分离链接、线性探测和双散列法等等。

2.3.1 分离链接

分离链接法包括为散列表的每个位置创建一个链表并将元素存储在里面。是解决冲突的最简单的方法，但是除了 HashTable 之外还需要额外的存储空间。

HashTableSeparateChaining 类：

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

put() 方法：

class HashTableSeparateChaining {
  put(key, value) {
    if(key != null && value != null) {
      const position = this.hashCode(key);
      // 值为null则创建链表
      if(this.table[position] == null) {
        this.table[position] = new LinkedList();
      }
      this.table[position].push(new ValuePair(key, value));
      return ture;
    }
    return false;
  }
}

get() 方法：

class HashTableSeparateChaining {
  get(key) {
    const position = this.hashCode();
    const linkedList = this.table[position];
    if(linkedList != null && !linkedList.isEmpty()) {
      let current = linkedList.head;
      while(current != null) {
        if(current.element.key === key) {
          return current.element;
        }
        current = current.next;
      }
    }
    return undefined;
  }
}

remove() 方法：

class HashTableSeparateChaining {
  remove(key) {
    const position = this.hashCode(key);
    const linkedList = this.table[position];
    if(linkedList != null && !linkedList.isEmpty()) {
      let current = linkedList.head;
      while(current != null) {
        if(current.element.key === key) {
          // 通过链表方法删除
          linkedList.remove(current.element);
          // 链表为空时删除
          if(linkedList.isEmpty()) {
            delete this.table[position]
          }
          return true;
        }
        current = current.next;
      }
    }
    return false;
  }
}

2.3.2 线性探测

线性探测不会增加额外的空间，当发生冲突时，会继续按某种规则查找表内非空的位置。比如哈希计算得出的位置 position 有值了，可以继续查找下一位置 position + 1，一直探测，直到找到没有值的位置。

线性探测技术删除元素有两种方法：

1. 软删除法。

当删除元素时，使用一个特殊值（标记）表示键值对被删除了（惰性删除或软删除），而不是真的删除。前期效率很快，但一段时间后，表内被删除的元素很多时，散列表的效率会降低，因为搜索键值会更慢。

2. 移动元素。

检验是否有必要将一个或多个元素移动到之前的位置，这种方法可以避免查找到已删除的无效位置。

class HashTableLinearSearch {
  put(key, value) {
    if(key != null && value != null) {
      const position = this.hashCode(key);
      if(this.table[position] == null) {
        this.table[position] = new ValuePair(key, value);
      } else {
        // 发生冲突，往后找到为空的位置
        let index = position + 1;
        while(this.table[index] != null) {
          index++;
        }
        this.table[index] = new ValuePair(key, value);
      }
      return true;
    }
    return false;
  }

  get(key) {
    const position = this.hashCode(key);
    if(this.table[position] != null) {
      if(this.table[position].key === key) {
        return this.table[position].value;
      } else {
        let index = position + 1;
        while(this.table[index] != null && this.table[index].key !== key) {
          index++;
        }
        if(this.table[index] != null && this.table[index].key === key) {
          return this.table[index].value;
        }
      }
    }
    return undefined;
  }

  remove(key) {
    const position = this.hashCode(key);
    if(this.table[position] != null) {
      if(this.table[position].key === key) {
        delete this.table[position];
        // 删除后要消除副作用，将冲突元素移动到之前的位置
        this.verifyRemoveSideEffect(key, position);
        return true;
      }
      let index = position + 1;
      while(this.table[index] != null && this.table[index].key !== key) {
        index++;
      }
      if(this.table[index] != null && this.table[index].key === key) {
        delete this.table[index];
        this.verifyRemoveSideEffect(key, index);
        return true;
      }
    }
    return false;
  }

  verifyRemoveSideEffect(key, removedPosition) {
    const hash = this.hashCode(key);
    let index = removedPosition + 1;
    while(this.table[index] != null) {
      const posHash = this.hashCode(this.table[index].key);
      if(posHash <= hash || posHash <= removedPosition) {
        this.table[removedPosition] = this.table[index];
        delete this.table[index];
        removedPosition = index;
      }
      index++;
    }
  }
}

2.4 创建更好的哈希函数

更受社区推崇的散列函数 djb2：

function djb2HashCode(key) {
  const tableKey = this.toStrFn(key);
  let hash = 5381;
  for(let i = 0; i < tableKey.length; i++) {
    hash = (hash * 33) + tableKey.charCodeAt(i);
  }
  // 该质数需要比散列表大小更大
  return hash % 1013;
}

3. ES2015 Map类

const map = new Map();
map.set('John', 'John@email.com');

console.log(map.size) // 1
console.log(map.has('John')) // true
console.log(map.get('Jphn')) // 'John@email.com'

• 和自定义的不同，ES2015 中的 Map 的 values() 和 keys() 方法返回一个迭代器，而不是值构成的数组。
• size 属性返回集合中元素个数，而不是 size() 方法。
• 通过 delete() 方法可以删除元素，clear() 方法清空集合，与自定义的集合方法功能一样。

4. ES2015 的 WeakMap 和 WeakSet

Map 和 Set 与弱化版本的区别是：

• WeakSet 和 WeakMap 类没有 keys()、values() 和 entries() 等方法。
• 只能用对象作为键。

说明

使用这两个类主要是为了性能，弱化版本没有强引用的键，使得垃圾回收器可以清除整个入口。