Javascript数据结构之字典和散列表

作者: tww844475003 分类: 前端开发 发布时间: 2022-02-16 22:27

字典

集合表示一组不重复的元素，字典和集合相似。但存储方式不同，字典是以【键，值】的形式存储元素，集合是以【值，值】的形式存储元素。

  • set(key, value)：向字典中添加新元素。如果 Key 已经存在，那么存在的 value 会被新的值覆盖
  • hasKey(key)：如果某个键值存在于该字典中，返回 true，否则返回 false
  • get(key, value)：通过以键值作为参数查找特定的数值并返回
  • remove(key)：通过使用键值作为参数来从字典中移除键值对应的数据值
  • clear()：删除该字典中的所有值
  • size()：返回字典所包含值的数量
  • isEmpty()：在 size 等于零的时候返回 true，否则返回 false
  • keys()：将字典所包含的所有键名以数组形式返回
  • values()：将字典所包含的所有数值以数组形式返回
  • keyValues()：将字典中所有【键，值】对返回
  • forEach(callbackFn)：迭代字典中所有键值对
  • toString()：返回字典数值的字符串
function defaultToString(item) {
  if (item === null) {
    return 'NULL';
  } if (item === undefined) {
    return 'UNDEFINED';
  } if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  }
  return item.toString();
}

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }

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

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

  // 向字典中添加新元素
  set(key, value) {
    if (key != null && value != null) {
      const tableKey = this.toStrFn(key);
      this.table[tableKey] = new ValuePair(key, value);
      return true;
    }
    return false;
  }

  // 检查键值是否存在
  hasKey(key) {
    return this.table[this.toStrFn(key)] != null;
  }

  // 根据键值获取数值
  get(key) {
    const valuePair = this.table[this.toStrFn(key)];
    return valuePair == null ? undefined : valuePair.value;
  }

  // 根据键值移除数值
  remove(key) {
    if (this.hasKey(key)) {
      delete this.table[this.toStrFn(key)];
      return true;
    }
    return false;
  }

  // 将数值以数组形式返回
  values() {
    return this.keyValues().map(valuePair => valuePair.value);
  }

  // 将键值以数组形式返回
  keys() {
    return this.keyValues().map(valuePair => valuePair.key);
  }

  // 返回键值、数值
  keyValues() {
    return Object.values(this.table);
  }

  // 迭代字典中所有键值对
  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;
      }
    }
  }

  // 是否空
  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;
  }
}

// 使用
const dictionary = new Dictionary();
dictionary.set('zhangsan', 'zhangsan@qq.com');
dictionary.set('lishi', 'lishi@qq.com');
dictionary.set('wangwu', 'wangwu@qq.com');
dictionary.set('zhaoliu', 'zhaoliu@qq.com');
console.log(dictionary.hasKey('lishi')); // true
console.log(dictionary.size()); // 4
console.log(dictionary.keys()); // [ 'zhangsan', 'lishi', 'wangwu', 'zhaoliu' ]
console.log(dictionary.values()); // [ 'zhangsan@qq.com', 'lishi@qq.com', 'wangwu@qq.com', 'zhaoliu@qq.com' ]
console.log(dictionary.get('zhangsan')); // zhangsan@qq.com
dictionary.remove('zhangsan');
console.log(dictionary.keys()); // [ 'zhangsan', 'wangwu', 'zhaoliu' ]
console.log(dictionary.values()); // [ 'zhangsan@qq.com', 'wangwu@qq.com', 'zhaoliu@qq.com' ]
console.log(dictionary.get('zhangsan')); // undefined
dictionary.forEach((k, v) => {
  console.log('forEach', `key：${k}，value：${v}`);
})
// forEach key：lishi，value：lishi@qq.com
// forEach key：wangwu，value：wangwu@qq.com
// forEach key：zhaoliu，value：zhaoliu@qq.com

散列表

