数据结构教程系列05：在JavaScript中实现哈希表

什么是哈希表？

甲哈希表（通常被称为散列映射）是一种数据结构，其将键映射到的值。哈希表有效地结合了lookup，insert和delete操作。密钥将发送到对其执行算术运算的哈希函数。结果（称为哈希值或哈希）是键值对的索引。

可以将其视为数据块上的签名，该签名使我们能够在恒定时间内进行搜索。哈希表的操作就像字典一样，我们可以将其映射为从哈希表获取所需数据。

这种数据结构已广泛用于多种计算机软件中，尤其是用于关联数组，数据库索引，高速缓存和集。通常，此操作为给定的键返回相同的哈希值。

哈希表的性能取决于三个基本因素：哈希函数，哈希表的大小和冲突处理方法。

哈希表由两部分组成：

• 对象：具有表存储数据的对象。该数组保存表中的所有键值条目。阵列的大小应根据预期的数据量进行设置。
• 哈希函数（或映射函数）：该函数确定键值对的索引。它应该是单向函数，并且为每个键产生不同的哈希值。

注意：在JavaScript中，哈希表通常使用数组来实现，因为它们可以在恒定时间内访问元素。

什么是哈希函数？

甲散列函数是每当键被查找，它接受一个项的键作为输入，特定的索引分配给该键并返回索引的方法或函数。对于给定的键，此操作通常返回相同的哈希值。一个好的哈希函数应该有效地计算和均匀分配密钥。

哈希函数有助于将键的范围限制为数组的边界，因此我们需要一个将大键转换为较小键的函数。这是哈希函数的工作。

哈希表冲突

有时，哈希函数可以为多个键生成相同的索引。这种情况称为哈希冲突。冲突是一个问题，因为哈希表中的每个插槽都应该存储一个元素。

哈希冲突通常使用四种常见策略进行处理。

1. 线性探测：线性探测通过跳过已经填充的索引来工作。可以通过将偏移值添加到已计算的索引来实现。如果该索引也已填充，请再次添加它，依此类推。使用这种策略的一个缺点是，如果您没有明智地选择偏移量，则可以跳回到开始的位置，错过阵列中的许多可能位置。

2. 链接：在链接策略中，哈希表的每个插槽都包含一个指向另一个数据结构（例如链表或树）的指针。该索引处的每个条目都将插入到该索引的链接列表中。如您所见，链接使我们能够在相同的时间对同一索引的多个键值对进行哈希处理（在链表的开头插入）。这种策略大大提高了性能，但是在空间方面却很昂贵。

3. 调整数组或列表的大小：减少冲突的另一种方法是调整列表或数组的大小。我们可以设置一个阈值，一旦超过阈值，我们就可以创建一个新表，该表的大小是原始表的两倍。然后，我们要做的就是复制上表中的元素。调整列表或数组的大小可显着减少冲突，但函数本身的成本很高。因此，我们需要谨慎设置阈值。典型的约定是将阈值设置为0.6，这意味着当表的60％被填充时，需要进行调整大小操作。
4. 双重哈希：在双重哈希中，有两个哈希函数。第二个哈希函数用于在第一个函数引起冲突的情况下提供偏移值。双散列可以比线性探测方法更快地找到下一个空闲时隙。这对于哈希表较小的应用程序很有用。以下函数是双重哈希的示例：

(firstHash(key) + i * secondHash(key)) % tableSize 

如何实现哈希表

为了使用JavaScript实现哈希表，我们将做三件事：创建哈希表类，添加哈希函数，以及实现向表中添加键/值对的方法。

首先，让我们创建HashTable类。

class HashTable {
 constructor() {
   this.values = {};
   this.length =  0;
   this.size =  0;
 }
}

构造函数包含一个对象，我们将在其中存储值，值的长度和哈希表的整个大小：这意味着哈希表包含多少个存储桶。我们将把数据存储在这些存储桶中。

接下来，我们必须实现一个简单的哈希函数。

