I need something analogous to Java's HashMap (or any kind of map, actually).
I have read in other forums that an Object() can be used as a map like this:
var object = new Object()
object.var1 = "blah";
object.var2 = anotherObject;
alert("This is how I can get the value: " + object.var1);
However, the way I see it this only works for static key-names. What if I need to have many dynamically-generated entries in the object? For example:
// this does not work the way I want it to
var key = "aaaaa";
object.key = anObject;
key = "bbbbb";
object.key = anotherObject;
when running this, instead of having something like:
object.aaaaa --> anObject
object.bbbbb --> anotherObject
I have:
object.key --> anotherObject
If you get the picture, how can I have a dynamically-generated hashmap-like entity with entries that are generated dynamically through a for-lopp for example?
Except for the clear() function.
This seems to work better:
PHP Code:
/* following does not work correctly
function clear() {
for( var i = 0; i < this.keyArray.length; i++ ) {
this.keyArray.pop(); this.valArray.pop();
}
}
*/
/* replaces above */
function clear() {
while (this.keyArray.length > 0) { this.keyArray.pop(); this.valArray.pop(); }
}
And this still is not a hashmap. A hashmap is an ordered array with key and value pairs.
Get: O(1) or O(log(n)) if implemented as a normal map.
Add: O(log(n))
Remove: same as Get, but includes some rotating if necessary.
Upperbound and Lowerbound: O(log(n))
I didn't find an implementation of a real hashmap in javascript yet. I've made one in C++ before, maybe I'm gonna convert that code into javascript...
All implementations I've found on the internet so far, are just wrappers around the normal javascript Object. The thing i'm missing is the fact that it's not ordered. Normal javascript Arrays can be ordered, but they only have a value, no key...
If any of you found a good solution, please post it here!
The thing i'm missing is the fact that it's not ordered. Normal javascript Arrays can be ordered, but they only have a value, no key...
Though it wasn't part of the spec, Object does indeed preserves the key's order. The only exceptions i know of were early versions of chrome, but they've probably fixed that by now...
if nothing else, use an array of {key:value} objects.
this gives you names, preserves order, and allows nice tools like Array.map, Array.sort, Array.concat, etc to work on your "hash".
You can also create expression objects, and use them instead of {key:value} objects, so that you can use .join() and what not as expected...
__________________ my site (updated 5/13) STATS (2013/5) HTML5:90.2% MOB:15.2% IE7:0.5% IE8:8.4% IE9:8.5% IE10:8.5%
var aArray = {};
aArray["def"] = "test1";
aArray["abc"] = "test2";
Then the order is still 'def' before 'abc' when I loop like
Code:
for (var sIndex in aArray) { var sValue = aArray[sIndex]; }
If I take a normal array like:
Code:
var aArray = new Array();
aArray.push("test1");
aArray.push("test2");
Then I can use the Array sort functions and stuff, but I don't have a key (other then the auto-numeric index). So it's not even close anymore to a hashtable or hashmap.
Although the javascript Array has a method to insert a item at a specific index, using splice, some test has shown me that the speed of that operation is O(n).
So the shortest solution in code I can come up with is a linked list with a seperate key-value Object for a quick get. Like:
Code:
function Node(sKey, sValue) {
this.sKey = "";
this.sValue = "";
this.nNext = null;
this.nPrev = null;
}
function Container() {
this.aHash = {};
this.nFirst = null;
}
Container.prototype.add(sKey, sValue) {
var nCur = new Node(sKey, sValue);
this.aHash[sKey] = nCur;
// standard linked list insert...
}
This gives the possibility to loop through the list in order and gives a Get with speed O(1). The Add and Delete are O(n) though, because of the linked list search...
A other solution would be implementing a Self-balancing dual-threaded hashed RB-Tree. This also gives the possibility to loop through it in order and gives the following performances:
Add: Log n
Del: 1
Get: 1
Upperbound and Lowerbound: Log n
The disadvantage is that it costs quite some code, which the user has to download when opening the page. So the question is, what's worth the extra performance...
(PS. Forgive my bad english at some points, I'm Dutch.)
Well, there's no real reason you couldn't truly implement a hashmap, if you don't mind writing the hashing code. But of course you would still end up putting the pairs into array elements (at least elements by number, though). So your performance might be better, but I'm not sure that I can see performance much mattering with the size of maps (and arrays) you would normally encounter in client-side JavaScript.
var aArray = new Array();
aArray.push("test1");
aArray.push("test2");
Then I can use the Array sort functions and stuff, but I don't have a key (other then the auto-numeric index). So it's not even close anymore to a hashtable or hashmap.
Although the javascript Array has a method to insert a item at a specific index, using splice, some test has shown me that the speed of that operation is O(n).
Give the elements names by using expressions. that way, you keep the fast/flexible array as the container, but gain "invisible" key names as well, giving you the best of both worlds.
Code:
// expression constructor:
function Expr(s,p){
if(this.Array===Array){return new Expr(s,p);}
if(p&&p.constructor===Object && !p._val){
for(it in p){if(p.hasOwnProperty(it)){this[it]=p[it];}}
}else{
this.x=p;
}
this._val=s;
return this;
}; Expr.prototype=({
valueOf: function(){return this.v;},
toString: function(){return this.v;}
});//end Expr constructor
function _(k,v){ //item maker
return new Expr( "v" , {k:k, v:v} );
}
function List(r){//hashmaker
r.at=function(key){ //items: finds by key
for(it in r){
if(r[it].k===key){return r[it];}
}
}
return r;
}
// a "hash"
var r=List([
_("fred",21),
_("joe",32),
_("tom",66),
_("dick",42),
_("harry",16)
]);
//test it out:
alert([
r[2], //normal, get value by slot
r[2].k, //get key
r.at('tom'), // by key
r.sort()[0].k, //smallest value's key
r.sort().reverse()[0] //biggest value
])//==="66,tom,66,harry,66"
the other nice thing about this approach is that each element (an expression) is an island.
you can .concat(), .slice(), etc, without having to worry about synchronization.
Don't worry about performance as much.
that's a bunch of textbook stuff, not real world javascript.
truth is, Chrome and FF3.5 will both bend these rules using various run-time optimizations.
All browsers will run Array.splice() much faster than anything we could cook up...
I'm not saying to ignore performance during design, but you should not let it slow down development.
Try to get something working, and see if you have a problem.
The only time i've run into major performance issues in javascript is in my image editor. But i knew before i wrote it that looping/processing arrays with millions of elements would take a little while in javascript. I was surprised at how fast it actually ran when i was done building the rough draft...
EDIT: i swapped out the expression evaluator code.
it doesn't need eval in this example, so now it's a bit faster...
__________________ my site (updated 5/13) STATS (2013/5) HTML5:90.2% MOB:15.2% IE7:0.5% IE8:8.4% IE9:8.5% IE10:8.5%
First of all: thank you all for your comments.
@Old Pedant: true, it is possible, but the question is indeed if the performance increase is worth the effort you must put in it...
@rnd me: Nice example of a clever way to extend a normal javascript Array. But both Get and Del are O(n). And if I want to keep the array sorted, Add is at least Log(n) or n, that depends on the sorting algorithm or Array.sort. Then I can as well make my own linked list...
@Trinithis: I saw that piece of jscript before. It's a nice implementation of a red-black tree, wich makes deletion, getting and adding relatively fast, but I cannot loop through the values in order.
@all of you saying performance is not an issue: I've heard that a lot, even at school and most of the times the people saying that are so wrong. Not everyone has a super-fast pc and if you want to analyse/modify a list of points on every mousemove (e.g. when drawing a graph), you must really think about it if there is no solution with a better performance than O(n).
Sure, it must not slow down development if it's not necessary. But it's also cheaper to come up with the best solution in the first place, than to recode/refactor your whole datastructure afterwards.
Cannot at all argue with you re your example. Yes, JS can indeed be too slow for some graphing intensive operations. I have a case where my simple-minded implementation worked, but the mouse movement was jerky at best. Cleaning up the code made the mouse movement acceptable on my dual-core AMD, but it still lagged on my wife's Sempron. Since it was only for my own use, I left it alone. But clearly I would have needed a "re-think" if I'd wanted to publish it on a web site.
Before you post, read our: 
