数据结构–哈希表

时间:2021-1-18 作者:admin

什么是哈希表

哈希表(HashTable):是根据关键码值(Key)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。

哈希表通常基于数组实现,相比于数组它存在更多的优势:

  • 在哈希表中 插入 删除 查找 非常快速,无论数据量大小,插入删除接近 O(1)的时间复杂度。
  • 哈希表的的速度比树还要快,可以瞬间查到对应的数据
  • 编码比较简单

不足之处:

  • 哈希表中的数据没有顺序,不能以一种固定的方式遍历数据
  • 通常情况下,key 不允许重复,相同的 key 不能保存不同的 value

哈希表的结构其实就是数组,哈希表的特点就是对下标值进行哈希化的转化,然后对值进行保存,这个转化就要借助哈希函数。通过该哈希函数获取 HashCode,也就是下标值。

所以要想实现哈希表,必须得实现哈希函数。

实现哈希函数

哈希表的优势在于它的速度,所以哈希函数不能采用消耗性能较高的复杂算法。提高速度的一个方法是在哈希函数中尽量减少乘法和除法。

性能高的哈希函数应具备以下两个优点:

  • 快速的计算;
  • 均匀的分布;

这里涉及到了霍纳法则:在中国霍纳法则也叫做秦久韶算法。