散列算法：尽可能快地在数据结构中找到一个值

  • put(key, value)：向散列表增加一个新的项
  • remove(key)：根据键值从散列表中移除值
  • get(key)：返回根据键值检索到的特定的值
function defaultToString(item) {
  if (item === null) {
    return 'NULL';
  } if (item === undefined) {
    return 'UNDEFINED';
  } if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  }
  return item.toString();
}

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }

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

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

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

  // 向字典中添加新元素
  put(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key);
      this.table[position] = new ValuePair(key, value);
      return true;
    }
    return false;
  }

  // 根据键值获取数值
  get(key) {
    const valuePair = this.table[this.hashCode(key)];
    return valuePair == null ? undefined : valuePair.value;
  }

  // 根据键值移除数值
  remove(key) {
    const hash = this.hashCode(key);
    const valuePair = this.table[hash];
    if (valuePair != null) {
      delete this.table[hash];
      return true;
    }
    return false;
  }

  getTable() {
    return this.table;
  }

  // 是否空
  isEmpty() {
    return this.size() === 0;
  }

  // 返回键值大小
  size() {
    return Object.keys(this.table).length;
  }

  // 清空字典
  clear() {
    this.table = {}
  }

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

// 使用
const hash = new HashTable();
hash.put('zhangsan', 'zhangsan@qq.com');
hash.put('lishi', 'lishi@qq.com');
hash.put('wangwu', 'wangwu@qq.com');
hash.put('zhaoliu', 'zhaoliu@qq.com');
console.log(hash.hashCode('zhangsan') + '- zhangsan');
console.log(hash.hashCode('lishi') + '- lishi');
console.log(hash.hashCode('wangwu') + '- wangwu');
console.log(hash.hashCode('zhaoliu') + '- zhaoliu');
hash.remove('zhangsan');
console.log(hash.get('zhangsan')); // undefined
console.log(hash.toString()); // {19 => [#lishi: lishi@qq.com]},{24 => [#zhaoliu: zhaoliu@qq.com]},{36 => [#wangwu: wangwu@qq.com]}
console.log(hash.getTable());
// {
//   '19': ValuePair { key: 'lishi', value: 'lishi@qq.com' },
//   '24': ValuePair { key: 'zhaoliu', value: 'zhaoliu@qq.com' },
//   '36': ValuePair { key: 'wangwu', value: 'wangwu@qq.com' }
// }

有时候，一些键会有相同的散列值如：

5 - Jonathan
5 - Jamie
5 - Sue
5 - Aethelwulf

hashCode 不同值，并没有返回唯一的散列键值，这样保存数据显然会丢失一部分数据。处理这种冲突的有以下几种方法：

  • 分离链接
  • 线性探查
  • 双散列法

分离链接

分离链接法包括为散列表每一个位置创建一个链表并将元素存储在里面。

put 方法验证加入新元素的位置是否已经被占据，如果第一次加入元素，new LinkedList()，否则 push(new ValuePair(key, value))

线性探查

线性探查是将元素直接存储到表中，而不是在单独的数据结构中。

当向表中某个位置添加一个新元素的时候，如果索引为 position 的位置已经被占据了，就尝试 position + 1 的位置。如果 position + 1 的位置也被占据了，就尝试 position + 2，以此类推。

双散列法

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;
}
288 - Jonathan
962 - Jamie
502 - Sue
149 - Aethelwulf
打赏微海报分享
前端开发那点事
微信公众号搜索“前端开发那点事”

如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

更多阅读
标签云
@vueuse/core chrome css css3 element-ui es6 flask gogocode HTTP HTTP通信 javascript jest jquery js node node.js npm object python react regex rollup selenium TCP连接 tree typescript vite vue vue-cli vue-codemirror vue.js vue3 vue3 hooks vue3.js vueuse webpack webpack5 web前端 web前端开发 前端开发 前端开发那点事 多态 数据结构 设计模式 面向对象编程