数据结构与算法

Javascript的数据结构与算法(二)

Posted by 黄成都 on 2016-12-14
Words 2.9k and Reading Time 13 Minutes
Viewed Times

1集合

1.1集合的实现

集合是由一组无序且唯一(即不能重复)的项组成的。这个数据结构使用了与有限集合相同 的数学概念,但应用在计算机科学的数据结构中。

集合中常用方法列表：

  • add(value):向集合中添加一个新的项。
  • remove(value):从集合中移除一个值。
  • has(value):如果在集合中，返回true，否则返回false。
  • clear():清除集合中的所有项。
  • size():返回集合所包含元素的数量。
  • values():返回一个包含集合中所有值得数组。
  • union(otherSet):并集操作，返回一个包含两个集合中所有元素的新集合。
  • intersection(otherSet):交集操作，返回一个包含两个集合中共有元素的新集合。
  • difference(otherSet):差集操作，返回一个包含左右存在于第一个集合并且不存在于第二个集合的元素的新集合。
  • subset(otherSet):子集操作，验证一个给定集合是否是另一个集合的子集，返回true和false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
function Set() {
    this.items = {};
}
Set.prototype = {
    constructor: Set,
    has: function(value) {
        return value in this.items;
    },
    add: function(value) {
        if (!this.has(value)) {
            this.items[value] = value;
            return true;
        }
        return false;
    },
    remove: function(value) {
        if (this.has(value)) {
            delete this.items[value];
            return true;
        }
        return false;
    },
    clear: function() {
        this.items = {};
    },
    size: function() {
        return Object.keys(this.items).length;
    },
    values: function() {
        return Object.keys(this.items);
    },
    union: function(otherSet) {
        var unionSet = new Set();
        var values = this.values();
        for (var i = 0; i < values.length; i++) {
            unionSet.add(values[i]);
        }
        values = otherSet.values();
        for (var i = 0; i < values.length; i++) {
            unionSet.add(values[i]);
        }
        return unionSet;
    },
    intersection: function(otherSet) {
        var intersectionSet = new Set();
        var values = this.values();
        for (var i = 0; i < values.length; i++) {
            if (otherSet.has(values[i])) {
                intersectionSet.add(values[i]);
            }
        }
        return intersectionSet;
    },
    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;
    },
    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;
    },
};

1.2集合的使用

1
2
3
4
5
6
7
8
9
10
11
var set = new Set();
set.add(1);
console.log(set.values());//["1"]
console.log(set.has(1));//true
console.log(set.size());//1
set.add(2);
console.log(set.values());//["1","2"]
console.log(set.has(2));//true
console.log(set.size());//2
set.remove(2);
console.log(set.values());//["1"]

交集、并集、子集、差集的使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//并集测试
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 setAB = setA.union(setB);
console.log(setAB.values()); // ["1", "2", "3", "4", "5", "6"]
//交集测试
setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);
var intersectionAB = setA.intersection(setB);
console.log(intersectionAB.values()); // ["2", "3"]
//差集侧事故
setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);
var differenceAB = setA.difference(setB);
console.log(differenceAB.values()); //["1"]
//子集测试
setA = new Set();
setA.add(1);
setA.add(2);
var setB = new Set();
setB.add(1);
setB.add(2);
setB.add(3);
setC = new Set();
setC.add(2);
setC.add(3);
setC.add(4);
console.log(setA.subset(setB)); //true
console.log(setA.subset(setC)); //false

2字典和散列表

集合、字典和散列表可以存储不重复的值。在集合中,我们感兴趣的是每个值本身,并把它 当作主要元素。在字典中,我们用[键,值]的形式来存储数据。在散列表中也是一样(也是以[键, 值]对的形式来存储数据)。

2.1字典

集合表示一组互不相同的元素(不重复的元素)。在字典中,存储的是[键,值] 对,其中键名是用来查询特定元素的。字典和集合很相似,集合以[值,值]的形式存储元素,字 典则是以[键,值]的形式来存储元素。字典也称作映射。下面是字典需要实现的方法：

  • set(key,value): 向字典中添加新元素。
  • remove(key): 通过使用键值来从字典中语出键值对应的数据值。
  • has(key): 如果某个键值存在于这个字典中，否则返回true，反之则返回false。
  • get(key): 通过键值查询特定的数值并且返回。
  • clear(): 将这个字典中的所有元素全部删除。
  • size(): 返回字典中包含元素的数量。
  • keys(): 将字典所包含的所有键名以数组的形式返回。
  • values(): 将字典所包含的所有数值以数组的形式返回。
  • getItems(): 返回字典。

