本文共 7245 字，大约阅读时间需要 24 分钟。
前言
如果你研究过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 = []; //初始数组长度为16 var length = 2 << 3; //数组扩容临界值为12 var threshold = 0.75 * length; //hash值计算 this.hash = function(h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } //返回HashMap的size this.size = function(){ return size; } //是否包含某个key this.containsKey = function(key) { if(key == null || key == undefined) return false; else { var hashCode = this.hashCode(key); var hash = this.hash(hashCode); var index = this.indexFor(hash, length) for(var e = table[index]; e != null && e != undefined; e = e.next){ if(e.key === key){ return true; } } return false; } } //是否包含某个value this.containsValue = function(value) { for(var index = 0; index < table.length; index++) { for (var e = table[index]; e != null && e != undefined; e = e.next) { if (JSON.stringify(e.value) === JSON.stringify(value)) { return true; } } } return false; } //HashMap是否为空 this.isEmpty = function(){ return size === 0; } //计算HashCode值，不同的key有不同的HashCode，这里使用字符串转ASCII码并拼接的方式 this.hashCode = function(key){ var hashcode = ''; for(var i=0 ;i< key.length; i++){ hashcode += key.charCodeAt(i); } return hashcode; } //向HashMap中存放值 this.put = function(key, value){ if(key == null || key == undefined) return var hashCode = this.hashCode(key); var hash = this.hash(hashCode); var index = this.indexFor(hash, length) for(var e = table[index]; e != null && e != undefined; e = e.next){ if(e.key === key){ var oldValue = e.value; e.value = value; return oldValue; } } this.addEntry(key, value, index) } //从HashMap中获取值 this.get = function(key){ if(key == null || key == undefined) return undefined var hashCode = this.hashCode(key); var hash = this.hash(hashCode); var index = this.indexFor(hash, length) for(var e = table[index]; e != null && e != undefined; e = e.next){ if(e.key === key){ return e.value; } } return undefined; } //从HashMap中删除值 this.remove = function(key){ if(key == null || key == undefined) return undefined var hashCode = this.hashCode(key); var hash = this.hash(hashCode); var index = this.indexFor(hash, length) var prev = table[index]; var e = prev; while(e != null && e!= undefined){ var next = e.next; if(e.key === key){ size--; if(prev == e){ table[index] = next; } else{ prev.next = next; } return e; } prev = e; e = next; } return e == null||e == undefined? undefined: e.value; } //清空HashMap this.clear = function() { table = []; // 设置size为0 size = 0; length = 2 << 3; threshold = 0.75 * length; } //根据hash值获取数据应该存放到数组的哪个桶(下标)中 this.indexFor = function(h, length) { return h & (length-1); } //添加一个新的桶来保存key和value this.addEntry = function(key, value, bucketIndex) { // 保存对应table的值 var e = table[bucketIndex]; // 然后用新的桶套住旧的桶，链表 table[bucketIndex] = { key: key, value: value, next: e} // 如果当前size大于等于阈值 if (size++ >= threshold) // 调整容量 { length = length << 1; threshold = 0.75 * length; } } //获取HashMap中所有的键值对 this.getEntries = function(){ var entries = []; for(var index = 0; index < table.length; index++) { for (var e = table[index]; e != null && e != undefined; e = e.next) { entries.push({key: e.key, value: e.value}) } } return entries; }} 其中hashcode这个函数，就是把key值的每个字符转换成ASCII码并且拼接的过程。这样可以保证当key值不同的时候，生成的字符串肯定也不相同。而hash这个函数则与Java中的HashMap源码中的hash方法完全相同。通过得到的这个hash值与数组的当前长度进行与运算，获取到我们要put的键值对应该放置在数组的哪个下标之中。
我们可以观察containsValue这个函数，这个函数的作用是判断HashMap中是否有某个value。在这个函数的实现里，有一个对象之间的比较：if (JSON.stringify(e.value) === JSON.stringify(value)) { return true;} 这里使用了JSON对象转字符串并进行比较，对嵌套的对象结构依然有效，不过比较的效率相对来说很低。不过相对于key的比较，value的比较并不会经常被调用，这也解释了之前所说的key只能为字符串，而value可以使任何形式的对象的说法。getEntries函数可以获得HashMap中所有的键值对，这个函数返回一个包含所有键值对的数组，如果想对HashMap进行遍历，那么可以调用这个函数，并且遍历返回的数组就可以了。
测试
测试语句如下：
var hs = new HashMap(); hs.put('asd', 123) hs.put('bqwe', 456) hs.put('czx', 789) hs.put('dcv', {a: 1, b: 2}) hs.put('edf', 123) hs.put('fsdf', 456) hs.put('gdf', 789) hs.put('hds', {a: 1, b: 2}) hs.put('idc', 123) hs.put('jdf', 456) hs.put('ker', 789) hs.put('lsd', [1, 2, 3]) hs.put('mvr', {a: 1, b: 2, c: {d: 2}}) hs.put("vvv", null) hs.put('', 'asdasd') console.log(hs.get('')) console.log(hs.get("qqq")) console.log(hs.containsKey('asd')) console.log(hs.get('asd')) hs.remove('asd') console.log(hs.containsKey('asd')) console.log(hs.containsValue({a: 1, b: 2, c: {d: 2}})) console.log(hs.containsValue(123)) console.log(hs.get('asd')) console.log(hs.size()) var en = hs.getEntries(); console.log(en) en.forEach((item) => { console.log(item.key) console.log(item.value) }) hs.clear(); console.log(hs.isEmpty()) 输出结果：
asdasdundefinedtrue123falsetruetrueundefined14[Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object]asdasdhdsObject {a: 1, b: 2}gdf789jdf456mvrObject {a: 1, b: 2, c: Object}fsdf456dcvObject {a: 1, b: 2}idc123bqwe456lsd[1, 2, 3]czx789ker789edf123vvvnulltrue