数组
HashMap底层本质上是一个固定长度的数组
根据Key定位到数组
HashMap的“hash”其实就是对key做哈希，比如将所有字符的charCode加起来然后再除以数组长度后取模（只是举个简单的例子，比一定要用这种算法，无论用那种算法，都会尽量保证当key足够多时，哈希后的结果能正态分布）。这样无论传什么key最终都会被转换成某一个数组下标，并且相同的key两次调用时获得的数组下标肯定是一样的。
class HashMap {
/** @type {*[]} */
_array = [];
/** @type {number} */
_size = 0;
constructor(size = 8) {
if (size < 1) {
throw new Error("size error")
}
this._size = size;
this._array = new Array(size);
this._array.fill(null);
}
put(key, value) {
const index = this._hashCode(key);
this._array[index] = value;
}
get(key) {
const index = this._hashCode(key);
return this._array[index];
}
_hashCode(str) {
//这里只是举个简单的例子，将所有的字符相加得出一个数字再取模
str = String(str);
let n = 0;
let i = str.length - 1;
while (i--) {
n += str.charCodeAt(i);
}
return n % this._size;
}
}
处理碰撞的问题
由于数组的长度是固定的，当key足够多的时候会出现两个key共用同一个数组下标的问题，比如长度为8的map，如果key为9或17最终都会定位到数组下标为1的位置上。这时就要引入单向链表的逻辑。
当往数组中存数据时，除了将value存进去还要将原始的key也存进去，同时要加一个next字段，如果发生了碰撞，第二个key不会直接存到数组里，而是将之前那条数据的next指向它。
当查询时获取到数组下标后先从数组中取到数据，然后再判断原始key和传进来的key是否一致，如果不一致再判断next的key是否一致，直到找到一致的或没有next
class HashMap {
/** @type {HashMap.HashMapEntity[]} */
_array = [];
/** @type {number} */
_size = 0;
/** @type {number} map中的key数量 */
length = 0;
constructor(size = 8) {/*...*/}
put(key, value) {
const index = this._hashCode(key);
let entity = this._array[index];
if (entity === null) {
//数组中这个位置是空的
this._array[index] = new HashMap.HashMapEntity(key, value);
} else {
//数组中这个位置已经有东西了
do {
if (entity.key === key) {
entity.value = value;
return false;//key已存在，直接更新value
}
} while (entity.next !== null && (entity = entity.next));
//循环结束没有发现相同的key，则创建一个新的实体并挂到链表的末尾
entity.next = new HashMap.HashMapEntity(key, value);
}
this.length++; //key不存在，添加了新值
return true;
}
get(key) {
const index = this._hashCode(key);
let entity = this._array[index];
while (entity !== null) {
if (entity.key === key) {
return entity.value;
} else {
entity = entity.next;
}
}
return undefined;
}
_hashCode(str) {/*...*/}
static HashMapEntity = class {
/** @type {string} */
key;
/** @type {HashMap.HashMapEntity} */
next = null;
/** @type {*} */
value;
constructor(key, data) {
this.key = key;
this.value = data;
}
}
}
效率与扩容
如果数组的长度很小，但是插入的key很多，这时就会出现大量的碰撞，虽然通过链表解决了这个问题，但是当链表长度很长时，插入和查询都会很慢，因为每次都要从链表的头开始查，最倒霉的情况要遍历整个链表才知道是否存在。
这时我们可以对数组进行扩容，这样碰撞的概率就会小很多。
因为扩容后数组的长度发生了改变，因此原有的哈希值对应的数组下标也有可能发生改变。比如数组长度为8时key为9和17时都对应的数组下标1，但是当数组长度扩充到16时，key为9时对应的数组下标变成了9。
因此扩容后我们还需要重排数据。这就意味着每次扩容可能会产生很大的开销，所以java的代码规范里要求在使用HashMap时最好预判数据量在初始化时指定好数组的长度，避免在运行的过程中反复扩容。在使用其它语言开发时如果hashMap/map/dictionary之类的如果能指定初始长度，最好也可以预判一下然后设置好初始值。
class HashMap {
/** @type {HashMap.HashMapEntity[]} */
_array = [];
/** @type {number} */
_size = 0;
/** @type {number} map中的key数量 */
length = 0;
constructor(size = 8) {/*...*/}
put(key, value) {
const index = this._hashCode(key);
let entity = this._array[index];
/*...省略略中间代码...*/
this.length++; //key不存在，添加了新值
if(this.length > this._size * 0.75) {
// 当数据量超过预设长度的75%时进行扩容
this._resize();
}
return true;
}
get(key) {/*...*/}
_hashCode(str) {/*...*/}
_resize() {
this.length = 0;
const oldArray = this._array;
// 创建新的，长度翻倍的数组
this._size = this._size * 2;
this._array = new Array(this._size);
this._array.fill(null);
// 遍历旧数组和链表，将每一对key/value复制到新数组中
oldArray.forEach(entity => {
while (entity !== null) {
this.put(entity.key, entity.value);
entity = entity.next;
}
})
}
static HashMapEntity = class {/*...*/}
}
附：完整实现
class HashMap {
/**
* @type {number}
* @private
*/
_size;
/**
* @type {HashMap.HashMapEntity[]}
* @private
*/
_array;
/**
* map的长度（key的数量）
* @type {number}
* @private
*/
_length = 0;
/**
* map的长度（key的数量）
* @return {number}
*/
get length(){
return this._length;
}
constructor(size = 8) {
if (size < 1) {
throw new Error("size error")
}
this._size = size;
this._array = new Array(size);
this._array.fill(null);
}
/**
* @param {string} key
* @param {*} value
*/
put(key, value) {
if (this._put(key, value)) {
if (++this._length > this._size * .75) {
this._resize()
}
}
}
/**
* @param {string} key
* @param {*} value
* @return {boolean}
* @private
*/
_put(key, value) {
const index = this._hashCode(key);
let entity = this._array[index];
if (entity === null) {
this._array[index] = new HashMap.HashMapEntity(key, value);
} else {
do {
if (entity.key === key) {
entity.value = value;
return false;
}
} while (entity.next !== null && (entity = entity.next));
entity.next = new HashMap.HashMapEntity(key, value);
}
return true;
}
/**
*
* @param {string} key
* @return {*}
*/
get(key) {
const index = this._hashCode(key);
let entity = this._array[index];
while (entity !== null) {
if (entity.key === key) {
return entity.value;
} else {
entity = entity.next;
}
}
return undefined;
}
/**
*
* @param {string} key
* @return {boolean}
*/
keyExists(key) {
const index = this._hashCode(key);
let entity = this._array[index];
while (entity !== null) {
if (entity.key === key) {
return true;
} else {
entity = entity.next;
}
}
return false;
}
/**
*
* @param {string} key
* @return {boolean}
*/
delete(key) {
const index = this._hashCode(key);
/** @type {HashMap.HashMapEntity} */
let current = this._array[index];
/** @type {HashMap.HashMapEntity} */
let prev = null;
while (current !== null) {
if (current.key === key) {
if (prev === null) {
if (current.next !== null) {
this._array[index] = current.next;
} else {
this._array[index] = null;
}
} else {
prev.next = current.next
}
this._length--;
return true;
} else {
prev = current;
current = current.next;
}
}
return false;
}
/**
* 数组扩容
* @private
*/
_resize() {
const oldArray = this._array;
this._size <<= 1;
this._array = new Array(this._size);
this._array.fill(null);
oldArray.forEach(entity => {
while (entity !== null) {
this._put(entity.key, entity.value);
entity = entity.next;
}
})
}
/**
* 计算哈希值
* @param {string} str
* @return {number}
* @private
*/
_hashCode(str) {
str = String(str);
let n = 0;
let i = str.length - 1;
while (i--) {
n += str.charCodeAt(i);
}
return n % this._size;
}
static HashMapEntity = class {
/**
* @type {string}
*/
key;
/**
* @type {HashMap.HashMapEntity}
*/
next = null;
/**
* @type {*}
*/
value;
constructor(key, data) {
this.key = key;
this.value = data;
}
}
}