2.1.1字典的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function Dictionary() {
    this.items = {};
}
Dictionary.prototype = {
    constructor: Dictionary,
    has: function(key) {
        return key in this.items;
    },
    set: function(key, value) {
        this.items[key] = value;
    },
    remove: function(key) {
        if (this.has(key)) {
            delete this.items[key];
            return true;
        }
        return false;
    },
    get: function(key) {
        return this.has(key) ? this.items[key] : undefined;
    },
    values: function() {
        var values = [];
        for (var key in this.items) {
            if (this.has(key)) {
                values.push(key);
            }
        }
        return values;
    },
    clear: function() {
        this.items = {};
    },
    size: function() {
        return Object.keys(this.items).length;
    },
    keys: function() {
        return Object.keys(this.items);
    },
    getItems: function() {
        return this.items;
    }
};

2.1.2字典的基本使用

1
2
3
4
5
6
7
8
9
10
11
var dictionary = new Dictionary();
console.log(dictionary.size()); //0
dictionary.set('first', 'huang');
dictionary.set('second', 'cheng');
dictionary.set('third', 'du');
console.log(dictionary.has('first')); //true
console.log(dictionary.get('second')); //cheng
console.log(dictionary.values()); // ["first", "second", "third"]
dictionary.remove('second');
console.log(dictionary.keys()); //["first", "third"]
console.log(dictionary.getItems()); //{ first="huang",  third="du"}

2.2散列表

HashTable类,也叫HashMap类,是Dictionary类的一种散列表实现方式。散列算法的作用是尽可能快地在数据结构中找到一个值。在之前的章节中,你已经知道如果 要在数据结构中获得一个值(使用get方法),需要遍历整个数据结构来找到它。如果使用散列 函数,就知道值的具体位置,因此能够快速检索到该值。散列函数的作用是给定一个键值,然后 返回值在表中的地址。

2.2.1基本版的散列表实现

在散列表中我们通过散列函数来确定键值对的关系。基本方法如下：

  • put(key,value): 向散列表增加一个新的选项(也可能是更新散列表)。
  • remove(key): 根据键值从散列表中移除值。
  • get(key): 返回根据键值检索到的特定值。

对于HashTable类来说,我们不需要像ArrayList类一样从table数组中将位置也移除。由 于元素分布于整个数组范围内,一些位置会没有任何元素占据,并默认为undefined值。我们也 不能将位置本身从数组中移除(这会改变其他元素的位置),否则,当下次需要获得或移除一个 元素的时候,这个元素会不在我们用散列函数求出的位置上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//lose-los散列函数
function loseloseHashCode(key) {
    var hash = 0;
    for (var i = 0; i < key.length; i++) {
        hash += key.charCodeAt(i);
    }
    return hash % 37;
}

function HashTable() {
    this.table = [];
}
HashTable.prototype = {
    constructor: HashTable,
    put: function(key, value) {
        var position = loseloseHashCode(key);
        console.log(position + '- ' + key);
        this.table[position] = value;
    },
    get: function(key) {
        return this.table[loseloseHashCode(key)];
    },
    remove: function(key) {
        this.table[loseloseHashCode(key)] = undefined;
    }
};

var hash = new HashTable();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'johnsnow@email.com');
hash.put('Tyrion', 'tyrion@email.com');
console.log(hash.get('Gandalf')); //gandalf@email.com
console.log(hash.get('Loiane')); //undefined
hash.remove('Gandalf');
console.log(hash.get('Gandalf')); //undefined

有时候,一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候,我们称其为冲突。当这种情况发生的时候就要去解决它。处理冲突有几种方法:分离链接、线性探查和双散列法,我们会介绍前两种方法。对于分离链接和线性探查来说,只需要重写三个方法:put、get和remove。这三个方法在 每种技术实现中都是不同的。

2.2.2分离链接版散列表

为了实现一个使用了分离链接的HashTable实例,我们需要一个新的辅助类来表示将要加入LinkedList实例的元素。我们管它叫ValuePair类。LinkedList的实现具体看javascript的数据结构与算法(一).html)。

  • 分离链接：分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法,但是它在HashTable实例之外还需要额外的存储空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
function HashTable() {
    this.table = []; 
    //lose-los散列函数 
    function loseloseHashCode(key) {
        var hash = 0;
        for (var i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        //console.log(key + " - " + (hash % 37));
        return hash % 37;
    }

    function ValuePair(key, value) {
        this.key = key;
        this.value = value;
        this.toString = function() {
            return '[' + this.key + ' - ' + this.value + ']';
        }
    }
    if ((typeof this.put !== 'function') && (typeof this.put !== 'string')) {
        HashTable.prototype.put = function(key, value) {
            var position = loseloseHashCode(key);
            if (this.table[position] === undefined) {
                this.table[position] = new LinkedList();
            }
            this.table[position].append(new ValuePair(key, value));
        };
        HashTable.prototype.get = function(key) {
            var position = loseloseHashCode(key);
            if (this.table[position] !== undefined) {
                var current = this.table[position].getHead();
                while (current.next) {
                    if (current.element.key === key) {
                        return current.element.value;
                    }
                    current = current.next;
                }
                //第一个元素或者最后一个元素
                if (current.element.key === key) {
                    return current.element.value;
                }
            } else {
                return undefined;
            }
        };
        HashTable.prototype.remove = function(key) {
            var position = loseloseHashCode(key);
            if (this.table[position] !== undefined) {
                var current = this.table[position].getHead();
                while (current.next) {
                    if (current.element.key === key) {
                        this.table[position].remove(current.element);
                        if (this.table[position].isEmpty()) {
                            this.table[position] = undefined;
                        }
                        return true;
                    }
                    current = current.next;
                }
                //检查是否是第一个或者最后一个
                if (current.element.key === key) {
                    this.table[position].remove(current.element);
                    if (this.table[position].isEmpty()) {
                        this.table[position] = undefined;
                    }
                    return true;
                }
            }
            return false;
        };
    }
}
var hash = new HashTable();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'johnsnow@email.com');
//下面两个hash值相同
hash.put('Aaron', 'huang@gmail.com');
hash.put('Tyrion', 'tyrion@email.com');
console.log(hash.get('Gandalf')); //gandalf@email.com
console.log(hash.get('Loiane')); //undefined
hash.remove('Gandalf');
console.log(hash.get('Gandalf')); //undefined

2.2.3线性探查版散列表

  • 另一种解决冲突的方法是线性探查。当想向表中某个位置加入一个新元素的时候,如果索引为index的位置已经被占据了,就尝试index+1的位置。如果index+1的位置也被占据了,就尝试 index+2的位置,以此类推。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
function HashTable() {
    this.table = []; //lose-los散列函数 
    function loseloseHashCode(key) {
        var hash = 0;
        for (var i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        //console.log(key + " - " + (hash % 37));
        return hash % 37;
    }

    function ValuePair(key, value) {
        this.key = key;
        this.value = value;
        this.toString = function() {
            return '[' + this.key + ' - ' + this.value + ']';
        }
    }
    if ((typeof this.put !== 'function') && (typeof this.put !== 'string')) {
        HashTable.prototype.put = function(key, value) {
            var position = loseloseHashCode(key);
            if (this.table[position] === undefined) {
                this.table[position] = new ValuePair(key, value);
            } else {
                var index = position + 1;
                while (this.table[index] !== undefined) {
                    index++;
                }
                this.table[index] = new ValuePair(key, value);
            }
        };
        HashTable.prototype.get = function(key) {
            var position = loseloseHashCode(key);
            if (this.table[position] !== undefined) {
                if (this.table[position].key === key) {
                    return this.table[position].value;
                } else {
                    var index = position + 1;
                    //index不超过数组的长度
                    while (((this.table[index] === undefined) || (this.table[index].key !== key)) && (index < this.table.length)) {
                        index++;
                    }
                    if (this.table[index] && (this.table[index].key === key)) {
                        return this.table[index].value;
                    } else {
                        return undefined;
                    }
                }
            } else {
                return undefined;
            }
        };
        HashTable.prototype.remove = function(key) {
            var position = loseloseHashCode(key);
            if (this.table[position] !== undefined) {
                if (this.table[position].key === key) {
                    this.table[position] = undefined;
                    return true;
                } else {
                    var index = position + 1;
                    while ((this.table[index] === undefined) || (this.table[index].key !== key)) {
                        index++;
                    }
                    if (this.table[index].key === key) {
                        this.table[index] = undefined;
                        return true;
                    }
                }
            } else {
                return false;
            }
        };
    }
}
var hash = new HashTable();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'johnsnow@email.com');
//下面两个hash值相同
hash.put('Aaron', 'huang@gmail.com');
hash.put('Tyrion', 'tyrion@email.com');
console.log(hash.get('Gandalf')); //gandalf@email.com
console.log(hash.get('Loiane')); //undefined
console.log(hash.remove('Gandalf')); //true
console.log(hash.get('Gandalf')); //undefined

源码地址

Javascript的数据结构与算法(二)源码

...

...

00:00
00:00
FEATURED TAGS
数据结构与算法