数据结构学习字典和散列表

集合、字典和散列表都可以存储不重复的值。在集合中，存储的是每个值本身。而在字典中，存储的是键值对（也称作字典映射）。在散列表中存储的也是键值对（也称作散列映射），但是两种数据结构的实现方式略有不同 ### 字典 ES6提供了Map类，也就是上面说的字典，Map类的具体操作可[移步至此](https://blog.86886.wang/posts/5b2324f88493c32a8e81fc99) ### 散列表 散列表也叫 HashTable 类，或者 HashMap 类，它是字典的一种散列表实现方式。要想创建散列表，需要先实现散列算法，散列算法的作用是尽可能快地在数据结构中找到一个值。在之前实现的数据结构中，获取一个值需要遍历整个数据结构，找到匹配项返回结果。如果使用散列函数，就可以知道值的具体位置，因此能够快速检索到该值，散列函数的作用是给定一个键值，然后返回值在表中的地址 #### 散列函数 ```js var loseloseHashCode = function (key) { var hash = 0; for (var i = 0; i < key.length; i++) { hash += key.charCodeAt(i); //每个字符的ASCII码值的和 } return hash % 37; // 为了得到比较小的数值，使用hash值和一个任意数做除法，求余数 }; ``` 这个散列函数接收一个key值，计算key值对应ASCII码值的和，然后返回一个计算后hash值。 #### 创建散列表 散列表要实现以下基本方法 ``` put(key,value) ：向散列表增加一个新的项（也能更新散列表） remove(key) ：根据键值从散列表中移除值 get(key) ：返回根据键值检索到的特定的值 ``` ```js function HashTable() { var table = []; // 新添加的元素在数组内部是用 位置:值 形式存储的 this.put = function(key, value) { var position = loseloseHashCode(key); console.log(position + ' - ' + key); table[position] = value; } // 基于位置查找元素 this.get = function (key) { return table[loseloseHashCode(key)]; }; // 移除元素只需要求出元素的位置，并赋值为undefined // 这里不能像数组一样直接删除，因为会把位置信息也删除 this.remove = function(key) { table[loseloseHashCode(key)] = undefined; } } ``` #### 使用 HashTable 类 ```js var hash = new HashTable(); hash.put('Gandalf', 'gandalf@email.com'); hash.put('John', 'johnsnow@email.com'); hash.put('Tyrion', 'tyrion@email.com'); // 19 - Gandalf // 29 - John // 16 - Tyrion ``` 散列表内部存储示意图  #### 散列表中的冲突 其实上面实现的散列表是有问题的，因为散列函数是基于ASCLL码计算的，这么做很容易导致由于码值相同而冲突。比如`Tyrion`和`Aaron`的计算结果都是16，但很显然这是两个不同的信息。 一个解决方法是使用线性探索，当向表中某个位置加入一个新元素的时候，如果索引为index的位置已经被占据了，就尝试index+1的位置。如果index+1的位置也被占据了，就尝试index+2的位置，以此类推。 具体实现 ```js // 把key和value保存为一个独立的对象 var ValuePair = function(key, value) { this.key = key; this.value = value; // 重写toString，方便查看执行结果 this.toString = function() { return '[' + this.key + ' - ' + this.value + ']'; } } function HashTable() { var table = []; this.put = function(key, value) { var position = loseloseHashCode(key); if (table[position] == undefined) { // 位置没有被占用 table[position] = new ValuePair(key, value); } else { // 位置被占用，hash值进行递增 var index = ++position; while (table[index] != undefined) { index++; } table[index] = new ValuePair(key, value); } }; this.get = function(key) { var position = loseloseHashCode(key); if (table[position] !== undefined) { // 找到元素后，需要判断下key值是否正确 if (table[position].key === key) { return table[position].value; } else { var index = ++position; while (table[index] === undefined || table[index].key !== key) { index++; } if (table[index].key === key) { return table[index].value; } } } return undefined; }; this.remove = function(key) { var position = loseloseHashCode(key); if (table[position] !== undefined) { if (table[position].key === key) { table[index] = undefined; // 赋值undefined } else { var index = ++position; while (table[index] === undefined || table[index].key !== key) { index++; } if (table[index].key === key) { table[index] = undefined; // 赋值undefined } } } return undefined; }; this.print = function() { for (var i = 0; i < table.length; ++i) { if (table[i] !== undefined) { console.log(i + ": " + table[i]); // 字符串拼接会调用对象的toString方法 } } }; } ``` 测试结果 ```js var hash = new HashTable(); hash.put('John', 'johnsnow@email.com'); hash.put('Tyrion', 'tyrion@email.com'); hash.put('Aaron', 'aaron@email.com'); hash.print() // 16: [Tyrion - tyrion@email.com] // 17: [Aaron - aaron@email.com] // 29: [John - johnsnow@email.com] ```