How is a JavaScript hash map implemented? - Stack Overflow

admin管理员组

文章数量:1134660

I currently work with OpenLayers and have a huge set of data to draw into a vector layer (greater than 100000 vectors).

I'm now trying to put all these vectors into a JavaScript hash map to analyze the performance. I want to know how is the hash map in JavaScript implemented, is it a real hash function or just a wrapped function that uses a simple data structure and a search algorithm?

I currently work with OpenLayers and have a huge set of data to draw into a vector layer (greater than 100000 vectors).

I'm now trying to put all these vectors into a JavaScript hash map to analyze the performance. I want to know how is the hash map in JavaScript implemented, is it a real hash function or just a wrapped function that uses a simple data structure and a search algorithm?

• javascript
• hash
• hashmap

Share Improve this question Follow edited Aug 22, 2013 at 15:41 Eric Leschinski 154k9696 gold badges421421 silver badges335335 bronze badges asked Jan 16, 2012 at 9:03 Patrick HillertPatrick Hillert 2,42944 gold badges2424 silver badges3838 bronze badges 2

• 3 There's not just one JS implementation, so there's no way to answer this. ECMAScript doesn't specify what data structure to use for objects, nor does it specify restraints on access time. Hashes are typical, but balanced trees could be used. – outis Commented Jan 16, 2012 at 9:31
• 1 ES6 have pure Maps. The link describes differences between plain object and Map, key details etc: MDN JavaScript Map – Den R Commented Jan 18, 2017 at 15:23

Add a comment  | 

7 Answers 7

Sorted by: Reset to default 242

Every JavaScript object is a simple hashmap which accepts a string or a Symbol as its key, so you could write your code as:

var map = {};
// add a item
map[key1] = value1;
// or remove it
delete map[key1];
// or determine whether a key exists
key1 in map;

JavaScript object is a real hashmap on its implementation, so the complexity on search is O(1), but there is no dedicated hashcode() function for JavaScript strings, it is implemented internally by JavaScript engine (V8, SpiderMonkey, JScript.dll, etc...)

2020 Update:

JavaScript today supports other datatypes as well: Map and WeakMap. They behave more closely as hash maps than traditional objects.

JavaScript objects cannot be implemented purely on top of hash maps.

Try this in your browser console:

var foo = {
    a: true,
    b: true,
    z: true,
    c: true
}

for (var i in foo) {
    console.log(i);
}

...and you'll recieve them back in insertion order, which is de facto standard behaviour.

Hash maps inherently do not maintain ordering, so JavaScript implementations may use hash maps somehow, but if they do, it'll require at least a separate index and some extra book-keeping for insertions.

Here's a video of Lars Bak explaining why v8 doesn't use hash maps to implement objects.

Should you try this class Map:

var myMap = new Map();

// setting the values
myMap.set("1", 'value1');
myMap.set("2", 'value2');
myMap.set("3", 'value3');

console.log(`Map size: ${myMap.size}`); // 3

// getting the values
console.log(`Key: "1", Value: ${myMap.get("1")}`);    // "value associated with "value1"
console.log(`Key: "2", Value: ${myMap.get("2")}`);    // "value associated with "value2"
console.log(`Key: "3", Value: ${myMap.get("3")}`);    // "value associated with "value3"

Notice: key and value can be any type.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

Here is an easy and convenient way of using something similar to the Java map:

var map= {
    'map_name_1': map_value_1,
    'map_name_2': map_value_2,
    'map_name_3': map_value_3,
    'map_name_4': map_value_4
    }

And to get the value:

alert( map['map_name_1'] );    // fives the value of map_value_1

......  etc  .....

While plain old JavaScript objects can be used as maps, they are usually implemented in a way to preserve insertion-order for compatibility with most browsers (see Craig Barnes's answer) and are thus not simple hash maps.

ES6 introduces proper Maps (see MDN JavaScript Map) of which the standard says:

Map object must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection.

I was running into the problem where i had the json with some common keys. I wanted to group all the values having the same key. After some surfing I found hashmap package. Which is really helpful.

To group the element with the same key, I used multi(key:*, value:*, key2:*, value2:*, ...).

This package is somewhat similar to Java Hashmap collection, but not as powerful as Java Hashmap.

function test() {
  var map = {
    'm1': 12,
    'm2': 13,
    'm3': 14,
    'm4': 15
  }
  alert(map['m3']);
}

<input type="button" value="click" onclick="test()" />

本文标签： How is a JavaScript hash map implementedStack Overflow