Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 14 of 14
  1. #1
    New to the CF scene
    Join Date
    Nov 2008
    Posts
    2
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Javascript Hashmap-like functionality?

    Hi all,

    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?

    Thanks!

  • #2
    New to the CF scene
    Join Date
    Nov 2008
    Posts
    2
    Thanks
    1
    Thanked 0 Times in 0 Posts

    solution


  • #3
    Senior Coder jmrker's Avatar
    Join Date
    Aug 2006
    Location
    FL
    Posts
    3,083
    Thanks
    38
    Thanked 498 Times in 492 Posts

    Thumbs up

    Quote Originally Posted by fragkakis View Post
    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(); }


  • #4
    Senior Coder rnd me's Avatar
    Join Date
    Jun 2007
    Location
    Urbana
    Posts
    4,333
    Thanks
    11
    Thanked 587 Times in 568 Posts
    all you need to do is use Array syntax, no need fir extra libraries.

    Code:
    var key = "aaaaa";
    object.key = anObject;
    
    key = "bbbbb";
    object.key = anotherObject;
    should be:

    Code:
    var key = "aaaaa";
    object[key]= anObject;
    
    key = "bbbbb";
    object[key]= anotherObject;
    my site (updated 13/9/26)
    BROWSER STATS [% share] (2014/5/28) IE7:0.1, IE8:5.3, IE11:8.4, IE9:3.2, IE10:3.2, FF:18.2, CH:46, SF:7.9, NON-MOUSE:32%

  • Users who have thanked rnd me for this post:

    fragkakis (11-25-2008)

  • #5
    New to the CF scene
    Join Date
    Apr 2009
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by fragkakis View Post
    The problem is that lookup is done in O(n) while a true map does it in O(1) so this is more like a list or a queue than a map...

  • #6
    New to the CF scene
    Join Date
    Oct 2009
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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))

    If some of you don't know or understand what a hashmap is, please visit http://en.wikipedia.org/wiki/Hashmap and http://en.wikipedia.org/wiki/Red_black_tree first.

    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!

  • #7
    Supreme Master coder! Philip M's Avatar
    Join Date
    Jun 2002
    Location
    London, England
    Posts
    17,982
    Thanks
    203
    Thanked 2,536 Times in 2,514 Posts
    Quote Originally Posted by jmhimself View Post
    And this still is not a hashmap. A hashmap is an ordered array with key and value pairs.
    I would have thought that the thread title Javascript Hashmap-like functionality was plain enough.

  • #8
    Senior Coder rnd me's Avatar
    Join Date
    Jun 2007
    Location
    Urbana
    Posts
    4,333
    Thanks
    11
    Thanked 587 Times in 568 Posts
    Quote Originally Posted by jmhimself View Post
    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...
    Last edited by rnd me; 10-28-2009 at 11:16 PM.
    my site (updated 13/9/26)
    BROWSER STATS [% share] (2014/5/28) IE7:0.1, IE8:5.3, IE11:8.4, IE9:3.2, IE10:3.2, FF:18.2, CH:46, SF:7.9, NON-MOUSE:32%

  • #9
    New to the CF scene
    Join Date
    Oct 2009
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts
    If I do the following:
    Code:
    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.)

  • #10
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,438
    Thanks
    75
    Thanked 4,372 Times in 4,337 Posts
    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.

  • #11
    Senior Coder rnd me's Avatar
    Join Date
    Jun 2007
    Location
    Urbana
    Posts
    4,333
    Thanks
    11
    Thanked 587 Times in 568 Posts
    Quote Originally Posted by jmhimself View Post

    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).

    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...
    Last edited by rnd me; 10-30-2009 at 01:28 AM.
    my site (updated 13/9/26)
    BROWSER STATS [% share] (2014/5/28) IE7:0.1, IE8:5.3, IE11:8.4, IE9:3.2, IE10:3.2, FF:18.2, CH:46, SF:7.9, NON-MOUSE:32%

  • #12
    Regular Coder
    Join Date
    Jun 2007
    Location
    USA
    Posts
    527
    Thanks
    26
    Thanked 74 Times in 72 Posts
    Trinithis

  • #13
    New to the CF scene
    Join Date
    Oct 2009
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #14
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,438
    Thanks
    75
    Thanked 4,372 Times in 4,337 Posts
    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.


  •  

    Tags for this Thread

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •