Javascript中的8种常见数据结构( 二 ) _Javascript

4.集合

文章插图

集合是数学的基本概念：定义明确且不同的对象的集合。ES6引入了集合的概念，它与数组有一定程度的相似性。但是，集合不允许重复元素，也不会被索引。
一个典型的集合具有以下方法：
· values：返回集合中的所有元素
· size：返回元素数
· has：确定元素是否存在
· add：将元素插入集合
· delete：从集合中删除元素
· union：返回两组的交集
· difference：返回两组的差异
· subset：确定某个集合是否是另一个集合的子集
为了区分ES6中的集合，在以下示例中我们声明为MySet：
function MySet() {var collection = [];this.has = function (element) {return (collection.indexOf(element) !== -1);}this.values = function () {return collection;}this.size = function () {return collection.length;}this.add = function (element) {if (!this.has(element)) {collection.push(element);return true;}return false;}this.remove = function (element) {if (this.has(element)) {index = collection.indexOf(element);collection.splice(index, 1);return true;}return false;}this.union = function (otherSet) {var unionSet = new MySet();var firstSet = this.values();var secondSet = otherSet.values();firstSet.forEach(function (e) {unionSet.add(e);});secondSet.forEach(function (e) {unionSet.add(e);});return unionSet; }this.intersection = function (otherSet) {var intersectionSet = new MySet();var firstSet = this.values();firstSet.forEach(function (e) {if (otherSet.has(e)) {intersectionSet.add(e);}});return intersectionSet;}this.difference = function (otherSet) {var differenceSet = new MySet();var firstSet = this.values();firstSet.forEach(function (e) {if (!otherSet.has(e)) {differenceSet.add(e);}});return differenceSet;}this.subset = function (otherSet) {var firstSet = this.values();return firstSet.every(function (value) {return otherSet.has(value);});} }5.哈希表

文章插图

哈希表是键值数据结构。由于通过键查询值的闪电般的速度，它通常用于Map，Dictionary或Object数据结构中。如上图所示，哈希表使用哈希函数将键转换为数字列表，这些数字用作相应键的值。要快速使用键获取价值，时间复杂度可以达到O（1）。相同的键必须返回相同的值-这是哈希函数的基础。
哈希表具有以下方法：
· add：添加键值对
· delete：删除键值对
· find：使用键查找对应的值
Java简化哈希表的示例：
function hash(string, max) { var hash = 0; for (var i = 0; i < string.length; i++) { hash += string.charCodeAt(i); } return hash % max;}function HashTable() { let storage = []; const storageLimit = 4; this.add = function (key, value) { var index = hash(key, storageLimit); if (storage[index] === undefined) { storage[index] = [ [key, value] ]; } else { var inserted = false; for (var i = 0; i < storage[index].length; i++) { if (storage[index][i][0] === key) { storage[index][i][1] = value; inserted = true; } } if (inserted === false) { storage[index].push([key, value]); } } } this.remove = function (key) { var index = hash(key, storageLimit); if (storage[index].length === 1 && storage[index][0][0] === key) { delete storage[index]; } else { for (var i = 0; i < storage[index]; i++) { if (storage[index][i][0] === key) { delete storage[index][i]; } } } } this.lookup = function (key) { var index = hash(key, storageLimit); if (storage[index] === undefined) { return undefined; } else { for (var i = 0; i < storage[index].length; i++) { if (storage[index][i][0] === key) { return storage[index][i][1]; } } } }}6.树

文章插图

树数据结构是多层结构。与Array，Stack和Queue相比，它也是一种非线性数据结构。在插入和搜索操作期间，此结构非常高效。让我们看一下树数据结构的一些概念：
· root：树的根节点，无父节点
· parent 父节点：上层的直接节点，只有一个
· children 子节点：较低层的直接节点，可以有多个
· siblings 兄弟姐妹：共享同一父节点
· leaf 叶：没有子节点
· edge 边缘：节点之间的分支或链接
· path 路径：从起始节点到目标节点的边缘
· height of node 节点高度：特定节点到叶节点的最长路径的边数
· height of tree 树的高度：根节点到叶节点的最长路径的边数
· depth of node 节点深度：从根节点到特定节点的边数
· degree of node 节点度：子节点数