2021/03/14 每日一题 设计哈希映射

LeetCode上设计哈希映射，简单难度，估计本月都是数据结构方面的内容

不能用内建的哈希集合，手动实现put、get、remove增查删功能，和昨天的代码不同，不仅需要记录元素还需要记录元素对应的值

首先直接想到是用数组来做

var MyHashMap = function() {
    this.arr = []
};

MyHashMap.prototype.put = function(key, value) {
    this.remove(key)
    this.arr.push([key,value])
    
};

MyHashMap.prototype.get = function(key) {
    for(let i = 0;i<this.arr.length;i++){
        // 获取对应元素
        if(this.arr[i][0] == key){
            return this.arr[i][1]
        }
    }
    // 不存在返回-1
    return -1
};

MyHashMap.prototype.remove = function(key) {
    for(let i = 0;i<this.arr.length;i++){
        // 删除对应元素
        if(this.arr[i][0] == key){
            this.arr.splice(i,1)
        }
    }
};

下面是官方题解提供的拉链法
拉链法的要点在于，用一个数组保存另一个数组，第一个数组是内存储的是对应hash值的数组，第二个数组就保存对应hash的数据，其实可以视为一个二维数组的形式

var MyHashMap = function() {
    // 随便设置一个数
    this.base = 1000;
    // 这里创建的就是第一层数组
    this.data = new Array(this.base).fill(0).map(i => new Array());
};

MyHashMap.prototype.put = function(key, value) {
    // 计算hash
    let hash = key % this.base;
    for(let i of this.data[hash]){
        if(i[0] === key) return i[1] = value;
    }
    this.data[hash].push([key, value]);
};

MyHashMap.prototype.get = function(key) {
    let hash = key % this.base;
    for(let i of this.data[hash]){
        if(i[0] === key) return i[1];
    }
    return -1;
};

MyHashMap.prototype.remove = function(key) {
    let hash = key % this.base;
    for(let i of this.data[hash]){
        if(i[0] === key) {
            let index = this.data[hash].indexOf(i);
            this.data[hash].splice(index, 1);
        }
    }
};