Как реализована хеш-карта JavaScript?

88

В настоящее время я работаю с OpenLayers и имею огромный набор данных для рисования в векторный слой (более 100000 векторов).

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

javascript hash hashmap Патрик Хиллер
источник
2
Существует не одна реализация JS, поэтому нет возможности ответить на этот вопрос. ECMAScript не указывает, какую структуру данных использовать для объектов, и не указывает ограничений на время доступа. Хеши типичны, но можно использовать сбалансированные деревья.
outis
1
У ES6 чистые Карты. Ссылка описывает различия между обычным объектом и картой, ключевые детали и т. Д .: Карта JavaScript MDN
Ден Роман

Ответы:

193

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

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

Объект javascript представляет собой реальную хэш-карту по своей реализации, поэтому сложность поиска составляет O (1), но нет специальной hashcode()функции для строк javascript, она реализована внутри движком javascript (V8, SpiderMonkey, JScript.dll и т. д.) .)

Обновление 2020:

javascript сегодня поддерживает и другие типы данных: Mapи WeakMap. Они более похожи на хэш-карты, чем на традиционные объекты.

отакустай
источник
Отлично. Раньше я использовал $ ('div # someDiv'). Data (key, value), и этот намного проще и, вероятно, лучше поддерживает старые браузеры. Спасибо
Swaroop
есть ли способ узнать длину карты?
перекати
2
@Sridhar использует Object.keys (map) .length
otakustay
1
Обратите внимание, что вы можете использовать число в качестве ключа, map[2] = 'foo'но оно преобразуется в строку внутри> map = { '2': 'foo' }
Гарри Морено
@otakustay, это была супер крутая функция, о которой я узнал сегодня :) На самом деле мне нужно внимательно изучить Javascript.
Панкадж Пракаш
31

Объекты JavaScript не могут быть реализованы исключительно поверх хэш-карт.

Попробуйте это в консоли своего браузера:

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

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

... и вы получите их обратно в порядке вставки, что де-факто является стандартным поведением.

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

Вот видео Ларса Бака, объясняющего, почему v8 не использует хэш-карты для реализации объектов .

Крэйг Барнс
источник
3
"Отакустай технически неправильный, худший вид неправильного". Это немного жестковато. Это может быть не 1: 1, но для целей использования хеша, например словаря, он работает таким же образом.
наверное,
1
Просто хочу уточнить, что это может быть верным для некоторых реализаций JavaScript (например, большинства браузеров), но не всегда верно. Порядок итерации по ключам не определен стандартами ECMAScript и может иметь любой порядок и при этом быть допустимой реализацией JS.
TheZ
19

Вот простой и удобный способ использования чего-то похожего на карту Java :

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
    }

И чтобы получить значение:

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

......  etc  .....
Милош
источник
12

Если вы попробуете этот класс Map:

var myMap = new Map();

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

myMap.size; // 3

// getting the values
myMap.get("1");    // "value associated with "value1"
myMap.get("2");       // "value associated with "value1"
myMap.get("3");      // "value associated with "value3"
Развернуть фрагмент

Примечание: ключ и значение могут быть любого типа.

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

Нгуен Тан Дат
источник
4

Хотя простые старые объекты JavaScript могут использоваться в качестве карт, они обычно реализуются таким образом, чтобы сохранить порядок вставки для совместимости с большинством браузеров (см. Ответ Крейга Барнса) и, таким образом, не являются простыми хэш-картами.

ES6 вводит правильные карты (см. MDN JavaScript Map ), о которых в стандарте говорится :

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

mb21
источник
1 
<html>
<head>
<script type="text/javascript">
function test(){
var map= {'m1': 12,'m2': 13,'m3': 14,'m4': 15}
     alert(map['m3']);
}
</script>
</head>
<body>
<input type="button" value="click" onclick="test()"/>
</body>
</html>
Раджендра Кумар
источник
0

Я столкнулся с проблемой, когда у меня был json с некоторыми общими ключами. Я хотел сгруппировать все значения, имеющие один и тот же ключ. После некоторого серфинга я нашел пакет hashmap . Что действительно полезно.

Чтобы сгруппировать элемент с тем же ключом, я использовал multi(key:*, value:*, key2:*, value2:*, ...).

Этот пакет чем-то похож на коллекцию Java Hashmap, но не такой мощный, как Java Hashmap.

dd619
источник