/** * @param {string} str 传递进来的想要转变为下标的字符串 * @param {number} [limit=7] 符合数组最大的一个长度值 */function hashFn(str, limit = 7) {  // 创建一个质数的常量  const PRIME = 31;  // 创建存放哈希数的变量  let hashCode = 0;  // 使用霍纳法则计算hashCode  for (const item of str) {    hashCode = PRIME * hashCode + item.charCodeAt();  }  // 对hashCode取余并返回。  return hashCode % limit;}

链地址法

本篇文章采用链地址发实现哈希表。

如下图所示,我们将每一个数字都对 10 进行取余操作,则余数的范围 0~9 作为数组的下标值。并且,数组每一个下标值对应的位置存储的不再是一个数字了,而是存储由经过取余操作后得到相同余数的数字组成的数组或链表。

这样可以根据下标值获取到整个数组或链表,之后继续在数组或链表中查找就可以了。而且,产生冲突的元素一般不会太多。

总结:链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据,而是一条链条,这条链条常使用的数据结构为数组或链表,两种数据结构查找的效率相当(因为链条的元素一般不会太多)。

哈希表常见的操作

  • put(key,value) 插入或修改操作
  • get(key) 获取哈希表中特定位置的元素
  • remove(key) 删除哈希表中特定的元素
  • isEmpty() 判断哈希表是否为空
  • size() 返回哈希表的长度
  • resize() 对哈希表进行扩容或压缩

ES6 实现哈希表的封装

实现哈希表数据的结构如下图:

  • isPrime(number) 判断数字是否为质数
/** * * 判断是不是数字 * @param {*} number * @returns */function isPrime(number) {  if (number <= 1 || number === 4) return false;  const temp = Math.ceil(Math.sqrt(number));  for (let i = 2; i < temp; i++) {    if (number % i === 0) {      return false;    }  }  return true;}
  • getPrime(number) 获取质数
getPrime(number) {    while (!isPrime(number)) {      number++;    }    return number;  }
  • 哈希表结构的封装
class HashTable {  constructor() {    this.storage = []; // 存储哈希表的数据    this.count = 0; // 当前存放元素的个数    this.limit = 7; // 取余的质数,和hashFn的第二个参数一个意思    // 装填因子(已有个数/总个数)    this.loadFactor = 0.75;    this.minLoadFactor = 0.25;  }}
  • put(key,value) 插入或修改操作
// put(key,value) 插入或修改操作  // 实现思路  // 首先,根据 key 获取索引值 index,目的为将数据插入到 storage 的对应位置;  // 然后,根据索引值取出 bucket,如果 bucket 不存在,先创建 bucket,随后放置在该索引值的位置;  // 接着,判断新增还是修改原来的值。如果已经有值了,就修改该值;如果没有,就执行后续操作。  // 最后,进行新增数据操作。  put(key, value) {    // 1. 根据key获取对应的哈希表的索引    let index = hashFn(key, this.limit);    // 2. 根据对应的index 取出存放对应index的数组    let bucket = this.storage[index]; // bucket数据格式为 [[key,value],[key,value]]    // 3. 判断是否存在 index 对应的 值    if (bucket === undefined) {      // 不存在就创建      bucket = [];      this.storage[index] = bucket;    }    // 4. 判断插入操作还是修改操作    for (let i = 0; i < bucket.length; i++) {      const [key_, value_] = bucket[i]; // bucket[i]的数据格式为[key,value]      if (key_ === key) {        // 如果key相等 就修改数据        value_ = value;        return; // 修改完数据就 return      }    }    // 5. bucket 新增数据    bucket.push([key, value]); // bucket 存储元组 tuple,格式为 [key, value]    this.count++;    // 判断哈希表是否要扩容, 若装填因子 > 0.75 则扩容    if (this.count / this.limit > this.loadFactor) {      this.resize(this.getPrime(this.limit * 2));    }  }
  • get(key) 获取哈希表中特定位置的元素
  // get(key) 获取哈希表中特定位置的元素  // 实现思路:  // 首先,根据 key 通过哈希函数获取它在 storage 中对应的索引值 index。  // 然后,根据索引值获取对应的 bucket。  // 接着,判断获取到的 bucket 是否为 null,如果为 null,直接返回 null。  // 随后,线性遍历 bucket 中每一个 key 是否等于传入的 key。如果等于,直接返回对应的 value。  // 最后,遍历完 bucket 后,仍然没有找到对应的 key,直接 return null 即可。  get(key) {    // 1. 获取key 对应的哈希表中的index    let index = hashFn(key, this.limit);    // 2. 根据获取的index 取出 this.storage 中保存的数据    let bucket = this.storage[index];    // 3. 判断 是否存在 bucket ,若不存在就证明没有这个key    if (bucket === undefined) return null;    // 4. 如果存在就返回对应的value    for (const [key_, value] of bucket) {      if (key_ === key) {        return value;      }    }    // 5. 要还是没有找到就返回 null    return null;  }
  • remove(key) 删除哈希表中特定的元素
 // remove(key) 删除哈希表中特定的元素  // 实现思路:  // 首先,根据 key 通过哈希函数获取它在 storage 中对应的索引值 index。  // 然后,根据索引值获取对应的 bucket。  // 接着,判断获取到的 bucket 是否为 null,如果为 null,直接返回 null。  // 随后,线性查找 bucket,寻找对应的数据,并且删除。  // 最后,依然没有找到,返回 null。  remove(key) {    // 1. 获取key 对应的哈希表中的index    let index = hashFn(key, this.limit);    // 2. 根据获取的index 取出 this.storage 中保存的数据    let bucket = this.storage[index];    // 3. 判断 是否存在 bucket ,若不存在就证明没有这个key    if (bucket === undefined) return null;    // 4. 删除对应的key的数据    for (let i = 0; i < bucket.length; i++) {      const [key_, value] = bucket[i];      if (key_ === key) {        bucket.splice(i, 1); // 删除对应位置的数组        this.count--;        return [key_, value];      }    }    // 根据装填因子的大小,判断是否要进行哈希表压缩    if (this.limit > 7 && this.count / this.limit < this.minLoadFactor) {      this.resize(this.getPrime(Math.floor(this.limit / 2)));    }  }
  • isEmpty() 判断哈希表是否为空
// isEmpty() 判断哈希表是否为空  isEmpty() {    return this.count === 0;  }
  • size() 返回哈希表的长度
// size() 返回哈希表的长度  size() {    return this.count;  }
  • resize(newLimit) 对哈希表进行扩容或者压缩
// resize(newLimit) 对哈希表进行扩容或者压缩  //   实现思路:  // 首先,定义一个变量,比如 oldStorage 指向原来的 storage。  // 然后,创建一个新的容量更大的数组,让 this.storage 指向它。  // 最后,将 oldStorage 中的每一个 bucket 中的每一个数据取出来依次添加到 this.storage 指向的新数组中。  resize(newLimit) {    // 1. 保存旧的 storage 中的数据    let oldStorage = this.storage;    // 2. 重置所有的属性    this.storage = [];    this.count = 0;    this.limit = newLimit;    // 3. 遍历 oldStorage 取出所有的数据, 重新put 到 this.storage中    // oldStorage 的数据结构为 [[[key,value],[key,value],[key,value],[key,value]],[...]]    // bucket 的数据结构为 [[key,value],[key,value],[key,value],[key,value]]    for (const bucket of oldStorage) {      if (bucket) {        for (const [key, value] of bucket) {          this.put(key, value);        }      }    }  }

哈希表总体代码

/** * @param {string} str 传递进来的想要转变为下标的字符串 * @param {number} [limit=7] 符合数组最大的一个长度值 */function hashFn(str, limit = 7) {  // 创建一个质数的常量  const PRIME = 31;  // 创建存放哈希数的变量  let hashCode = 0;  // 使用霍纳法则计算hashCode  for (const item of str) {    hashCode = PRIME * hashCode + item.charCodeAt();  }  // 对hashCode取余并返回。  return hashCode % limit;}/** * * 判断是不是数字 * @param {*} number * @returns */function isPrime(number) {  if (number <= 1 || number === 4) return false;  const temp = Math.ceil(Math.sqrt(number));  for (let i = 2; i < temp; i++) {    if (number % i === 0) {      return false;    }  }  return true;}/** * * * @class HashTable */class HashTable {  constructor() {    this.storage = []; // 存储哈希表的数据    this.count = 0; // 当前存放元素的个数    this.limit = 7; // 取余的质数,和hashFn的第二个参数一个意思    // 装填因子(已有个数/总个数)    this.loadFactor = 0.75;    this.minLoadFactor = 0.25;  }  getPrime(number) {    while (!isPrime(number)) {      number++;    }    return number;  }  // hashTable 常见的操作  // put(key,value) 插入或修改操作  // get(key) 获取哈希表中特定位置的元素  // remove(key) 删除哈希表中特定的元素  // isEmpty() 判断哈希表是否为空  // size() 返回哈希表的长度  // resize(newLimit) 对哈希表进行扩容  // put(key,value) 插入或修改操作  // 实现思路  // 首先,根据 key 获取索引值 index,目的为将数据插入到 storage 的对应位置;  // 然后,根据索引值取出 bucket,如果 bucket 不存在,先创建 bucket,随后放置在该索引值的位置;  // 接着,判断新增还是修改原来的值。如果已经有值了,就修改该值;如果没有,就执行后续操作。  // 最后,进行新增数据操作。  put(key, value) {    // 1. 根据key获取对应的哈希表的索引    let index = hashFn(key, this.limit);    // 2. 根据对应的index 取出存放对应index的数组    let bucket = this.storage[index]; // bucket数据格式为 [[key,value],[key,value]]    // 3. 判断是否存在 index 对应的 值    if (bucket === undefined) {      // 不存在就创建      bucket = [];      this.storage[index] = bucket;    }    // 4. 判断插入操作还是修改操作    for (let i = 0; i < bucket.length; i++) {      const [key_, value_] = bucket[i]; // bucket[i]的数据格式为[key,value]      if (key_ === key) {        // 如果key相等 就修改数据        value_ = value;        return; // 修改完数据就 return      }    }    // 5. bucket 新增数据    bucket.push([key, value]); // bucket 存储元组 tuple,格式为 [key, value]    this.count++;    // 判断哈希表是否要扩容, 若装填因子 > 0.75 则扩容    if (this.count / this.limit > this.loadFactor) {      this.resize(this.getPrime(this.limit * 2));    }  }  // get(key) 获取哈希表中特定位置的元素  // 实现思路:  // 首先,根据 key 通过哈希函数获取它在 storage 中对应的索引值 index。  // 然后,根据索引值获取对应的 bucket。  // 接着,判断获取到的 bucket 是否为 null,如果为 null,直接返回 null。  // 随后,线性遍历 bucket 中每一个 key 是否等于传入的 key。如果等于,直接返回对应的 value。  // 最后,遍历完 bucket 后,仍然没有找到对应的 key,直接 return null 即可。  get(key) {    // 1. 获取key 对应的哈希表中的index    let index = hashFn(key, this.limit);    // 2. 根据获取的index 取出 this.storage 中保存的数据    let bucket = this.storage[index];    // 3. 判断 是否存在 bucket ,若不存在就证明没有这个key    if (bucket === undefined) return null;    // 4. 如果存在就返回对应的value    for (const [key_, value] of bucket) {      if (key_ === key) {        return value;      }    }    // 5. 要还是没有找到就返回 null    return null;  }  // remove(key) 删除哈希表中特定的元素  // 实现思路:  // 首先,根据 key 通过哈希函数获取它在 storage 中对应的索引值 index。  // 然后,根据索引值获取对应的 bucket。  // 接着,判断获取到的 bucket 是否为 null,如果为 null,直接返回 null。  // 随后,线性查找 bucket,寻找对应的数据,并且删除。  // 最后,依然没有找到,返回 null。  remove(key) {    // 1. 获取key 对应的哈希表中的index    let index = hashFn(key, this.limit);    // 2. 根据获取的index 取出 this.storage 中保存的数据    let bucket = this.storage[index];    // 3. 判断 是否存在 bucket ,若不存在就证明没有这个key    if (bucket === undefined) return null;    // 4. 删除对应的key的数据    for (let i = 0; i < bucket.length; i++) {      const [key_, value] = bucket[i];      if (key_ === key) {        bucket.splice(i, 1); // 删除对应位置的数组        this.count--;        return [key_, value];      }    }    // 根据装填因子的大小,判断是否要进行哈希表压缩    if (this.limit > 7 && this.count / this.limit < this.minLoadFactor) {      this.resize(this.getPrime(Math.floor(this.limit / 2)));    }  }  // isEmpty() 判断哈希表是否为空  isEmpty() {    return this.count === 0;  }  // size() 返回哈希表的长度  size() {    return this.count;  }  // resize(newLimit) 对哈希表进行扩容或者压缩  //   实现思路:  // 首先,定义一个变量,比如 oldStorage 指向原来的 storage。  // 然后,创建一个新的容量更大的数组,让 this.storage 指向它。  // 最后,将 oldStorage 中的每一个 bucket 中的每一个数据取出来依次添加到 this.storage 指向的新数组中。  resize(newLimit) {    // 1. 保存旧的 storage 中的数据    let oldStorage = this.storage;    // 2. 重置所有的属性    this.storage = [];    this.count = 0;    this.limit = newLimit;    // 3. 遍历 oldStorage 取出所有的数据, 重新put 到 this.storage中    // oldStorage 的数据结构为 [[[key,value],[key,value],[key,value],[key,value]],[...]]    // bucket 的数据结构为 [[key,value],[key,value],[key,value],[key,value]]    for (const bucket of oldStorage) {      if (bucket) {        for (const [key, value] of bucket) {          this.put(key, value);        }      }    }  }}
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。