数据结构和算法是一位优秀的程序员的基本功。在面试时这两点也是考察的重点，本文参考《学习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值相加。
散列表.PNG
下面通过数组来实现散列表。散列表主要包括以下方法：
散列函数：将键值与值的地址相对应
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;
};
对于散列表来说，我们移植某个值时不需要像数组一样，将位置也删除。如果将位置删除，会导致其他元素的位置改变，散列函数的对应关系就会被打乱。
这一篇就先介绍到这儿啦，接下来的一篇将介绍树和图这两种数据结构，请期待哈～
网友评论