前言
如果你研究过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())输出结果：
asdasd
undefined
true
123
false
true
true
undefined
14
[Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object]
asdasd
hds
Object {a: 1, b: 2}
gdf
789
jdf
456
mvr
Object {a: 1, b: 2, c: Object}
fsdf
456
dcv
Object {a: 1, b: 2}
idc
123
bqwe
456
lsd
[1, 2, 3]
czx
789
ker
789
edf
123
vvv
null
true
