7.1 字典

我们知道，集合表示一组互不相同的元素（不能重复的元素）。在字典中，存储的是[键, 值]对，其中键名是用来查询特定元素的。字典和集合很相似，集合以[值, 值]的形式存储元素，字典则是以[键, 值]的形式来存储元素。字典也称作映射、符号表或关联数组

7.1.1 创建字典类

以下就是我们Dictionary类的骨架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function defaultToString(key) {
    if(key === null){
        return 'NULL'
    }else if (key === undefined){
        return  'UNDEFINED';
    }else if(typeof key === 'string' || key instanceof String){
        return `${key}`;
    }
    return key.toString();
}
export default class Dictionary {
    constructor(toStringFn = defaultToString) {
        this.toStringFn = toStringFn;
        this.table = {};
    }
}

在字典中，理想的情况是用字符串作为键名，值可以是任何类型。但是JavaScript不是强类型语言，我们不能保证键一定是字符串。我们需要把所有作为键名传入的对象化转为字符串，使得从Dictionary类中搜索和获取值更简单。

为了在字典中保存value，我们将key转化为了字符串，而为保存信息需要，我们同样要保存原始的key。因此，我们不只是将value保存在字典中，而是要保存两个值：原始的key和value。所以我们需要声明一个[键，值对类：

1
2
3
4
5
6
7
8
9
10
class ValuePairs {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }

    toString() {
        return `[#${this.key}: ${this.value}]`
    }
}

然后我们需要声明一些字典所能使用的方法：

set(key,value)：向字典中添加新元素。如果key存在，那么已存在的value会被新的值覆盖

get(key)：通过以键名作为参数查找特定数值并返回

remove(key)：通过使用键名作为参数从字典中移除键名对应的数据值

has(key)：如果某个键存在于字典中，返回true，否则返回false

keyValues()：将字典中所有[键,值]对返回

values()：将字典所包含的所有数值以数组形式返回

keys()：将字典所包含的所有键名以数组形式返回

clear()：删除字典中所有值

size()：返回字典所包含值的数量

isEmpty()：判断是否是空字典

forEach(callback)：迭代字典中所有的键值对。callback有两个参数：key和value。该方法可以在回调函数返回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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
/**
 * Created by yh on 2021/9/26
 */
function defaultToString(key) {
    if (key === null) {
        return 'NULL'
    } else if (key === undefined) {
        return 'UNDEFINED';
    } else if (typeof key === 'string' || key instanceof String) {
        return `${key}`;
    }
    return key.toString();
}

class ValuePairs {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }

    toString() {
        return `[#${this.key}: ${this.value}]`
    }
}

export default class Dictionary {
    constructor(toStringFn = defaultToString) {
        this._toStringFn = toStringFn;
        this.table = {};
    }

    /**
     * 向字典中添加新元素。如果key存在，那么已存在的value会被新的值覆盖
     * @param key
     * @param value
     */
    set(key, value) {
        let tableKey = this._toStringFn(key);
        this.table[tableKey] = new ValuePairs(key, value);
    }

    /**
     * 通过以键名作为参数查找特定数值并返回
     * @param key
     * @return {*}
     */
    get(key) {
        let valuePairs = this.table[this._toStringFn(key)];//获取所有[键，值]队类
        if (valuePairs) {
            return valuePairs.value;
        }
        return undefined;
    }

    /**
     * 通过使用键名作为参数从字典中移除键名对应的数据值
     * @param key
     * @return {boolean}
     */
    remove(key) {
        if (this.has(key)) {
            delete this.table[this._toStringFn(key)];
            return true;
        }
        return false;
    }

    /**
     * 如果某个键存在于字典中，返回true，否则返回false
     * @param key
     * @return {boolean}
     */
    has(key) {
        return Object.prototype.hasOwnProperty.call(this.table, this._toStringFn(key));
    }


    /**
     * 将字典中所有[键,值]对返回
     * @return {[]}
     */
    keyValues() {
        let valuePairs = [];
        for (let key in this.table) {
            if (this.has(key)) {
                valuePairs.push(this.table[key]);
            }
        }
        return valuePairs;
    }

    /**
     * 将字典所包含的所有数值以数组形式返回
     */
    values() {
        return this.keyValues().map(valuePair => valuePair.value);
    }

    /**
     * 将字典所包含的所有键名以数组形式返回
     * @return {string[]}
     */
    keys() {
        return this.keyValues().map(valuePair => valuePair.key);
    }

    /**
     * 删除字典中所有值
     */
    clear() {
        this.table = {};
    }

    /**
     * 返回字典所包含值的数量
     * @return {number}
     */
    size() {
        return Object.keys(this.table).length;
    }

    /**
     * 判断是否是空字典
     * @return {boolean}
     */
    isEmpty() {
        return this.size() === 0;
    }


    /**
     * 矢代字典中所有的键值对。callback有两个参数：key和value。该方法可以在回调函数返回false时被终止
     * @param callback
     */
    forEach(callback) {
        if (typeof callback !== 'function') return;
        let valuePairs = this.keyValues();
        for (let i = 0; i < valuePairs.length; i++) {
            let result = callback(valuePairs[i].key, valuePairs[i].value);
            if (result === false) {
                break;
            }
        }
    }

    toString() {
        if (this.isEmpty()) {
            return '';
        }
        let valuePairs = this.keyValues();
        let objString = `${valuePairs[0].toString()}`
        for (let i = 1; i < valuePairs.length; i++) {
            objString = `${objString},${valuePairs[i].toString()}`
        }
        return objString;
    }
}

7.1.2 使用Dictionary类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let dictionary = new Dictionary();
dictionary.set("张三","Lu0@email.net");
dictionary.set("李四","UGFuT70lwe@email.com");

console.log(dictionary.size());
console.log(dictionary.toString());

console.log(dictionary.has("李四"));
console.log(dictionary.get('李四'));

dictionary.remove("李四");
dictionary.set("John","kGR2y@email.com")

console.log(dictionary.keys());
console.log(dictionary.values());

运行结果如下：

Dictionary类运行结果1.png

我们再试试forEach()方法来迭代字典类元元素

1
2
3
dictionary.forEach((key,value) => {
    console.log(`${key}的电子邮箱号码为：${value}`);
});

运行结果为：

Dictionary类运行结果2.png

7.2 散列表

散列表（或者叫哈希表），是一种改进的Dictionary，它将key通过一个固定的算法（散列函数或哈希函数）得出一个数字，然后将Dictionary中key所对应的value存放到这个数字所对应的数组下标所包含的存储空间中。在原始的Dictionary中，如果要查找某个key所对应的value，我们需要遍历整个字典。为了提高查询的效率，我们将key对应的value保存到数组里，只要key不变，使用相同的散列函数计算出来的数字就是固定的，于是就可以很快地在数组中找到你想要查找的value。

Image

散列表有一些在计算机科学中应用的例子。因为它是字典的一种实现，所以可以用作关联数组。它也可以用来对数据库进行索引。当我们在关系型数据库中创建一个新的表时，一个不错的做法就是同时创建一个索引来更快地查询到记录的key。在这情况下，散列表可以用来保存键和对表中记录的引用。另一个很常见的应用是使用散列表来表现对象。JavaScript语言内部就是使用散列表来表示每个对象。此时，对象的每个属性和方法（属性）被存储为key对象类型，每个key指向对应的对象成员。

接下来我们来使用最常见的散列函数-lose lose 散列函数，方法是简单地将每个键中的每个字母的ASCII值相加得到散列值，如下图所示：

Image

7.2.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
function defaultToString(key) {
    if (key === null) {
        return 'NULL'
    } else if (key === undefined) {
        return 'UNDEFINED';
    } else if (typeof key === 'string' || key instanceof String) {
        return `${key}`;
    }
    return key.toString();
}

class ValuePairs {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }

    toString() {
        return `[#${this.key}: ${this.value}]`
    }
}

export default class HashTable {
    constructor(toStringFn = defaultToString) {
        this._toStringFn = toStringFn;
        this.table = {};
    }
}

然后我们给类添加一些基本方法：

put(key,value)：向散列表增加一个新的项（也能更新散列列表）

get(key)：返回根据键名检索到的特定的值

remove(key)：根据键名从散列表中移除值

has(key)：如果某个键存在于字典中，返回true，否则返回false

keyValues()：将散列表中所有[键,值]对返回

values()：将散列表所包含的所有数值以数组形式返回

keys()：将散列表所包含的所有键名以数组形式返回

clear()：删除字典中所有值

size()：返回散列表所包含值的数量

isEmpty()：判断是否是空散列表

forEach(callback)：迭代散列表中所有的键值对。callback有两个参数：key和value。该方法可以在回调函数返回false时被终止

创建散列函数

