JS数据结构学习（二）

集合（ES6 set）

集合是由一组无序且唯一（不能重复）的项组成的。这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。
空集是不包含任何元素的集合。
可以把集合想象成一个既没有重复元素，也没有顺序概念的数组。

实现

声明集合的方法：

add(value):向集合添加一个新的项。
remove(value):从集合移除一个值。
has(value):如果值在集合中，返回true，否则返回false。
clear():移除集合中的所有项。
size():返回集合所包含元素的数量。与数组的length属性类似。
values():返回一个包含集合中所有值得数组。

function Set() {
    var items = {};
    this.add = function(value){
        if (!this.has(value)){
            items[value] = value;
            return true;
        }
        return false;
    };
    this.remove = function(value){
        if (this.has(value)){
            delete items[value];
            return true;
        }
        return false;
    };
    this.has = function(value){
        return items.hasOwnProperty(value);
    };
    this.clear = function(){
        items = {};
    };
    this.size = function(){
        return Object.keys(items).length;
    };
    this.values = function(){
        return Object.keys(items);
    };
}

并集

this.union = function(otherSet){
    var unionSet = new Set(); //{1}
    var values = this.values(); //{2}
    for (var i=0; i<values.length; i++){
        unionSet.add(values[i]);
    }
    values = otherSet.values(); //{3}
    for (var i=0; i<values.length; i++){
        unionSet.add(values[i]);
    }
    return unionSet;
};

测试上述代码：

var setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

var setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);

var unionAB = setA.union(setB);
console.log(unionAB.values()); // ["1", "2", "3", "4", "5", "6"]

交集

this.intersection = function(otherSet){
    var intersectionSet = new Set(); //{1}
    var values = this.values();
    for (var i=0; i<values.length; i++){ //{2}
        if (otherSet.has(values[i])){ //{3}
            intersectionSet.add(values[i]); //{4}
        }
    }
    return intersectionSet;
}

测试上述代码：

var setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

var setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

var intersectionAB = setA.intersection(setB);
console.log(intersectionAB.values()); // ['2', '3']

差集

this.difference = function(otherSet){
    var differenceSet = new Set();
    var values = this.values();
    for (var i=0; i<values.length; i++){
        if (!otherSet.has(values[i])){
            differenceSet.add(values[i]);
        }
    }
return differenceSet;
};

测试上述代码：

var setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

var setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

var differenceAB = setA.difference(setB);
console.log(differenceAB.values()); // ['1']

子集

this.subset = function(otherSet){
    if (this.size() > otherSet.size()){
        return false;
    } else {
        var values = this.values();
        for (var i=0; i<values.length; i++){
            if (!otherSet.has(values[i])){
                return false;
            }
        }
        return true; //{5}
    }
};

测试上述代码：

var setA = new Set();
setA.add(1);
setA.add(2);

var setB = new Set();
setB.add(1);
setB.add(2);
setB.add(3);

var setC = new Set();
setC.add(2);
setC.add(3);
setC.add(4);

console.log(setA.subset(setB));
console.log(setA.subset(setC));
// setA是setB的子集（因此输出为true），然而setA不是setC的子集（setC
只包含了setA中的2，而不包含1），因此输出为false。

字典(ES6 map)

字典和集合很相似，集合以[值, 值]的形式存储元素，字典则是以[键, 值]的形式来存储元素，也称作映射。

散列表

散列算法的作用是尽可能快地在数据结构中找到一个值。如果要在数据结构中获得一个值，需要遍历整个数据结构来找到它。如果使用散列函数，就知道值得具体位置，因此能够快速检索到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址。

Posted by Hexo on 2017-07-28