JavaScript 数据结构之散列表的创建(2)

下面是详细讲解“JavaScript 数据结构之散列表的创建(2)”的完整攻略。

散列表（哈希表）

散列表是一种数据结构，使用哈希函数将键映射到索引。散列表可以在常量时间 O(1) 中进行插入、删除和查找操作，但也具有碰撞冲突问题。

碰撞冲突问题

在散列表中，当两个不同的键通过哈希函数映射到了同一个索引位置时，就会发生碰撞冲突问题。解决碰撞冲突问题的方法有很多，常用的有“链地址法”和“线性探测法”。

链地址法解决碰撞冲突

链地址法也就是“拉链法”，即将同一个索引位置上的所有键都放入到一个链表中。当冲突发生时，只需要将当前键添加到对应索引位置上的链表中即可。

下面是一个使用链地址法的散列表实现示例：

class HashTable {
  constructor() {
    this.table = [];
  }

  // 哈希函数
  hash(data) {
    let total = 0;
    for (let i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    return total % this.table.length;
  }

  // 插入操作
  insert(key, value) {
    let index = this.hash(key);

    if (!this.table[index]) {
      // 该索引位置不存在键值对，则创建一个链表存储键值对
      this.table[index] = [];
    }

    // 遍历链表查找指定键
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i].key === key) {
        // 键已存在，则更新值
        this.table[index][i].value = value;
        return;
      }
    }

    // 键不存在，则添加新的键值对
    this.table[index].push({ key, value });
  }

  // 获取操作
  get(key) {
    let index = this.hash(key);

    if (!this.table[index]) {
      return undefined;
    }

    // 遍历链表查找指定键
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i].key === key) {
        // 键存在，则返回对应的值
        return this.table[index][i].value;
      }
    }

    // 键不存在，则返回 undefined
    return undefined;
  }

  // 删除操作
  remove(key) {
    let index = this.hash(key);

    if (!this.table[index]) {
      return;
    }

    // 遍历链表查找指定键
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i].key === key) {
        // 键存在，则从链表中删除该键值对
        this.table[index].splice(i, 1);
        return;
      }
    }
  }
}

// 测试
let hashTable = new HashTable();
hashTable.insert('name', 'Tom');
hashTable.insert('age', 18);
console.log(hashTable.get('name')); // Tom
console.log(hashTable.get('age')); // 18
hashTable.remove('age');
console.log(hashTable.get('age')); // undefined

上面的代码中，我们使用了一个对象数组来存储在散列表中的键值对，如果发生冲突则将键值对存储在同一个索引位置上的对象数组中。

线性探测法解决碰撞冲突

线性探测法也就是“开放地址法”，当发生碰撞时，它会逐一探测下一个空闲位置，直到找到可用的位置为止。

下面是一个使用线性探测法的散列表实现示例：

class HashTable {
  constructor() {
    this.table = [];
  }

  // 哈希函数
  hash(data) {
    let total = 0;
    for (let i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    return total % this.table.length;
  }

  // 插入操作
  insert(key, value) {
    let index = this.hash(key);

    if (this.table[index] === undefined) {
      // 该索引位置为空，则直接存储键值对
      this.table[index] = { key, value };
    } else {
      // 该索引位置不为空，则线性探测下一个空闲位置
      let i = 1;
      while (this.table[index + i] !== undefined) {
        i++;
      }
      this.table[index + i] = { key, value };
    }
  }

  // 获取操作
  get(key) {
    let index = this.hash(key);

    // 遍历散列表查找指定键
    for (let i = 0; i < this.table.length; i++) {
      let pos = (index + i) % this.table.length;
      if (this.table[pos] && this.table[pos].key === key) {
        // 键存在，则返回对应的值
        return this.table[pos].value;
      }
    }

    // 键不存在，则返回 undefined
    return undefined;
  }

  // 删除操作
  remove(key) {
    let index = this.hash(key);

    // 遍历散列表查找指定键
    for (let i = 0; i < this.table.length; i++) {
      let pos = (index + i) % this.table.length;
      if (this.table[pos] && this.table[pos].key === key) {
        // 键存在，则将该位置的值置为 undefined
        this.table[pos] = undefined;
        return;
      }
    }
  }
}

// 测试
let hashTable = new HashTable();
hashTable.insert('name', 'Tom');
hashTable.insert('age', 18);
console.log(hashTable.get('name')); // Tom
console.log(hashTable.get('age')); // 18
hashTable.remove('age');
console.log(hashTable.get('age')); // undefined

上面的代码中，我们采用了一种简单的线性探测方法来解决碰撞冲突，如果发生冲突则线性探测下一个空闲位置存储键值对。

至此，“JavaScript 数据结构之散列表的创建(2)”完整攻略讲解完毕，内容详尽、示例丰富，希望能够帮助到你。