JavaScript: память / эффективность ассоциативных массивов?

Question

Я строю древовидную структуру данных из ассоциативных массивов. Каждая клавиша состоит из 1-2 символов. Ключи уникальны для своего уровня. На корневом уровне будет не более 40 ключей и не более 5 ключей на каждом последующем уровне дерева. Это может выглядеть примерно так:

{a:{b:null,c:null},de:{f:{g:null}},h:null,i:null,j:null,k:null}

Первоначально я думал, что создание такого большого количества объектов с таким небольшим количеством ключей (в среднем <3) будет неэффективно и потребует много памяти. В этом случае я бы реализовал свою собственную хеш-таблицу следующим образом: </p>

//Suppose keys is a multi-dimensional array [[key,data],...]
var hash = function(keys){
    var max = keys.length*3, tbl = [];
    //Get key hash value
    var code = function(key){
        return (key.charCodeAt(0)*31)%max;
    }
    //Get key values
    this.get(key){
        //2 character keys actually have a separate hash generation algorithm...
        //we'll ignore them for now
        var map = code(key), i=map;
        //Find the key value
        while(true){
            if (typeof tbl[i] == 'undefined') return false;
            if (code(tbl[i][0]) == map && tbl[i][0] == key) return tbl[i][1];
            else i = (i+1)%max;
        }
    }

    //Instantiate the class
    for (var i=0; i<keys.length; i++){
        var index = code(keys[i][0]);
        while(typeof tbl[index] != 'undefined')
            index = (index+1)%max;
        tbl[index] = keys[i];
    }
}

Затем я где-то читал, что массивы JavaScript иногда реализуются как ассоциативные массивы при их редком заполнении, что может разрушить цель создания моей собственной хэш-структуры. Но я не уверен. Итак, что будет более эффективным с точки зрения памяти и скорости?

Answer 1

Прочитайте эту статью: http://mrale.ph/blog/2011/11/05/the-trap-of-the-performance-sweet-spot.html

В основном из-за динамической природы JavaScript, ваши структуры данных не будут очень эффективными. Если вам нужны очень эффективные структуры данных, попробуйте использовать новые типизированные массивы, представленные недавно.

Если вам не нравятся теоретические результаты, Resig провел тестирование производительности реальных слов на разных типах деревьев, анализируя размер данных, анализ и обработку производительности: http://ejohn.org/blog/javascript-trie-performance-analysis/

Answer 2

Ваше решение, если я правильно понимаю, определенно будет работать хуже. Вы выражаете беспокойство по этому поводу:

[...] создание большого количества объектов с таким небольшим количеством ключей (в среднем <3) [...] </p>

но ваше решение делает то же самое. Каждый из ваших вложенных хэшей все еще будет объектом с небольшим количеством ключей, только теперь некоторые из его ключей являются замыканием с именем get (которое будет иметь более высокие требования к памяти, поскольку оно неявно закрывается над такими переменными, как tbl и code, где code - другое закрытие ...).