尧尧神教
尧尧神教
7月前 · 3 人阅读

数据结构和算法是一位优秀的程序员的基本功。在面试时这两点也是考察的重点,本文参考《学习JavaScript数据结构与算法》一书,总结了常见的数据结构。

目录:
一、数组
二、栈和队列
三、链表
四、集合
五、字典和散列表
六、树
七、图

第二篇我们将介绍集合、字典以及散列表这三种数据结构

四、集合:
集合是由一组无序且唯一(即不重复)的项组成的,类似于我们数学中有限集合的概念。在ES6中已经有了Set对象,可以参考MDN中对Set对象的介绍 https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Set。接下来,我们通过扩展对象来实现JavaScript中Set的功能。
Set集合需要声明的方法主要有以下这些:
has(value):如果值在集合中,返回true,否则返回false

this.has = function(value) {
  return items.hasOwnProterty(value);
}

add(value):向集合中添加一个新的项

this.add = function(value) {
  if (!this.has(value)) {
    items[value] = value;
  }
  return false;

remove(value): 从集合移除一个值

this.remove = function(value) {
  if (this.has(value)) {
    delete items[value];
    return true;
  }
  return false;

clear():移除集合中的所有项

this.clear = function() {
  items = {};
};

size():返回集合所包含元素的数量,与数组的length属性类似

this.size = function() {
   return Object.keys(items).length;
}

values():返回一个包含集合中所有值的数组,在这里要说明一下在《学习JavaScript数据结构与算法》这本书中的实现方式是有问题的,下面是我修改之后的方法:

this.values = function() {
    let keyArr = Object.keys(items);
    let values = [];
    keyArr.forEach( (key) => {
       values.push(items[key]);
     });
  return values;
};

集合已经定义好了,接下来看看我们该怎样使用封装好的Set集合呢?

var set = new Set ();
set.add(1);
console.log(set.values());  //输出 [1]
console.log(set.has(1));  // 输出true

这里,我们定义的Set集合与ES6中定义的区别在于我们的values方法返回的是数组而ES6中返回的一个可迭代的对象。
五、字典和散列表:
字典:字典和集合一样,都存储不重复的值。在集合中,我们感兴趣的是每个值本身,并把它当做主要元素。在字典中,我们用[键,值]的形式来存储数据,其中键名可以用来查询特定元素。同样,ES6中包含了一个Map对象,用来实现字典数据结构。https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Map。Map的实现方式与Set类似,这边就不再赘述。接下来介绍一种很重要的数据结构:散列表。
散列表:在之前介绍的几种数据结构中,要想寻找某个值,必须要遍历整个数据结构。然而,通过散列表,我们可以尽可能快地在数据结构中找到某个值。
散列表的核心是散列函数,散列函数的作用是给定一个键值,然后返回表中的地址。最常见的散列函数——“lose lose”散列函数:简单地将每个键值中的每个字母的ASCII值相加。

下面通过数组来实现散列表。散列表主要包括以下方法:

散列函数:

将键值与值的地址相对应

put(key, value):

向散列表增加一个新的项

remove(key):

根据键值从散列表中移除值

get(key):

返回根据键值检索到的特定的值

function HashTable() {
  var table = [];
  var loseloseHashFun = function (key) {
    var hash = 0;
    for (var i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % 37; // 取hash值除以37的余数作为值的地址,目的减少数组长度
  };
  this.put = function (key, value) {
    var position = loseloseHashCode(key);
    table[position] = value;
  };
  this.get = function (key) {
    return table[loseloseHashCode(key)];
  };
  this.remove = function (key) {
    table[loseloseHashCode(key)] = undefined;
  };

对于散列表来说,我们移植某个值时不需要像数组一样,将位置也删除。如果将位置删除,会导致其他元素的位置改变,散列函数的对应关系就会被打乱。

这一篇就先介绍到这儿啦,接下来的一篇将介绍这两种数据结构,请期待哈~

收藏 0
value key function 集合 数据结构 set
评论 ( 0 )