javascript实现的HashMap类代码

JavaScript实现的HashMap类代码

HashMap是一种非常常用的数据结构，用于提高键值对查找的效率。JavaScript作为一门弱类型语言，没有原生的HashMap，但我们可以用Object对象来实现一个简单的HashMap类。

实现细节

• 使用Object对象存储键值对，遍历时需要注意使用hasOwnProperty方法判断是否为对象本身的属性
• 使用JavaScript中的哈希函数实现key到index的映射，尽可能避免index冲突以保证查找效率
• 实现put、remove、get、size四个基本方法
• 使用ES6语法中的Symbol数据类型实现HashMap类的迭代器

HashMap类代码

下面是一个简单的HashMap类的实现：

class HashMap {
  constructor() {
    this._items = Object.create(null);
    this._count = 0;
    this._size = 0;
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this._size;
  }

  put(key, value) {
    const hash = this._hash(key);
    if (!this._items[hash]) {
      this._items[hash] = Object.create(null);
    }

    if (!this._items[hash][key]) {
      this._count++;
    }

    this._items[hash][key] = value;
  }

  remove(key) {
    const hash = this._hash(key);
    if (this._items[hash] && this._items[hash][key]) {
      delete this._items[hash][key];
      this._count--;
    }
  }

  get(key) {
    const hash = this._hash(key);
    if (this._items[hash] && this._items[hash][key]) {
      return this._items[hash][key];
    }
    return null;
  }

  size() {
    return this._count;
  }

  *[Symbol.iterator]() {
    const keys = Object.keys(this._items);
    for (let i = 0; i < keys.length; i++) {
      const hash = this._items[keys[i]];
      for (let key in hash) {
        if (hash.hasOwnProperty(key)) {
          yield hash[key];
        }
      }
    }
  }
}

示例说明

1. 插入和查找

const map = new HashMap();
map.put('a', 1);
map.put('b', 2);
map.put('c', 3);

console.log(map.get('a'));  // 1
console.log(map.get('b'));  // 2
console.log(map.get('c'));  // 3
console.log(map.get('d'));  // null

这里插入了三组键值对'a': 1, 'b': 2, 'c': 3，然后进行了查找。map.get('a')返回值为1，map.get('d')返回值为null，验证了HashMap的正确性。

1. 迭代

const map = new HashMap();
map.put('a', 1);
map.put('b', 2);
map.put('c', 3);

for (let item of map) {
  console.log(item);
}

这里插入三组键值对'a': 1, 'b': 2, 'c': 3，然后使用for...of循环输出HashMap中的所有值。输出结果为1, 2, 3，表明HashMap的迭代功能也可用。