在实现这三个方法之前，我们要实现的第一个方法是散列函数，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
loseLoseHashCode(key) {
    //如果是一个数则直接返回
    if (typeof key === 'number') {
        return key;
    }
    // 把key转为一个字符串
    const tableKey = this._toStringFn(key);
    let hash = 0;   // 散列值的总和
    for (let i = 0; i < tableKey.length; i++) {
        // 从ASCII表中查到的每一个字符对应的ASCII值加到hash变量中。
        hash += tableKey.charCodeAt(i);
    }
    // 为了得到比较小的数值，我们会使用hash值和任意数做除法的余数，这样可以规避操作数超过数值变量变大表示范围的风险
    return hash % 37;
}

完整代码：

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
function defaultToString(key) {
    if (key === null) {
        return 'NULL'
    } else if (key === undefined) {
        return 'UNDEFINED';
    } else if (typeof key === 'string' || key instanceof String) {
        return `${key}`;
    }
    return key.toString();
}

class ValuePairs {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }

    toString() {
        return `[#${this.key}: ${this.value}]`
    }
}

export default class HashTable {
    constructor(toStringFn = defaultToString) {
        this._toStringFn = toStringFn;
        this.table = {};
    }

    loseLoseHashCode(key) {
        //如果是一个数则直接返回
        if (typeof key === 'number') {
            return key;
        }
        // 把key转为一个字符串
        const tableKey = this._toStringFn(key);
        let hash = 0;   // 散列值的总和
        for (let i = 0; i < tableKey.length; i++) {
            // 从ASCII表中查到的每一个字符对应的ASCII值加到hash变量中。
            hash += tableKey.charCodeAt(i);
        }
        // 为了得到比较小的数值，我们会使用hash值和任意数做除法的余数，这样可以规避操作数超过数值变量变大表示范围的风险
        return hash % 37;
    }

    hashCode(key) {
        return this.loseLoseHashCode(key);
    }

    /**
     * 向散列表增加一个新的项（也能更新散列列表）
     * @param key
     * @param value
     */
    put(key, value) {
        if (key === null && value === null) return false;
        let position = this.hashCode(key);  
        this.table[position] = new ValuePairs(key, value);
        return true;
    }

    /**
     * 根据键名从散列表中移除值
     * @param key
     */
    remove(key) {
        let hash = this.hashCode(key);
        let valuePairs = this.table[hash];
        if (valuePairs != null) {
            delete this.table[hash];
            return true;
        }
        return false;
    }

    /**
     * 返回根据键名检索到的特定的值
     * @param key
     */
    get(key) {
        let valuePairs = this.table[this.hashCode(key)];
        return valuePairs == null ? undefined : valuePairs.value;
    }

    /**
     * 如果某个键存在于散列表中，返回true，否则返回false
     * @param key
     * @return {boolean}
     */
    has(key) {
        return Object.prototype.hasOwnProperty.call(this.table, this.hashCode(key));
    }

    /**
     * 将散列表中所有[键,值]对返回
     * @return {[]}
     */
    keyValues() {
        let valuePairs = [];
        for (let key in this.table) {
            if (this.has(key)) {
                valuePairs.push(this.table[key]);
            }
        }
        return valuePairs;
    }

    /**
     * 将散列表所包含的所有数值以数组形式返回
     */
    values() {
        return this.keyValues().map(valuePair => valuePair.value);
    }

    /**
     * 将散列表所包含的所有键名以数组形式返回
     * @return {string[]}
     */
    keys() {
        return this.keyValues().map(valuePair => valuePair.key);
    }

    /**
     * 删除散列表中所有值
     */
    clear() {
        this.table = {};
    }

    /**
     * 返回散列表所包含值的数量
     * @return {number}
     */
    size() {
        return Object.keys(this.table).length;
    }

    /**
     * 判断是否是空散列表
     * @return {boolean}
     */
    isEmpty() {
        return this.size() === 0;
    }


    /**
     * 矢代散列表中所有的键值对。callback有两个参数：key和value。该方法可以在回调函数返回false时被终止
     * @param callback
     */
    forEach(callback) {
        if (typeof callback !== 'function') return;
        let valuePairs = this.keyValues();
        for (let i = 0; i < valuePairs.length; i++) {
            let result = callback(valuePairs[i].key, valuePairs[i].value);
            if (result === false) {
                break;
            }
        }
    }

