数据结构：字典与哈希表详解

### 数据结构：字典与哈希表详解 #### 1. 集合操作的差异与简化语法 集合的交集函数和差集函数存在一定差异。差集函数旨在添加集合A有而集合B没有的不同元素。我们可以用更简洁的语法来表示差集函数，示例代码如下： ```javascript differenceAB = new Set([x for (x of setA) if (!setB.has(x))]); ``` 不过需要注意的是，目前只有Firefox浏览器支持这种简化语法代码。但差集函数在所有支持ES6的现代浏览器中都可以执行。 #### 2. 字典数据结构 - **字典的概念**：集合是由不同元素组成的集合，而字典则用于存储`[键, 值]`对，其中键用于查找特定元素。字典与集合类似，集合存储的是`[键, 键]`元素集合，而字典存储的是`[键, 值]`元素集合，字典也被称为映射。 - **创建字典**：类似于集合类，ECMAScript 6中也有Map类的实现，也就是字典。下面是自定义`Dictionary`类的骨架代码： ```javascript function Dictionary(){ var items = {}; } ``` 与集合类类似，我们将元素存储在一个对象实例中，而非数组。 - **字典的方法**： - `set(key,value)`：向字典中添加新项。 - `delete(key)`：使用键从字典中移除值。 - `has(key)`：如果键存在于字典中则返回`true`，否则返回`false`。 - `get(key)`：返回通过键搜索到的特定值。 - `clear()`：移除字典中的所有项。 - `size()`：返回字典中元素的数量，类似于数组的`length`属性。 - `keys()`：返回字典中所有键的数组。 - `values()`：返回字典中所有值的数组。 以下是部分方法的具体实现代码： ```javascript this.has = function(key){ return key in items; }; this.set = function(key, value){ items[key] = value; }; this.delete = function(key){ if (this.has(key)){ delete items[key]; return true; } return false; }; this.get = function(key) { return this.has(key) ? items[key] : undefined; }; this.values = function(){ var values = []; for (var k in items) { if (this.has(k)) { values.push(items[k]); } } return values; }; this.keys = function(){ return Object.keys(items); }; this.getItems = function(){ return items; } ``` - **使用字典类**：我们可以创建`Dictionary`类的实例，并添加一些电子邮件地址来模拟电子邮件地址簿。示例代码如下： ```javascript var dictionary = new Dictionary(); dictionary.set('Gandalf', '[email protected]'); dictionary.set('John', '[email protected]'); dictionary.set('Tyrion', '[email protected]'); console.log(dictionary.has('Gandalf')); console.log(dictionary.size()); console.log(dictionary.keys()); console.log(dictionary.values()); console.log(dictionary.get('Tyrion')); dictionary.delete('John'); console.log(dictionary.keys()); console.log(dictionary.values()); console.log(dictionary.getItems()); ``` 上述代码展示了如何使用字典类的各种方法，包括添加元素、检查元素是否存在、获取元素数量、获取键和值的数组等操作。 #### 3. 哈希表数据结构 - **哈希表的概念**：哈希表（也称为HashMap）是字典类的哈希实现。哈希的目的是在最短时间内找到数据结构中的值。传统的数据结构在获取值时需要遍历整个结构，而使用哈希函数可以直接知道值所在的位置，从而快速检索。哈希函数根据给定的键返回表中值所在的地址。 - **创建哈希表**：我们使用数组来表示哈希表的数据结构。以下是`HashTable`类的骨架代码： ```javascript function HashTable() { var table = []; } ``` - **哈希表的方法**： - `put(key,value)`：向哈希表中添加新项（也可用于更新）。 - `remove(key)`：使用键从哈希表中移除值。 - `get(key)`：返回通过键搜索到的特定值。 在实现这些方法之前，需要先实现哈希函数，以下是`loseloseHashCode`哈希函数的代码： ```javascript var loseloseHashCode = function (key) { var hash = 0; for (var i = 0; i < key.length; i++) { hash += key.charCodeAt(i); } ```