Javascript实现Java的HashMap(链表散列)

本文主要是介绍Javascript实现Java的HashMap(链表散列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

如果你研究过Java中HashMap的源码，你就会知道HashMap底层的存储结构。Java中的HashMap是以链表散列的形式存储的，也就是数组+链表：HashMap中有一个Entry数组，默认的数组长度是16。这个值必须是2的整数次幂，以保证在通过key的hash值来计算entry应该放置的数组下标时可以尽量做到平均分配。而Entry数组中的每一个非空Entry都是一个Entry链表的头结点。这样做的好处就是HashMap结合了数组在寻址（查找）上的优势和链表在放置和删除上的优势。当一个链表的长度过长，查询所耗费的时间也在增加，当达到一定阈值的时候，Entry数组就会自动扩容至原来的两倍。这个时候就需要把原数组的所有元素都拷贝至新数组中，这也是HashMap操作过程中一个消耗相对大一些的操作。HashMap的存储结构如下图：

不过在JavaScript中，并没有为我们提供一个类似于HashMap的结构用于存储数据。JavaScript中的数组其实可以被用来当做一个映射集，比如如下语句

var a = new Array(1,2,3);a[-10]="a[-10]";a["sss"]="sss";

都是可以正常运行的，不过有一点需要注意的是，当[]里不是非负整数的时候，该属性并没有被存放到数组中，而是作为这个数组对象的一个属性被存储进来。所以这样的赋值显然也不会改变数组的长度。当上面的语句被执行之后，如果你输出这个数组的长度，则依然会得到3。这显然不是我们想要的结果，所以我们可以参考Java中的HashMap源码来写一个在JavaScript中适用的HashMap。

项目下载地址

正文

在Javascript中，我们仍然以”数组+链表“的链表散列形式来存储HashMap中的数据。这里我们规定key的值必须为字符串，可以为空字符串，但是不能为null或undefined。这样做的原因一是大部分的时间我们都会以字符串作为key，而我们的HashMap计算hash值的方法就是通过计算key值字符串每个字符的ASCII码并拼接获得的；还有一个原因就是Javascript中并不会像Java语言中会为每个不同的对象生成不同的hash值，所以Javascript中对象之间的比较也非常复杂。如果实现了这一功能，在put操作比较key的时候就会非常耗时，违背了HashMap设计的初衷。而对于value的类型并没有限制，可以是任何类型的变量。还有一点值得一提的是，由于Javascript数组本身就不是定容的，即可以通过赋值语句动态的增减数组的长度，所以相对于Java中的HashMap来说，我们将要实现的HashMap在扩容的时候还省去了把原数组中的entry拷贝至新数组的步骤。
下面上代码：

function HashMap(){//初始大小var size = 0;//数组var table = [];//初始数组长度为16var length = 2 << 3;//数组扩容临界值为12var threshold = 0.75 * length;//hash值计算this.hash = function(h) {h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}//返回HashMap的sizethis.size = function(){return size;}//是否包含某个keythis.containsKey =