    toString() {
        if (this.isEmpty()) {
            return '';
        }
        let keys = Object.keys(this.table);
        let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`
        for (let i = 1; i < keys.length; i++) {
            objString = `${objString},{${keys[i]} => ${this.table[keys[i]].toString()}}`
        }
        return objString;
    }


}

7.2.2 使用HashTable类

我们来写几个测试用例去测试一下HashTable类：

1
2
3
4
5
6
7
8
9
10
11
12
let hash = new HashTable();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'john@email.com');
hash.put('Jack', 'jack@email.com');

console.log(hash.toString())

console.log(hash.get('John'));
console.log(hash.get('Mane'));

hash.remove('John');
console.log(hash.get('John'));

运行结果：

HashTable测试用例.png

7.2.4 处理散列表中的冲突

有时候，一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候，我们称其为冲突。例如我们看看下面的代码会得到怎么样的输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
let hash = new HashTable();

hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'john@email.com');
hash.put('Tyrion', 'tyrion@email.com');
hash.put('Aaron', 'aaron@email.com');
hash.put('Donnie', 'donnie@email.com');
hash.put('Ana', 'ana@email.com');
hash.put('Jamie', 'jamie@email.com');
hash.put('Sue', 'sue@email.com');
hash.put('Mindy', 'mindy@email.com');
hash.put('Paul', 'paul@email.com');
hash.put('Nathan', 'nathan@email.com');

通过对每个提到的名字调用hash.hashCode()方法，输出结果如下：

散列表冲突测试用例结果.png

从结果中可以看到，尽管有些keys不同，但是通过我们提供的散列函数居然得到了相同的hash值，这显然违背了我们的设计原则。在哈希表中，这个叫做散列冲突，为了得到一个可靠的哈希表，我们必须尽可能地避免散列冲突。那如何避免这种冲突呢？这里介绍两种解决冲突的方法：分离链接和线性探查。

7.2.5 分离连接

分离连接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是在HashTable实例之外还需要额外的存储空间。

如图所示（为了简化，图中的值被省略了）：

Image

新的采用了分离链接的HashTableSeparateChaining类可以继承自前面的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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import HashTable from "./HashTable.js";
import LinkedList from "./LinkedList.js";

class ValuePairs {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }

    toString() {
        return `[#${this.key}: ${this.value}]`
    }
}

export default class HashTableSeparateChaining extends HashTable {
    put(key, value) {
        if (key == null && value == null) return false;
        const position = this.hashCode(key);
        // 如果当前位置为空，那就new一个链表进行赋值
        if (this.table[position] == null) {
            this.table[position] = new LinkedList();
        }
        // 往链表中添加元素
        this.table[position].push(new ValuePairs(key, value));
        return true;
    }

    get(key) {
        const position = this.hashCode(key);
        const linkedList = this.table[position];
        // 验证在特定的位置是否有元素存在，且链表不为空
        if (linkedList != null && !linkedList.isEmpty()) {
            let current = linkedList.getHead();
            // 迭代链表元素寻找匹配key
            while (current != null) {
                if (current.element.key === key) {
                    return current.element.value;
                }
                current = current.next;
            }
        }
        return undefined;
    }

    remove(key) {
        const position = this.hashCode(key);
        const linkedList = this.table[position];
        // 验证在特定的位置是否有元素存在，且链表不为空
        if (linkedList != null && !linkedList.isEmpty()) {
            let current = linkedList.getHead();
            // 迭代链表元素寻找匹配key
            while (current != null) {
                if (current.element.key === key) {
                    linkedList.remove(current.element);
                    if (linkedList.isEmpty()) {
                        delete this.table[position];
                    }
                    return true;
                }
                current = current.next;
            }
        }
        return false;
    }

    size() {
        return this.keyValues().length;
    }
    
    keyValues() {
        let valuePairs = [];
        for (let i in this.table) {
            let linkedList = this.table[i];
            if (linkedList === undefined) continue;
            let current = linkedList.getHead();
            while (current) {
                valuePairs.push(current.element)
                current = current.next;
            }
        }
        return valuePairs;
    }

    toString() {
        let objString = "";
        for (let i in this.table) {
            let linkedList = this.table[i];
            if (linkedList === undefined) continue;
            objString += `${i}: `;
            let current = linkedList.getHead();
            while (current) {
                objString += current.element.toString();
                current = current.next;
                if (current) objString += ', ';
            }
            objString += '\r\n';
        }
        return objString;
    }

}

下面是HashTableSeparateChaining类的测试用例及结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
let hash = new HashTableSeparateChaining();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'john@email.com');
hash.put('Tyrion', 'tyrion@email.com');
hash.put('Aaron', 'aaron@email.com');
hash.put('Donnie', 'donnie@email.com');
hash.put('Ana', 'ana@email.com');
hash.put('Jamie', 'jamie@email.com');
hash.put('Sue', 'sue@email.com');
hash.put('Mindy', 'mindy@email.com');
hash.put('Paul', 'paul@email.com');
hash.put('Nathan', 'nathan@email.com');

