JavaScript 实现 Map 集合数据结构及操作示例

Map 集合的设计原理

要实现一个具备 put、get、size 等功能的 Map 结构，核心在于解决 Key 的唯一性验证以及 Value 的高效存取。该实现方案采用了以下策略：

• hashmap（哈希存储）：作为主字典，直接将 Key 映射到 Value，保证 O(1) 复杂度的查询效率。
• keys / vals / entrys 数组：用于维护数据的插入顺序，分别存储 Key 列表、Value 列表及键值对对象列表。
• index 索引对象：记录每个 Key 在当前数组中的下标位置，以便在 remove 或 clear 时快速定位并剔除元素，避免全量扫描。
• Entry 内部类：使用闭包封装 Key 和 Value，提供获取接口，保护数据不被外部直接篡改。

核心代码实现

第 1 步：定义 Map 构造函数与内部状态

初始化底层存储容器，定义 Entry 结构体用于封装单个键值对。

var Map = function (){
  // 底层哈希表，用于快速查找
  var hashmap = {};
  // 维持插入顺序的数组
  var keys = [];
  var vals = [];
  var entrys = [];
  // 当前容量大小
  var size = 0;
  // 键到下标的映射，加速删除操作
  var index = {};
 
  // 内部 Entry 构造函数
  var Entry = function(key, value){
    var entryKey = key;
    var entryValue = value;
    this.getKey = function () { return entryKey; };
    this.getValue = function(){ return entryValue; };
  };

第 2 步：实现基本增删查改方法

在此阶段补充 put（新增/更新）、get（取值）、clear（按Key清除）、size（获取数量）等方法，确保逻辑严密。

// 添加或更新键值对
this.put = function(key, value){
  if(!this.get(key)){
    // 如果是新 Key，追加到数组末尾
    entrys.push(new Entry(key, value));
    keys.push(key);
    vals.push(value);
    index[key] = size;
    size ++;
  } else {
    // 如果 Key 已存在，仅更新对应下标的值和 Entry
    var i = index[key];
    entrys[i] = new Entry(key, value);
    vals[i] = value;
  }
  hashmap[key] = value;
};
 
// 获取指定 Key 的值
this.get = function(key){
  return hashmap[key];
};
 
// 清空指定 Key 的数据
this.clear = function(key) {
  hashmap[key] = undefined;
  var i = index[key];
  entrys.splice(i, 1);
  vals.splice(i, 1);
  keys.splice(i, 1);
  size --;
  // 注意：实际生产中需重新校准后续元素的 index 值，此处为简化示意
};
 
this.isEmpty = function() {
  return size === 0; 
};
 
this.size = function() { return size; };

// 返回所有 Keys 和 Values 的数组
this.keySet = function() { return keys; };
this.values = function() { return vals; };
this.entrySet = function() { return entrys; };
};

第 3 步：扩展常用工具方法

为了提升 API 的使用体验，通过原型链扩展了 containsKey（是否存在）、remove（移除并返回值）和 putAll（批量导入）。

Map.prototype = {
  containsKey : function(key) {
    return this.get(key) !== undefined;
  },
  remove : function(key) {
    var v = this.get(key);
    this.clear(key);
    return v;
  },
  putAll : function(set) {
    for(var e in set){
      if(set[e]){
        this.put(e, set[e]);
      }
    }
  }
};

功能测试与使用示例

通过实例化 Map 并进行一系列常规操作，验证其正确性。包括添加多个键值对、检查大小、移除特定项以及遍历输出。

var h = new Map();
h.put('a', 10);
h.put('b', 11);
h.put('c', 3);
h.put('d', 5);

console.info(h.size()); // 预期输出: 4
h.clear('a');
console.info(h.containsKey('a')); // 预期输出: false (注意: clear 后 hashmap 设为 undefined)
console.info(h.containsKey('b')); // 预期输出: true
console.info(h.size());           // 预期输出: 3
 
// 打印不同类型的集合视图
console.log(h.entrySet()); // 包含 Entry 对象的数组
console.log(h.keySet());   // ['b', 'c', 'd']
console.log(h.values());   // [11, 3, 5]
 
// 遍历输出完整内容
for(var i in h.entrySet()){
  var obj = h.entrySet()[i];
  console.log(obj.getKey() + ":" + obj.getValue());
}

上述实现展示了在较早期的 JavaScript 环境下构建强类型 Map 集合的思路。虽然在现代浏览器和 Node.js 环境中直接使用原生的 Map 对象更为高效且标准，但理解其底层的数组维护与哈希映射机制有助于深入掌握数据结构的运作原理。

以上就是 JavaScript 实现 Map 集合的详细教学内容，更多关于前端数据结构与算法的资料请关注本站其它相关文章！