Dictionary和HashTable

Posted on | In

一、字典和散列表的概念

1.字典是什么？

​ 是一些元素的结合。每个元素有一个称作key的域，不同元素的key各不相同。

2.字典和集合有什么异同？

​ 集合是以[值，值]的方式存储数据，而字典是以[键，值]方式存储数据。

3.什么是散列表和散列函数？

​ 散列表：是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

​ 散列函数：给定一个键值，然后返回值在表中的位置。

4.散列表的特点是什么？

1) 访问速度很快

由于散列表有散列函数，可以将指定的 Key 都映射到一个地址上，所以在访问一个 Key（键）对应的 Value（值）时，根本不需要一个一个地进行查找，可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时，速度都很快。

2) 需要额外的空间

首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题。另外，如果有冲突的话，则也是需要额外的空间去存储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。

这个特点有个很常用的词可以表达，叫作“空间换时间”，在大多数时候，对于算法的实现，为了能够有更好的性能，往往会考虑牺牲些空间，让算法能够更快些。

3) 无序

散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素，散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快，但是对于有序访问却没有办法应对。

4) 可能会产生碰撞

没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决方案不一定一样。

二、请实现一个字典

  • set(key,value)：向字典中添加新元素。
  • delete(key)：通过使用键值从字典中移除键值对应的值。
  • has(key)：如果某个键值存在于这个字典中，则返回 true，否则返回 false。
  • get(key)：使用键值查找对应的值并返回。
  • clear()：删除字典中的所有元素。
  • size()：返回字典包含的元素数量，与数组的 length 属性类似。
  • keys()：将字典的所有键名以数组的形式返回。
  • values()：将字典包含的所有数值以数组形式返回。
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
// - set(key,value)：向字典中添加新元素。
// - delete(key)：通过使用键值从字典中移除键值对应的值。
// - has(key)：如果某个键值存在于这个字典中，则返回 true，否则返回 false。
// - get(key)：使用键值查找对应的值并返回。
// - clear()：删除字典中的所有元素。
// - size()：返回字典包含的元素数量，与数组的 length 属性类似。
// - keys()：将字典的所有键名以数组的形式返回。
// - values()：将字典包含的所有数值以数组形式返回。

class Dictionary {
    constructor() {
        this.item = {}
    }
    set(key, value) {
        this.item[key] = value;
    }
    delete(key){
        if (this.has(key)){
            delete this.item[key];
            return true;
        }
        return false;
    }
    has(key){
        return this.item.hasOwnProperty(key);//hasOwnProperty方法是判断实例上是否有某个属性，而in操作符会先判断实例，没有的话会往[[Prototype]]上找
    }
    get(key){
        return this.has(key) ? this.item[key] : undefined;
    }
    clear(){
        this.item = {};
    }
    size(){
        return this.keys().length;
    }
    keys(){
        return Object.keys(this.item);
    }
    values(){
        return Object.values(this.item);//返回可被枚举的值
    }
}

三、请实现一个散列表

散列函数：

WX20190723-131710@2x

  • put(key,value)：向散列表增加/更新一个新的项。
  • remove(key)：根据键值从散列表中移除值。
  • get(key)：根据键值检索到特定的值。
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
class HashTable {
    constructor() {
        this.table = [];
    }
    hashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
    put(key, value) {
        const position = this.hashCode(key);
        this.table[position] = value;
    }
    remove(key) {
        const position = this.hashCode(key);
        this.table[position] = undefined;
    }
    get(key) {
        const position = this.hashCode(key);
        return this.table[position];
    }
    print() {
        for (var i = 0; i < this.table.length; ++i) { //{1}
            if (this.table[i] !== undefined) {        //{2}
                console.log(i + ": " + this.table[i]);//{3}
            }
        }
    }
}

为什么remove方法，不是删除键，而是将键值设置为undefined?

WX20190723-132117@2x

散列表中存在的冲突

1
2
3
4
let hashTable = new HashTable();
hashTable.put('Jamie','123');
hashTable.put('Sue','345');
hashTable.print();//5: 345

Jamie和Sue的散列值是一样的，后面覆盖了前面的。解决方法在下面。

四、请利用之前已实现的链表，实现一个分离链接的散列表

分离链接是为散列表的每一个位置创建一个链表储存元素的方式来处理散列表中的冲突：

请实现新的散列表方法：

  • put(key,value)：将 key 和 value 存在一个 ValuePair 对象中（即可定义一个包含 key 和 value 属性的 ValuePair 类），并将其加入对应位置的链表中。
  • get(key)：返回键值对应的值，没有则返回 undefined。
  • remove(key)：从散列表中移除键值对应的元素。
  • print()：打印散列表中已保存的值。
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
class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
}

class HashTable {
    constructor() {
        this.table = [];
    }
    hashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
    put(key, value) {
        const position = this.hashCode(key);
        if (this.table[position] == undefined) {
            this.table[position] = new LinkedList();
        }
        this.table[position].append(new ValuePair(key, value));
    }
    get(key) {
        const position = this.hashCode(key);
        if (this.table[position] != undefined) {
            let current = this.table[position].getHead();
            while (current && current.element.key !== key) {
                current = current.next;
            }
            if (current) return current.element.value;
        }
        return undefined;
    }
    remove(key) {
        const position = this.hashCode(key);
        if (this.table[position] != undefined) {
            let current = this.table[position].getHead();
            while (current && current.element.key !== key) {
                current = current.next;
            }
            if (current) {
                this.table[position].remove(current.element);
                if (this.table[position].isEmpty()) this.table[position] = undefined;
                return true;
            }
        }
        return false;
    }
    print() {
        return Object.values(this.table);
    }
}

五、实现一个线性探查的散列表

线性探查是解决散列表中冲突的另一种方法，当向表中某一个位置加入新元素的时候，如果索引为 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
class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
}

class HashTable {
    constructor() {
        this.table = [];
    }
    hashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
    put(key, value) {
        let position = this.hashCode(key);
        while (this.table[position]) {
            position++;
        }
        this.table[position] = new ValuePair(key, value);
    }
    get(key) {
        let position = this.hashCode(key);
        if (this.table[position] != undefined) {
            while (this.table[position] == undefined || this.table[position].key != key) {
                position++;
            }
            if (this.table[position].key == key) {
                return this.table[position].value
            }
        }
        return undefined;
    }
    remove(key) {
        let position = this.hashCode(key);
        if (this.table[position] != undefined) {
            while (this.table[position] == undefined || this.table[position].key != key) {
                position++;
            }
            if (this.table[position].key == key) {
                this.table[position] = undefined;
                return true;
            }
        }
        return false;
    }
    print() {
        return Object.values(this.table);
    }
}

这个会进入死循环

1
2
3
hashTable.put('Jamie','123');
console.log(hashTable.get('Jamie'));
console.log(hashTable.get('Sue'));

Map类

1
2
3
4
5
6
7
8
9
var map = new Map();
map.set('Gandalf', 'gandalf@email.com');
map.set('John', 'johnsnow@email.com');
map.set('Tyrion', 'tyrion@email.com');
var g = map.keys();
console.log(map.has('Gandalf')); //输出true 
console.log(map.size); //输出3
console.log(g.next()); //输出{value: "Gandalf", done: false}
console.log(g.next()); //输出{value: "John", done: false}

Map类的values和keys返回的是Iterator，并且自带size属性

WeakMap和WeakSet
  • WeakSet或WeakMap类􏴌􏱨entries􏲡keys和values􏳠方法􏴝
  • 􏳗 􏰬能用对象作为􏳎􏰦键名
  • 知道键才能取出值