console.log(hash.toString());
console.log(`size: ${hash.size()}`);
console.log(hash.get('John'));

console.log(hash.remove('Ana'));
console.log(hash.remove('John'));
console.log(hash.toString());

分离连接测试用例.png

7.2.6 线性探查

​ 另一种解决冲突的方法是线性探查。之所以称作线性，是因为它处理冲突的方法是将元素直接存储到表中，而不是在单独的数据结构中。

​ 当想向表中某个位置添加一个新元素的时候，如果索引为position的位置已经被占据了，就尝试position + 1的位置。如果position + 1的位置也被占据了，就尝试position + 2的位置，以此类推，直到散列表中找到一个空闲的位置。

下图展示了这个过程：

Image

​ 当我们从散列表中移除一个键值对的时候，仅仅在所实现位置移除是不够的。如果我们只是移除了元素，就可能在查找有相同的hash（位置）的其它元素时找到一个空的位置，这个会导致算法出现问题。

​ 线性探查技术分为两种。第一种是软删除方法。我们使用一个特殊的值标记来标识键值对被删除了，而不是真的删除它。经过一段时间，散列表被操作过后，我们会得到一个标记了若干删除位置的散列表。这回逐渐降低散列表的效率，因为搜索键值会随时间变得更慢。能快速访问并找到一个键是我们使用散列表的重要原因。下图展示了这个过程：

Image

​ 第二种方法需要检验是否有必要将一个或多个元素移动到之前的位置。当搜索一个键时，这种方法可以避免找到一个空位置。如果移动元素是必要的，我们就需要在散列表中挪动键值对。下图展现了这个过程：

Image

两种方法都各有各的优缺点，我们来实现一下第二种方法：

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
import HashTable, {ValuePairs} from "./HashTable.js";


export default class HashTableLinearProbing extends HashTable {
    put(key, value) {
        if (key == null && value == null) return false;
        const position = this.hashCode(key);
        if (this.table[position] == null) {
            this.table[position] = new ValuePairs(key, value);
        } else {
            let index = position + 1;
            while (this.table[index] != null) {
                index++;
            }
            this.table[index] = new ValuePairs(key, value);
        }
        return true;
    }

    get(key) {
        const position = this.hashCode(key);
        if (this.table[position] != null) {
            if (this.table[position].key === key) {
                return this.table[position].value;
            } else {
                let index = position + 1;
                while (this.table[index] != null && this.table[index].key !== key) {
                    index++;
                }
                if (this.table[index] != null && this.table[index].key === key) {
                    return this.table[index].value;
                }
            }
        }
        return undefined;
    }

    remove(key) {
        const position = this.hashCode(key);
        if (this.table[position] != null) {
            if (this.table[position].key === key) {
                delete this.table[position];
                this._verifyRemoveSideEffect(key, position);
                return true;
            }
            let index = position + 1;
            while (this.table[index] != null && this.table[index].key !== key) {
                index++;
            }
            if (this.table[index] != null && this.table[index].key === key) {
                delete this.table[index];
                this._verifyRemoveSideEffect(key, index);
                return true;
            }
        }
        return false;
    }

    _verifyRemoveSideEffect(key, removedPosition) {
        const hash = this.hashCode(key);
        let index = removedPosition + 1;
        while (this.table[index] != null) {
            const posHash = this.hashCode(this.table[index].key);
            if (posHash <= hash || posHash <= removedPosition) {
                this.table[removedPosition] = this.table[index];
                delete this.table[index];
                removedPosition = index;
            }
            index++;
        }
    }
}

我们来写一下测试用例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
let hash = new HashTableLinearProbing();
hash.put('Ygritte', 'ygritte@email.com');
hash.put('Jonathan', 'jonathan@email.com');
hash.put('Jamie', 'jamie@email.com');
hash.put('Jack', 'jack@email.com');
hash.put('Jasmine', 'jasmine@email.com');
hash.put('Jake', 'jake@email.com');
hash.put('Nathan', 'nathan@email.com');
hash.put('Athelstan', 'athelstan@email.com');
hash.put('Sue', 'sue@email.com');
hash.put('Aethelwulf', 'aethelwulf@email.com');
hash.put('Sargeras', 'sargeras@email.com');

console.log(hash.toString());

hash.remove('Jonathan');

console.log('删除Jonathan后：')
console.log(hash.toString());

运行结果如下：

线性探查测试用例.png