calculateHash(key) {
 return key.toString().length % this.size;
}

此函数采用提供的键，并返回使用算术模量计算得出的哈希值。

最后，我们需要一种方法来插入键/值对。看一下代码，看看它的作用：

add(key, value) {
  const hash = this.calculateHash(key);
  if (!this.values.hasOwnProperty(hash)) {
     this.values[hash] = {};
  }
  if (!this.values[hash].hasOwnProperty(key)) {
     this.length++;
  }
  this.values[hash][key] = value;
}

我们在这里要做的第一件事是计算密钥的哈希值。如果哈希还不存在，则将其保存到对象存储中。我们执行的下一个检查是在哈希上。如果没有保存键，则保存键和值，并增加哈希表的大小。

在哈希表中搜索非常快。与数组不同，在数组中我们必须遍历所有元素直到找到所需的项目，而哈希表仅获取索引。我将在下面为我们的哈希表实现添加完整的代码。

class HashTable {
  constructor() {
    this.values = {};
    this.length =  0;
    this.size =  0;
  }

  calculateHash(key) {
    return key.toString().length % this.size;
  }

  add(key, value) {
    const hash = this.calculateHash(key);
    If (!this.values.hasOwnProperty(hash)) {
      this.values[hash] = {};
    }
    if (!this.values[hash].hasOwnProperty(key)) {
       this.length++;
    }
    this.values[hash][key] = value;
  }

  search(key) {
     const hash = this.calculateHash(key);
     if (this.values.hasOwnProperty(hash) && this.values[hash].hasOwnProperty(key)) {
       return this.values[hash][key];
     } else {
       return null;
     }
  }
}

//create object of type hash table
const ht = new HashTable();
//add data to the hash table ht
ht.add("Canada", "300");
ht.add("Germany", "100");
ht.add("Italy", "50");

//search
console.log(ht.search("Italy"));

这就完成了我们的基本JavaScript哈希表实现。请注意，我们使用Object来表示哈希表。JavaScript中的对象实际上是使用哈希表本身实现的！许多编程语言还以内置关联数组或标准库模块的形式提供对哈希表的支持。

桶链实现

现在，让我们看看另一个使用存储桶链接的实现。链接策略以及调整大小操作可避免表中发生冲突。

具有相同哈希键的所有元素都将存储在该索引处的数组中。在数据结构中，这些阵列称为存储桶。哈希表的大小设置为$n*m$ 哪里 $ñ$ 是它可以容纳的键的数量，并且 $米$ 是每个存储桶包含的插槽数。

我们将从建立一个简单的HashEntry类开始。如前所述，典型的哈希条目由三个数据成员组成：键，值和对新条目的引用。

class HashEntry{
    constructor(key, data){
        this.key = key;
        // data to be stored
        this.value = data;
        // reference to new entry
        this.next = null;
    }
}
        
let entry = new HashEntry(3, "Educative");
console.log (String(entry.key) + ", " + entry.value);

现在，我们将创建HashTable一个HashEntry对象集合的类。我们将跟踪表中的插槽数和哈希表的当前大小。当我们需要调整表格大小时，这些变量将派上用场。

class HashTable{
  //Constructor
  constructor(){
    //Size of the HashTable
    this.slots = 10;
    //Current entries in the table
    //Used while resizing the table when half of the table gets filled
    this.size = 0;
    //Array of HashEntry objects (by deafult all None)
    this.bucket = [];
    for (var i=0; i<this.slots; i++){
      this.bucket[i]=null;
    }
  }
  //Helper Functions  
  get_size(){
    return this.size;
  }
  isEmpty(){
    return this.get_size() == 0;
  }
}
  
let ht = new HashTable();
console.log(ht.isEmpty());

我们需要的最后一件事是哈希函数。在上一课中，我们尝试了一些不同的方法。对于我们的实现，我们将简单地将键与哈希表的总大小（插槽）进行模块化。

//Hash Function
getIndex(key){
	let index = key % this.slots;
	return index;
}