js实现 hashMap

js实现 hashMap

已有 354 次阅读  2012-09-27 17:03   标签:  ? 

001	var hash_map = function () {

002

003	var hash_table_length = 1024 * 1024; //2的幂次方

004	var hash_table = new Array(hash_table_length); //hashTable表

005	var total_size = 0; //总长度

006

007

/*

008	* 新增hashmap值

009

* 参数：

010	* key  : key值

011	* value: 原始Value值

012

*/

013	this.put = function (key, value) {

014	if (key != null) {

015	var hash = hashCode(key); //进过hashCode，将key转化成整型

016	var index = indexFor(hash, hash_table.length);

017	//从冲突链表中查询KEY键是否存在，存在的话覆盖新值

018	for (var obj = hash_table[index]; obj != null; obj = obj.next) {

019	if (obj.hash == hash && obj.key == key) {

020	obj.value = value;

021	return obj.value;

022

}

023

}

024	addEntry(hash, key, value, index);

025

}

026	return false;

027

}

028

029

/*

030	* 获取hashmap对应值

031

* 参数：

032	* key  : key值

033

*/

034	this.get = function (key) {

035	if (key != null) {

036	var hash = hashCode(key); //进过hashCode，将key转化成整型

037	var index = indexFor(hash, hash_table.length);

038	for (var obj = hash_table[index]; obj != null; obj = obj.next) {

039	if (obj.hash == hash && obj.key == key) {

040	return obj.value;

041

}

042

}

043

}

044	return false;

045

}

046

047

/*

048	* 删除一个hash值

049

* 参数：

050	* key  : key值

051

*/

052	this.remove = function (key) {

053	if (key != null) {

054	var hash  = hashCode(key); //进过hashCode，将key转化成整型

055	var index = indexFor(hash, hash_table.length);

056	var entry = hash_table[index];

057	var e = entry;

058	while (e != null) { //循环跑链表,将需要删除值的next对象放到前一个对象的next中

059	var next = e.next;

060	if (e.hash == hash && e.key == key) {

061	if (entry == e) {

062	hash_table[index] = next;

063

} else {

064	entry.next = next;

065

}

066	total_size--;

067	return true;

068

}

069	entry = e;

070

e = next;

071

}

072

}

073	return false;

074

}

075

076

/*

077	* 清空hashtable操作

078

* 参数：

079	* key  : key值

080

*/

081	this.clear = function () {

082	hash_table = null;

083	hash_table = new Array(hash_table_length);

084	total_size = 0;

085	return hash_table;

086

}

087

088

/*

089	* 判断KEY值是否存在

090

* 参数：

091	* key  : key值

092

*/

093	this.isSet = function (key) {

094	if (key != null) {

095	var hash = hashCode(key); //进过hashCode，将key转化成整型

096	var index = indexFor(hash, hash_table.length);

097	for (var obj = hash_table[index]; obj != null; obj = obj.next) {

098	if (obj.hash == hash && obj.key == key) {

099	return true;

100

}

101

}

102

}

103	return false;

104

}

105

106

/*

107	* 返回hashMap长度

108

*/

109	this.size = function () {

110	return total_size;

111

}

112

113

/*

114	* 解决hash冲突的链表结构

115

* 参数：

116	* hash : hash值，key经过hashCode的值

117	* key  : key值

118	* value: 原始Value值

119	* index: hashTable 索引值

120

*/

121	var addEntry = function (hash, key, value, index) {

122	var entry = hash_table[index];

123	var item  = {

124	"hash"  : hash,

125	"key"   : key,

126	"value" : value,

127	"next"  : entry

128

};

129	hash_table[index] = item;

130	total_size++; //统计数据表总长度

131

}

132

133

/*

134	*  经过该函数得到 哈希表 哈希地址

135

*/

136	var indexFor = function (hash, length) {

137	return hash & (length - 1);

138

}

139

140

/*

141	*  通过hashCode函数，将key转化成整型

142

*/

143	var hashCode = function (key) {

144	var h = 0, off = 0;

145	var length = key.length;

146	for (var i = 0; i < length; i++) {

147	var temp = key.charCodeAt(off++);

148	h = 31 * h + temp;

149	if (h > 0x7fffffff || h < 0x80000000) {

150	h = h & 0xffffffff;

151

}

152

}

153	h ^= (h >>> 20) ^ (h >>> 12);

154	return h ^ (h >>> 7) ^ (h >>> 4);

155

};

156

}

未实现自动扩容，初始化的时候，hashTable设置大点就行了，自动扩容可能会有很大效率问题

通过对key值进行hash成一个整型，并且作&与操作，将key值hash到hashTable数组中的一个值中

对于hash出来的值冲突的情况，实现了链表结构

主要参照java hashMap实现

思考：如果更复杂的hashMap，可以实现hashTable表多维数组的hash

hashTable的length越长，hash冲突越少