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

作者 : IT 大叔 本文共5044个字,预计阅读时间需要13分钟 发布时间: 2020-09-9

数据结构教程系列

数据结构教程系列01:JavaScript数组教程

数据结构教程系列02:使用Java深入研究树

数据结构教程系列03:如何在Java中使用链接列表

数据结构教程系列04:在JavaScript中引入图

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

数据结构教程系列06:如何在Java中使用堆栈和队列

在计算机编程中,数据结构用于组织数据并将算法(或命令)应用于代码。对数据结构和算法有很好的了解对于有效地解决问题非常有用,并且对于破解编码面试至关重要。

通过查看本文中的哈希表数据结构,我们将继续我们的数据结构系列。我们将学习它们的含义,它们的用途以及如何在JavaScript中实现它们。

今天,我们将介绍:

  • 什么是哈希表?
  • 什么是哈希函数
  • 哈希表冲突
  • 如何实现哈希表
  • 整理和面试问题

什么是哈希表?

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

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

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

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

哈希表由两部分组成:

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

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

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

哈希表的使用

哈希表可在恒定时间内访问元素,因此强烈建议将哈希表用于优先考虑搜索和数据检索操作的算法。散列是大量数据的理想选择,因为它们花费固定的时间来执行插入,删除和搜索。

就时间复杂度而言,运算为 0(1)。平均而言,哈希表查找比其他表查找数据结构更有效。哈希表的一些常见用法是:

  • 数据库索引
  • 快取
  • 独特的数据表示
  • 在未排序的数组中查找
  • 使用二进制搜索在排序数组中查找

哈希表与树

散列和树执行相似的工作,但是程序中的各种因素决定了何时使用另一个。

当应用程序需要按特定顺序对数据进行排序时,树更有用。哈希表是键值对组织,因此是随机排序数据的明智选择。

哈希表可以在恒定时间内执行,而树通常在 O(log n)。在最坏的情况下,哈希表的性能可能低至上)。但是,AVL树将保持O(log n) 在最坏的情况下。

一个有效的哈希表需要一个哈希函数来分发密钥。树比较简单,因为它仅在需要时才访问额外的空间,并且不需要哈希函数。

数据结构教程系列05:在JavaScript中实现哈希表插图(2)

什么是哈希函数?

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

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

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::2

常用哈希函数

有许多种具有不同用途的哈希函数。让我们看一下现代编程中使用的一些最常见的哈希函数。

算术模块化:在这种方法中,我们采用键的列表/数组大小为模块化:index=key MOD tableSize。因此,index将始终停留在0和之间tableSize - 1

截断:在这里,我们选择键的一部分作为索引而不是整个键。我们可以将mod函数用于此操作,尽管它不必基于数组大小

折叠:此方法涉及将密钥分成小块,并在每个块上应用不同的算术策略。

哈希表冲突

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

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

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

数据结构教程系列05:在JavaScript中实现哈希表插图(4)

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

数据结构教程系列05:在JavaScript中实现哈希表插图(6)

  1. 调整数组或列表的大小:减少冲突的另一种方法是调整列表或数组的大小。我们可以设置一个阈值,一旦超过阈值,我们就可以创建一个新表,该表的大小是原始表的两倍。然后,我们要做的就是复制上表中的元素。调整列表或数组的大小可显着减少冲突,但函数本身的成本很高。因此,我们需要谨慎设置阈值。典型的约定是将阈值设置为0.6,这意味着当表的60%被填充时,需要进行调整大小操作。
  2. 双重哈希:在双重哈希中,有两个哈希函数。第二个哈希函数用于在第一个函数引起冲突的情况下提供偏移值。双散列可以比线性探测方法更快地找到下一个空闲时隙。这对于哈希表较小的应用程序很有用。以下函数是双重哈希的示例:
(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 哪里 ñ 是它可以容纳的键的数量,并且  是每个存储桶包含的插槽数。

数据结构教程系列05:在JavaScript中实现哈希表插图(8)

我们将从建立一个简单的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;
}

好了!下一步将是实现搜索,插入和删除的操作。

整理和面试问题

祝贺您完成本文的结尾!我希望这是您继续学习哈希表和数据结构一般知识的良好起点。

接下来要学习的是哈希表的常见访谈问题,因此您可以了解如何实现操作和映射哈希表。其中一些包括:

  • 实现插入,删除和搜索
  • 检查数组是否不相交
  • 在数组中查找对称对
  • 找到两对 a + b = c + d
  • 查找两个加起来等于“值”的数字
  • 使用哈希表从链接列表中删除重复项
  • 如何将新值插入已占用的哈希键
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 数据结构教程系列05:在JavaScript中实现哈希表

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论