在本节中，你将会学到HashTable类，也叫HashMap类，它是Dictionary类的一种散列表实现方式。
散列算法的作用是尽可能快地在数据结构中找到一个值。在之前的章节中，你已经知道如果要在数据结构中获得一个值（使用get方法），需要遍历整个数据结构来找到它。如果使用散列函数，就知道值的具体位置，因此能够快速检索到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址。
举个例子，我们继续使用在前一节中使用的电子邮件地址簿。我们将要使用最常见的散列函数——“lose lose”散列函数，方法是简单地将每个键值中的每个字母的ASCII值相加。
7.2.1 创建散列表
我们将使用数组来表示我们的数据结构，该数据结构和上一章中的图表所用的非常相似。
和之前一样，我们从搭建类的骨架开始：
function HashTable { var table = ;} 然后，给类添加一些方法。我们给每个类实现三个基本方法。
put(key,value)：向散列表增加一个新的项（也能更新散列表）。remove(key)：根据键值从散列表中移除值。get(key)：返回根据键值检索到的特定的值。
在实现这三个方法之前，要实现的第一个方法是散列函数，它是HashTable类中的一个私有方法：
var loseloseHashCode = function (key) { var hash = 0; //{1} for (var i = 0; i < key.length; i++) { //{2} hash += key.charCodeAt(i); //{3} } return hash % 37; //{4}}; 给定一个key参数，我们就能根据组成key的每个字符的ASCII码值的和得到一个数字。所以，首先需要一个变量来存储这个总和（行{1}）。然后，遍历key（行{2}）并将从ASCII表中查到的每个字符对应的ASCII值加到hash变量中（可以使用JavaScript的String类中的charCodeAt方法——行{3}）。最后，返回hash值。为了得到比较小的数值，我们会使用hash值和一个任意数做除法的余数（mod）。
要了解更多关于ASCII的信息，请访问http://www.asciitable.com/。
现在，有了散列函数，我们就可以实现put方法了：
this.put = function(key, value) { var position = loseloseHashCode(key); //{5} console.log(position + ' - ' + key); //{6} table[position] = value; //{7}}; 首先，根据给定的key，我们需要根据所创建的散列函数计算出它在表中的位置（行{5}）。为了便于展示信息，我们将计算出的位置输出至控制台（行{6}）。由于它不是必需的，我们也可以将这行代码移除。然后要做的，是将value参数添加到用散列函数计算出的对应的位置上。（行{7}）。
从HashTable实例中查找一个值也很简单。为此，我们将会实现一个get方法：
this.get = function (key) { return table[loseloseHashCode(key)];}; 首先，我们会使用所创建的散列函数来求出给定key所对应的位置。这个函数会返回值的位置，因此我们所要做的就是根据这个位置从数组table中获得这个值。
我们要实现的最后一个方法是remove方法：
this.remove = function(key) { table[loseloseHashCode(key)] = undefined;}; 要从HashTable实例中移除一个元素，只需要求出元素的位置（可以使用散列函数来获取）并赋值为undefined。
对于HashTable类来说，我们不需要像ArrayList类一样从table数组中将位置也移除。由于元素分布于整个数组范围内，一些位置会没有任何元素占据，并默认为undefined值。我们也不能将位置本身从数组中移除（这会改变其他元素的位置），否则，当下次需要获得或移除一个元素的时候，这个元素会不在我们用散列函数求出的位置上。
7.2.2 使用HashTable类
让我们执行一些代码来测试HashTable类：
var hash = new HashTable;hash.put('Gandalf', '[email protected]');hash.put('John', '[email protected]');hash.put('Tyrion', '[email protected]'); 执行上述代码，会在控制台中获得如下输出：
19 - Gandalf29 - John16 - Tyrion 下面的图表展现了包含这三个元素的HashTable数据结构：
现在来测试get方法：
console.log(hash.get('Gandalf'));console.log(hash.get('Loiane')); 获得如下的输出：
[email protected]undefined 由于Gandalf是一个在散列表中存在的键，get方法将会返回它的值。而由于Loiane是一个不存在的键，当我们试图在数组中根据位置获取值的时候（一个由散列函数生成的位置），返回值将会是undefined（即不存在）。
然后，我们试试从散列表中移除Gandalf：
hash.remove('Gandalf');console.log(hash.get('Gandalf')); 由于Gandalf不再存在于表中，hash.get('Gandalf')方法将会在控制台上给出undefined的输出结果。
7.2.3 散列表和散列集合
散列表和散列映射是一样的，我们已经在本章中介绍了这种数据结构。
在一些编程语言中，还有一种叫作散列集合的实现。散列集合由一个集合构成，但是插入、移除或获取元素时，使用的是散列函数。我们可以重用本章中实现的所有代码来实现散列集合，不同之处在于，不再添加键值对，而是只插入值而没有键。例如，可以使用散列集合来存储所有的英语单词（不包括它们的定义）。和集合相似，散列集合只存储唯一的不重复的值。
7.2.4 处理散列表中的冲突
有时候，一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候，我们称其为冲突。例如，我们看看下面的代码会得到怎样的输出结果：
var hash = new HashTable;hash.put('Gandalf', '[email protected]');hash.put('John', '[email protected]');hash.put('Tyrion', '[email protected]');hash.put('Aaron', '[email protected]');hash.put('Donnie', '[email protected]');hash.put('Ana', '[email protected]');hash.put('Jonathan', '[email protected]');hash.put('Jamie', '[email protected]');hash.put('Sue', '[email protected]');hash.put('Mindy', '[email protected]');hash.put('Paul', '[email protected]');hash.put('Nathan', '[email protected]'); 输出结果如下：
19 - Gandalf29 - John16 - Tyrion16 - Aaron13 - Donnie13 - Ana5 - Jonathan5 - Jamie5 - Sue32 - Mindy32 - Paul10 – Nathan 注意，
Tyrion和Aaron有相同的散列值（16）。Donnie和Ana有相同的散列值（13），Jonathan、Jamie和Sue有相同的散列值（5），Mindy和Paul也有相同的散列值（32）。
那HashTable实例会怎样呢？执行之前的代码后散列表中会有哪些值呢？
为了获得结果，我们来实现一个叫作print的辅助方法，它会在控制台上输出HashTable中的值：
this.print = function { for (var i = 0; i < table.length; ++i) { //{1} if (table[i] !== undefined) { //{2} console.log(i + ": " + table[i]);//{3} } }}; 首先，遍历数组中的所有元素（行{1}）。当某个位置上有值的时候（行{2}），会在控制台上输出位置和对应的值（行{3}）。
现在来使用这个方法：
hash.print; 在控制台上得到如下的输出结果：
5: [email protected]10: [email protected]13: [email protected]16: [email protected]19: [email protected]29: [email protected]32: [email protected] Jonathan、Jamie和Sue有相同的散列值，也就是5。由于Sue是最后一个被添加的，Sue将是在HashTable实例中占据位置5的元素。首先，Jonathan会占据这个位置，然后Jamie会覆盖它，然后Sue会再次覆盖。这对于其他发生冲突的元素来说也是一样的。
使用一个数据结构来保存数据的目的显然不是去丢失这些数据，而是通过某种方法将它们全部保存起来。因此，当这种情况发生的时候就要去解决它。处理冲突有几种方法：分离链接、线性探查和双散列法。在本书中，我们会介绍前两种方法。
分离链接
分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是它在
HashTable实例之外还需要额外的存储空间。例如，我们在之前的测试代码中使用分离链接的话，输出结果将会是这样：
在位置5上，将会有包含三个元素的
LinkedList实例；在位置13、16和32上，将会有包含两个元素的LinkedList实例；在位置10、19和29上，将会有包含单个元素的LinkedList实例。对于分离链接和线性探查来说，只需要重写三个方法：
put、get和remove。这三个方法在每种技术实现中都是不同的。为了实现一个使用了分离链接的
HashTable实例，我们需要一个新的辅助类来表示将要加入LinkedList实例的元素。我们管它叫ValuePair类（在HashTable类内部定义）：var ValuePair = function(key, value){ this.key = key; this.value = value; this.toString = function { return '[' + this.key + ' - ' + this.value + ']'; }};这个类只会将
key和value存储在一个Object实例中。我们也重写了toString方法，以便之后在浏览器控制台中输出结果。(1)
put方法我们来实现第一个方法，
put方法，代码如下：this.put = function(key, value){ var position = loseloseHashCode(key); if (table[position] == undefined) { //{1} table[position] = new LinkedList; } table[position].append(new ValuePair(key, value)); //{2}};在这个方法中，将验证要加入新元素的位置是否已经被占据（行
{1}）。如果这个位置是第一次被加入元素，我们会在这个位置上初始化一个LinkedList类的实例（你已经在第5章中学习过）。然后，使用第5章中实现的append方法向LinkedList实例中添加一个ValuePair实例（键和值）（行{2}）。(2)
get方法然后，我们实现用来获取特定值的
get方法：this.get = function(key) { var position = loseloseHashCode(key); if (table[position] !== undefined){ //{3} //遍历链表来寻找键/值 var current = table[position].getHead; //{4} while(current.next){ //{5} if (current.element.key === key){ //{6} return current.element.value; //{7} } current = current.next; //{8} } //检查元素在链表第一个或最后一个节点的情况 if (current.element.key === key){ //{9} return current.element.value; } } return undefined; //{10}};我们要做的第一个验证，是确定在特定的位置上是否有元素存在（行
{3}）。如果没有，则返回一个undefined表示在HashTable实例中没有找到这个值（行{10}）。如果在这个位置上有值存在，我们知道这是一个LinkedList实例。现在要做的是遍历这个链表来寻找我们需要的元素。在遍历之前先要获取链表表头的引用（行{4}），然后就可以从链表的头部遍历到尾部（行{5}，current.next将会是null）。Node链表包含next指针和element属性。而element属性又是ValuePair的实例，所以它又有value和key属性。可以通过current.element.key来获得Node链表的key属性，并通过比较它来确定它是否就是我们要找的键（行{6}）。（这就是要使用ValuePair这个辅助类来存储元素的原因。我们不能简单地存储值本身，这样就不能确定哪个值对应着特定的键。）如果key值相同，就返回Node的值（行{7}）；如果不相同，就继续遍历链表，访问下一个节点（行{8}）。如果要找的元素是链表的第一个或最后一个节点，那么就不会进入
while循环的内部。因此，需要在行{9}处理这种特殊的情况。(3)
remove方法使用分离链接法从
HashTable实例中移除一个元素和之前在本章实现的remove方法有一些不同。现在使用的是链表，我们需要从链表中移除一个元素。来看看remove方法的实现：this.remove = function(key){ var position = loseloseHashCode(key); if (table[position] !== undefined){ var current = table[position].getHead; while(current.next){ if (current.element.key === key){ //{11} table[position].remove(current.element); //{12} if (table[position].isEmpty){ //{13} table[position] = undefined; //{14} } return true; //{15} } current = current.next; } // 检查是否为第一个或最后一个元素 if (current.element.key === key){ //{16} table[position].remove(current.element); if (table[position].isEmpty){ table[position] = undefined; } return true; } } return false; //{17}};在
remove方法中，我们使用和get方法一样的步骤找到要找的元素。遍历LinkedList实例时，如果链表中的current元素就是要找的元素（行{11}），使用remove方法将其从链表中移除。然后进行一步额外的验证：如果链表为空了（行{13}——链表中不再有任何元素了），就将散列表这个位置的值设为undefined（行{14}），这样搜索一个元素或打印它的内容的时候，就可以跳过这个位置了。最后，返回true表示这个元素已经被移除（行{15}）或者在最后返回false表示这个元素在散列表中不存在（行{17}）。同样，需要和get方法一样，处理元素在第一个或最后一个的情况（行{16}）。重写了这三个方法后，我们就拥有了一个使用了分离链接法来处理冲突的
HashMap实例。线性探查
另一种解决冲突的方法是线性探查。当想向表中某个位置加入一个新元素的时候，如果索引为index的位置已经被占据了，就尝试index+1的位置。如果index+1的位置也被占据了，就尝试index+2的位置，以此类推。
put方法让我们继续实现需要重写的三个方法。第一个是
put方法：this.put = function(key, value){ var position = loseloseHashCode(key); // {1} if (table[position] == undefined) { // {2} table[position] = new ValuePair(key, value); // {3} } else { var index = ++position; // {4} while (table[index] != undefined){ // {5} index++; // {6} } table[index] = new ValuePair(key, value); // {7} }};和之前一样，先获得由散列函数生成的位置（行
{1}），然后验证这个位置是否有元素存在（如果这个位置被占据了，将会通过行{2}的验证）。如果没有元素存在，就在这个位置加入新元素（行{3}——一个ValuePair的实例）。如果这个位置已经被占据了，需要找到下一个没有被占据的位置（
position的值是undefined），因此我们声明一个index变量并赋值为position+1（行{4}——在变量名前使用自增运算符++会先递增变量值然后再将其赋值给index）。然后验证这个位置是否被占据（行{5}），如果被占据了，继续将index递增（行{6}），直到找到一个没有被占据的位置。然后要做的，就是将值分配到这个位置（行{7}）。在一些编程语言中，我们需要定义数组的大小。如果使用线性探查的话，需要注意的一个问题是数组的可用位置可能会被用完。在JavaScript中，我们不需要担心这个问题，因为我们不需要定义数组的大小，它可以根据需要自动改变大小——这是JavaScript内置的一个功能。
如果再次执行7.2.4节中插入数据的代码，下图展示使用了线性探查的散列表的最终结果：
让我们来模拟一下散列表中的插入操作。
(1) 试着插入Gandalf。它的散列值是19，由于散列表刚刚被创建，位置19还是空的——可以在这里插入数据。
(2) 试着在位置29插入John。它也是空的，所以可以插入这个姓名。
(3) 试着在位置16插入Tyrion。它是空的，所以可以插入这个姓名。
(4) 试着插入Aaron，它的散列值也是16。位置16已经被Tyrion占据了，所以需要检查索引值为position+1的位置（16+1）。位置17是空的，所以可以在位置 17插入Aaron。
(5) 接着，试着在位置13插入Donnie。它是空的，所以可以插入这个姓名。
(6) 想在位置13插入Ana，但是这个位置被占据了。因此在位置14进行尝试，它是空的，所以可以在这里插入姓名。
(7) 然后，在位置5插入Jonathan，这个位置是空的，所以可以插入这个姓名。
(8) 试着在位置5插入Jamie，但是这个位置被占了。所以跳至位置6，这个位置是空的，因此可以在这个位置插入姓名。
(9) 试着在位置5插入Sue，但是位置被占据了。所以跳至位置6，但也被占了。接着跳至位置7，这里是空的，所以可以在这里插入姓名。以此类推。
get方法现在插入了所有的元素，让我们实现
get方法来获取它们的值吧：this.get = function(key) { var position = loseloseHashCode(key); if (table[position] !== undefined){ //{8} if (table[position].key === key) { //{9} return table[position].value; //{10} } else { var index = ++position; while (table[index] === undefined || table[index].key !== key){ //{11} index++; } if (table[index].key === key) { //{12} return table[index].value; //{13} } } } return undefined; //{14}};要获得一个键对应的值，先要确定这个键存在（行
{8}）。如果这个键不存在，说明要查找的值不在散列表中，因此可以返回undefined（行{14}）。如果这个键存在，需要检查我们要找的值是否就是这个位置上的值（行{9}）。如果是，就返回这个值（行{10}）。如果不是，就在散列表中的下一个位置继续查找，直到找到一个键值与我们要找的键值相同的元素（行
{11}）。然后，验证一下当前项就是我们要找的项（行{12}——只是为了确认一下）并且将它的值返回（行{13}）。我们无法确定要找的元素实际上在哪个位置，这就是使用
ValuePair来表示HashTable元素的原因。remove方法remove方法和get方法基本相同，不同之处在于行{10}和{13}，它们将会由下面的代码代替：table[index] = undefined;要移除一个元素，只需要给其赋值为
undefined，来表示这个位置不再被占据并且可以在必要时接受一个新元素。
7.2.5 创建更好的散列函数
我们实现的“lose lose”散列函数并不是一个表现良好的散列函数，因为它会产生太多的冲突。如果我们使用这个函数的话，会产生各种各样的冲突。一个表现良好的散列函数是由几个方面构成的：插入和检索元素的时间（即性能），当然也包括较低的冲突可能性。我们可以在网上找到一些不同的实现方法，或者也可以实现自己的散列函数。
另一个可以实现的比“lose lose”更好的散列函数是djb2：
var djb2HashCode = function (key) { var hash = 5381; //{1} for (var i = 0; i < key.length; i++) { //{2} hash = hash * 33 + key.charCodeAt(i); //{3} } return hash % 1013; //{4}}; 它包括初始化一个hash变量并赋值为一个质数（行{1}——大多数实现都使用5381），然后迭代参数key（行{2}），将hash与33相乘（用来当作一个魔力数），并和当前迭代到的字符的ASCII码值相加（行{3}）。
最后，我们将使用相加的和与另一个随机质数（比我们认为的散列表的大小要大——在本例中，我们认为散列表的大小为1000）相除的余数。
如果再次执行7.2.4节中插入数据的代码，这将是使用djb2HashCode代替loseloseHash Code的最终结果：
798 - Gandalf838 - John624 - Tyrion215 - Aaron278 - Donnie925 - Ana288 - Jonathan962 - Jamie502 - Sue804 - Mindy54 - Paul223 - Nathan 没有冲突！
这并不是最好的散列函数，但这是最受社区推崇的散列函数之一。
也有一些为数字键值准备的散列函数，你可以在http://goo.gl/VtdN2x找到一系列的实现。