如果我知道需要删除的元素的索引，我可以在恒定时间内从数组中删除元素吗

Question

我正在尝试在 JavaScript 中实现 hashmap 功能，并希望将所有内容保持在恒定的时间内。

问题 1： 在恒定时间（O(1)）内从数组中删除元素，我正在使用数组。

问题 2： 解决冲突问题的最佳方法，以防我们对不同的键使用相同的哈希值。

问题3：创建哈希码的最佳方法。目前我正在使用每个字符的一些 ASCII 值。

代码示例

class myHashMap {
    constructor(size = 0 ){
        if(size){
            this.hashMap = new Array(size).fill(null);
            this.size = size;
        }
            else{
            this.hashMap = new Array();
            this.size = 0;
            }

    }
    hash(key){

// Here hashing can have collision 
//for example: 122 and 212 will have same hash which is not correct
        let CharArray = key.split("");
       return CharArray.reduce((acc,current) => {
            return acc+current.charCodeAt(0);
        },0);
      
    }
    set(key,value)
    {
        this.size++;
        this.hashMap[this.hash(key)] = value;
    }

    get(key){
        return this.hashMap[key];

    }
    has(key){
        return this.hashMap[key];
    }
    remove(key)
    {

        this.size--;
         this.hashMap.splice(this.hash(key),1); 
      // Here I need to remove element in O(1)
    }
}

Answer 1

问题 1：在常数时间内从数组中删除元素 (O(1)) 我是 使用数组。

除非您使用“数组”的某些非标准定义，否则您无法在恒定时间内从数组中删除元素。您可以在恒定时间内将某个项目设置为某个空值。但“数组”的标准用法意味着多个已知大小的项目布置在连续的内存中，以便可以通过指针算术在恒定时间内通过索引访问它们。要从这样的结构中删除元素，这意味着数组实际上会变小，您至少需要在要删除的项目之后复制数组中的项目，这是一个 O(n) 操作。

问题 2：如果哈希值相同，解决冲突问题的最佳方法 对于不同的键。

没有最好的方法。这个问题有多种解决方案，它们在时间效率、空间、实施难易度和其他考虑因素方面做出了不同的权衡。两种最常见的大类解决方案是（1）使用“桶”结构，本质上使哈希表成为另一种容器的大部分为空实例的数组——历史上链表很常见——以及（2）让该表是平坦的，并通过“开放寻址”处理冲突，这意味着探测，直到找到从哈希索引找到的槽开始的空槽。上述中，一般来说（1）更容易实现。

问题 3：创建哈希码的最佳方法。目前我正在使用一些 每个字符的 ASCII 值。

这是一个很大的主题，但是，是的，您需要使用字符串中字符的数值，问题是您如何处理这些值。看看 C++ 中

boost::hash_combine

的实现示例，其中 StackOverflow 上有很多参考文献。

Answer 2

如果数组中项目的顺序不重要，您可以通过将目标元素与数组中的最后一个元素交换，然后使用

pop()

方法删除最后一个元素，在恒定时间内删除一个元素。

const array = [1, 2, 3, 4, 5];
const indexToRemove = 1;

// [1, 5, 3, 4, 1]
[array[indexToRemove], array[array.length-1]] = [array[array.length-1], array[indexToRemove]];

array.pop(); // [1, 5, 3, 4]