JavaScript эквивалентный Hashmap
Внимание: примерный код этого ответа (например, примерный код вопроса) использует расширение PHP
mysql, которое устарело в PHP 5.5.0 и полностью удалено в PHP 7.0.0.Если вы используете последнюю версию PHP, опция
mysql_real_escape_string, описанная ниже, больше не будет доступна (хотяmysqli::escape_stringявляется современным эквивалентом). В настоящее время опцияmysql_real_escape_stringимеет смысл только для устаревшего кода на старой версии PHP.У вас есть два варианта - экранирование специальных символов в вашем
unsafe_variableили использование параметризованный запрос. Оба будут защищать вас от SQL-инъекций. Параметрированный запрос считается лучшей практикой, но для его использования потребуется переходить на более новое расширение mysql в PHP.Мы рассмотрим нижнюю строку удара, которая будет первой.
//Connect $unsafe_variable = $_POST["user-input"]; $safe_variable = mysql_real_escape_string($unsafe_variable); mysql_query("INSERT INTO table (column) VALUES ('" . $safe_variable . "')"); //DisconnectСм. также информацию о функции
mysql_real_escape_string.Чтобы использовать параметризованный запрос, вам нужно использовать MySQLi , а не функции MySQL . Чтобы переписать ваш пример, нам понадобится что-то вроде следующего.
prepare("INSERT INTO table (column) VALUES (?)"); // TODO check that $stmt creation succeeded // "s" means the database expects a string $stmt->bind_param("s", $unsafe_variable); $stmt->execute(); $stmt->close(); $mysqli->close(); ?>Ключевая функция, которую вы хотите прочитать, будет
mysqli::prepare.Также, как предложили другие, вы можете сочтет полезным / легче повысить уровень абстракции с помощью чего-то вроде PDO .
Обратите внимание, что случай вы спросили об этом довольно просто, и что более сложные случаи могут потребовать более сложных подходов. В частности:
- Если вы хотите изменить структуру SQL на основе пользовательского ввода, параметризованные запросы не помогут, и требуемое экранирование не распространяется на
mysql_real_escape_string. В этом случае вам лучше было бы пропускать вход пользователя через белый список, чтобы обеспечить доступ только «безопасных» значений.- Если вы используете целые числа от пользовательского ввода в состоянии и берете
mysql_real_escape_string, вы столкнетесь с проблемой, описанной в Polynomial в комментариях ниже. Этот случай более сложный, поскольку целые числа не будут окружены кавычками, поэтому вы можете справиться, подтвердив, что пользовательский ввод содержит только цифры.- Есть, вероятно, другие случаи, о которых я не знаю. Вы можете найти , этот является полезным ресурсом для некоторых более тонких проблем, с которыми вы можете столкнуться.
6 ответов
Почему бы не хешировать Ваши объекты самостоятельно вручную и использование получившие строки как ключи для регулярного словаря JavaScript? В конце концов, Вы находитесь в лучшем положении для знания то, что делает объекты уникальными. Это - то, что я делаю.
Пример:
var key = function(obj){
// some unique object-dependent key
return obj.totallyUniqueEmployeeIdKey; // just an example
};
var dict = {};
dict[key(obj1)] = obj1;
dict[key(obj2)] = obj2;
Этот путь можно управлять индексацией, сделанной JavaScript без тяжелого подъема выделения памяти и обработки переполнения.
, Конечно, если Вы действительно хотите "решение промышленного класса", можно создать класс, параметризованный ключевой функцией, и со всем необходимым API контейнера, но … мы используем JavaScript, и пытающийся быть простыми и легкими, таким образом, это функциональное решение просто и быстро.
ключевая функция может быть столь же простой как выбирающий правильные атрибуты объекта, например, ключ или ряд ключей, которые уже уникальны, комбинация ключей, которые уникальны вместе или так же сложны как использующий некоторые криптографические хеши как в DojoX, Кодирующий , или DojoX UUID. В то время как последние решения могут произвести уникальные ключи, лично я стараюсь избегать их любой ценой, особенно, если я знаю то, что делает мои объекты уникальными.
Обновление в 2014: Огрызался в 2008, это простое решение все еще требует большего количества объяснений. Позвольте мне разъяснить идею в Q& форма.
Ваше решение не имеет реального хеша. Где это???
JavaScript является высокоуровневым языком. Его основной примитив ( Объект ) включает хэш-таблицу для хранения свойств. Эта хэш-таблица обычно пишется на низкоуровневом языке для эффективности. Используя простой объект со строковыми ключами мы используем эффективно реализованную хэш-таблицу без усилий с нашей стороны.
, Как Вы знаете, что они используют хеш?
существует три главных способа сохранить набор объектов адресуемым ключом:
- Незаказанный. В этом случае для получения объекта его ключом мы должны пробежаться через всю остановку ключей, когда мы находим его. В среднем это возьмет n/2 сравнения.
- Заказанный.
- Пример № 1: сортированный массив — при выполнении двоичного поиска мы найдем наш ключ после ~log2 (n) сравнения в среднем. Намного лучше.
- Пример № 2: дерево. Снова это будет ~log (n) попытки.
- Хэш-таблица. В среднем требуется постоянное время. Сравните: O (n) по сравнению с O (регистрируют n) по сравнению с O (1). Бум.
, Очевидно, объекты JavaScript используют хэш-таблицы в некоторой форме для обработки общих случаев.
поставщики браузера действительно используют хэш-таблицы???
Действительно.
- Chrome/node.js / V8: JSObject. Ищите NameDictionary и NameDictionaryShape с подходящими деталями в [1 111] objects.cc и объекты-inl.h .
- Firefox / Геккон : JSObject, NativeObject, и PlainObject с подходящими деталями в [1 117] jsobj.cpp и vm/NativeObject.cpp.
они обрабатывают коллизии?
Да. Посмотрите выше. При нахождении коллизии на неравных строках зарегистрируйте ошибку с поставщиком.
Поэтому, какова Ваша идея?
, Если Вы хотите хешировать объект, найдите то, что делает его уникальным, и используйте его в качестве ключа. Не пытайтесь вычислить реальный хеш или эмулировать хэш-таблицы — это уже эффективно обрабатывается базовым объектом JavaScript.
Использование этот ключ с JavaScript Object для усиления его встроенной хэш-таблицы, избегая возможных столкновений со свойствами по умолчанию.
Примеры для запущения Вас:
- , Если Ваши объекты включают уникальное имя пользователя — используйте его в качестве ключа.
- , Если это включает уникальное потребительское число — используйте его в качестве ключа.
- , Если это включает уникальные выпущенные правительством числа как SSN, или номер паспорта и Ваша система не позволяют дубликаты — используйте его в качестве ключа.
- , Если комбинация полей является уникальным — используйте его в качестве ключа.
- Аббревиатура штата + число водительских прав делает превосходный ключ.
- сокращение Страны + номер паспорта является превосходным ключом также.
- Некоторая функция на полях или целый объект, может возвратить уникальное значение — используйте его в качестве ключа.
я использовал Ваше предложение и кэшировал все объекты с помощью имени пользователя. Но некоторого мудрого парня называют "toString", который является встроенным свойством! Что я должен сделать теперь?
, Очевидно, если даже удаленно возможно, что получающийся ключ будет исключительно, состоит из латинских символов, необходимо делать с этим что-то. Например, добавьте любой нелатинский символ Unicode, Вам нравится вначале или в конце не сталкиваться со свойствами по умолчанию: "#toString", "#MarySmith". Если составной ключ используется, отдельные ключевые компоненты с помощью некоторого нелатинского разделителя: "имя, город, состояние".
В целом это - место, где мы должны быть творческими, и выбрать самые легкие ключи с данными ограничениями (уникальность, потенциальные столкновения со свойствами по умолчанию).
Примечание: уникальные ключи не сталкиваются по определению, в то время как потенциальные столкновения хеша будут обработаны лежанием в основе Object.
, Почему Вам не нравятся промышленные решения?
, по моему скромному мнению, лучший код не является никаким кодом вообще: это не имеет никаких ошибок, не требует никакого обслуживания, легкого понять, и выполняется мгновенно. Все "хэш-таблицы в JavaScript" я видел, были> 100 строк кода и включил несколько объектов. Сравните его с: dict[key] = value.
Другая точка: даже возможно разбить производительность исконного объекта, записанного на низкоуровневом языке, с помощью JavaScript и тех же самых исконных объектов реализовать то, что уже реализовано?
я все еще хочу хешировать свои объекты без любых ключей!
Мы находимся в удаче: ECMAScript 6 (запланированный для выпуска середины 2015, плюс-минус 1-2 года после этого для становления широко распространенным) определяет , карта и установила .
Оценка по определению они могут использовать адрес объекта в качестве ключа, который делает объекты немедленно отличными без искусственных ключей. OTOH, два различных, все же одинаковые объекты, будет отображен как отличный.
разбивка Сравнения от [1 121] MDN:
Объекты подобны Картам в тот и позволенный Вы установить ключи к значениям, получить те значения, клавиши Delete, и обнаружить, хранится ли что-то в ключе. Из-за этого (и потому что не было никаких встроенных альтернатив), Объекты использовались в качестве Карт исторически; однако, существуют важные различия, которые делают использование Карты предпочтительным в определенных случаях:
- ключи Объекта являются Строками и Символами, тогда как они могут быть любым значением для Карты, включая функции, объекты и любой примитив.
- ключи в Карте заказаны, в то время как ключи, добавленные к объекту, не. Таким образом, при итерации по нему, Карта возражает ключам возвратов в порядке вставки.
- можно получить размер Карты легко со свойством размера, в то время как количество свойств в Объекте должно быть определено вручную.
- Карта А является повторяемым и может таким образом быть непосредственно выполнена с помощью итераций, тогда как итерация по Объекту требует получения его ключей в некотором виде и итерации по ним.
- Объект имеет прототип, таким образом, существуют ключи по умолчанию в карте, которая могла столкнуться с Вашими ключами, если Вы не осторожны. С ES5 это может быть обойдено при помощи карты = Object.create (пустой указатель), но это редко делается.
- Карта А может работать лучше в сценариях, включающих частое дополнение и удаление пар ключей.
JavaScript не создает - в Map/hashmap. Это нужно назвать , ассоциативный массив .
hash["X"], равняется hash.X, но позвольте "X" как строковая переменная. Другими словами, hash[x], функционально равняется eval("hash."+x.toString())
, Это более подобно как object.properties скорее тогда отображение значения ключа. При поиске лучшего Ключа/построения карты ценности в JavaScript используйте объект Карты, который можно найти в сети.
Необходимо было бы сохранить в некоторых двустишиях внутреннего состояния пар объекта/значения
HashMap = function(){
this._dict = [];
}
HashMap.prototype._get = function(key){
for(var i=0, couplet; couplet = this._dict[i]; i++){
if(couplet[0] === key){
return couplet;
}
}
}
HashMap.prototype.put = function(key, value){
var couplet = this._get(key);
if(couplet){
couplet[1] = value;
}else{
this._dict.push([key, value]);
}
return this; // for chaining
}
HashMap.prototype.get = function(key){
var couplet = this._get(key);
if(couplet){
return couplet[1];
}
}
И использовать его как таковой:
var color = {}; // unique object instance
var shape = {}; // unique object instance
var map = new HashMap();
map.put(color, "blue");
map.put(shape, "round");
console.log("Item is", map.get(color), "and", map.get(shape));
, Конечно, эта реализация также где-нибудь вроде O (n). Примерами Eugene выше является единственный способ получить хеш, который работает с любым видом скорости, которую Вы ожидали бы от реального хеша.
Обновление:
Другой подход, вроде ответа Eugene должен так или иначе присоединить уникальный идентификатор ко всем объектам. Один из моих любимых подходов должен взять один из встроенных методов, наследованных от Объектного суперкласса, заменить его пользовательской функциональной передачей и свойствами присоединения к тому функциональному объекту. Если бы необходимо было переписать мой метод HashMap, чтобы сделать это, он был бы похож:
HashMap = function(){
this._dict = {};
}
HashMap.prototype._shared = {id: 1};
HashMap.prototype.put = function put(key, value){
if(typeof key == "object"){
if(!key.hasOwnProperty._id){
key.hasOwnProperty = function(key){
return Object.prototype.hasOwnProperty.call(this, key);
}
key.hasOwnProperty._id = this._shared.id++;
}
this._dict[key.hasOwnProperty._id] = value;
}else{
this._dict[key] = value;
}
return this; // for chaining
}
HashMap.prototype.get = function get(key){
if(typeof key == "object"){
return this._dict[key.hasOwnProperty._id];
}
return this._dict[key];
}
Эта версия, кажется, незначительно быстрее, но в теории это будет значительно быстрее для больших наборов данных.
Описание проблемы
JavaScript не имеет никакого встроенного генерала тип карты (иногда называемый словарь ассоциативного массива или ), который позволяет получать доступ к произвольным значениям произвольными ключами. Фундаментальная структура данных JavaScript объект , специальный тип карты, которая только принимает строки как ключи и имеет специальную семантику как формирующее прототип наследование, методы get и методы set и некоторый дальнейший вуду.
, Когда использования возражает как карты, необходимо помнить, что ключ будет преобразован в строковое значение через toString(), который приводит к отображению 5 и '5' к тому же значению и всем объектам, которые не перезаписывают toString() метод к значению, индексированному '[object Object]'. Вы могли бы также непреднамеренно получить доступ к его унаследованным свойствам, если Вы не проверяете hasOwnProperty().
JavaScript, встроенный массив , тип не помогает одному биту: массивы JavaScript не являются ассоциативными массивами, но просто возражает с несколькими более специальными свойствами. Если Вы хотите знать, почему они не могут использоваться в качестве карт, взгляд здесь .
Решение
Eugene Lazutkin Eugene уже описало основную идею использовать пользовательскую хеш-функцию для генерации уникальных строк, которые могут использоваться для поиска присваиваемых значений как свойств объекта словаря. Это, скорее всего, будет быстрым решением, потому что объекты внутренне реализованы как [1 126] хэш-таблицы .
- Примечание: Хэш-таблицы (иногда называемый карты хеша ) являются конкретной реализацией понятия карты с помощью вспомогательного массива и поиска через числовые значения хэш-функции. Среда выполнения могла бы использовать другие структуры (такой как [1 128] деревья поиска или списки пропуска ) для реализации объектов JavaScript, но поскольку объекты являются фундаментальной структурой данных, они должны быть достаточно оптимизированы.
для получения уникального значения хэш-функции для произвольных объектов, одна возможность состоит в том, чтобы использовать глобальный счетчик и кэшировать значение хэш-функции в самом объекте (например, в свойстве, названном __hash).
хеш-функция А, которая делает это, и работает и на примитивные значения и на объекты:
function hash(value) {
return (typeof value) + ' ' + (value instanceof Object ?
(value.__hash || (value.__hash = ++arguments.callee.current)) :
value.toString());
}
hash.current = 0;
Эта функция может использоваться, как описано Eugene. Для удобства мы далее обернем его в Map класс.
Мой Map реализация
следующая реализация дополнительно сохранит пар значения ключа в двунаправленном связанном списке для разрешения быстрого повторения и по ключам и по значениям. Для предоставления собственной хеш-функции можно перезаписать экземпляр hash() метод после создания.
// linking the key-value-pairs is optional
// if no argument is provided, linkItems === undefined, i.e. !== false
// --> linking will be enabled
function Map(linkItems) {
this.current = undefined;
this.size = 0;
if(linkItems === false)
this.disableLinking();
}
Map.noop = function() {
return this;
};
Map.illegal = function() {
throw new Error("illegal operation for maps without linking");
};
// map initialisation from existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
var map = new Map;
for(var prop in obj) {
if(foreignKeys || obj.hasOwnProperty(prop))
map.put(prop, obj[prop]);
}
return map;
};
Map.prototype.disableLinking = function() {
this.link = Map.noop;
this.unlink = Map.noop;
this.disableLinking = Map.noop;
this.next = Map.illegal;
this.key = Map.illegal;
this.value = Map.illegal;
this.removeAll = Map.illegal;
return this;
};
// overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
return (typeof value) + ' ' + (value instanceof Object ?
(value.__hash || (value.__hash = ++arguments.callee.current)) :
value.toString());
};
Map.prototype.hash.current = 0;
// --- mapping functions
Map.prototype.get = function(key) {
var item = this[this.hash(key)];
return item === undefined ? undefined : item.value;
};
Map.prototype.put = function(key, value) {
var hash = this.hash(key);
if(this[hash] === undefined) {
var item = { key : key, value : value };
this[hash] = item;
this.link(item);
++this.size;
}
else this[hash].value = value;
return this;
};
Map.prototype.remove = function(key) {
var hash = this.hash(key);
var item = this[hash];
if(item !== undefined) {
--this.size;
this.unlink(item);
delete this[hash];
}
return this;
};
// only works if linked
Map.prototype.removeAll = function() {
while(this.size)
this.remove(this.key());
return this;
};
// --- linked list helper functions
Map.prototype.link = function(item) {
if(this.size == 0) {
item.prev = item;
item.next = item;
this.current = item;
}
else {
item.prev = this.current.prev;
item.prev.next = item;
item.next = this.current;
this.current.prev = item;
}
};
Map.prototype.unlink = function(item) {
if(this.size == 0)
this.current = undefined;
else {
item.prev.next = item.next;
item.next.prev = item.prev;
if(item === this.current)
this.current = item.next;
}
};
// --- iterator functions - only work if map is linked
Map.prototype.next = function() {
this.current = this.current.next;
};
Map.prototype.key = function() {
return this.current.key;
};
Map.prototype.value = function() {
return this.current.value;
};
Пример
следующий сценарий
var map = new Map;
map.put('spam', 'eggs').
put('foo', 'bar').
put('foo', 'baz').
put({}, 'an object').
put({}, 'another object').
put(5, 'five').
put(5, 'five again').
put('5', 'another five');
for(var i = 0; i++ < map.size; map.next())
document.writeln(map.hash(map.key()) + ' : ' + map.value());
генерирует этот вывод:
string spam : eggs
string foo : baz
object 1 : an object
object 2 : another object
number 5 : five again
string 5 : another five
Дальнейшие соображения
PEZ предложил перезаписать toString() метод, по-видимому, с нашей хеш-функцией. Это не выполнимо, потому что это не работает на примитивные значения (изменяющийся toString() для примитивов, очень плохая идея). Если бы мы хотим toString() возвратить значимые значения для произвольных объектов, мы должны были бы изменить Object.prototype, который некоторые люди (самостоятельно не включенный) рассматривают verboten.
Редактирование: текущая версия моего Map реализация, а также другие положительные герои JavaScript может быть получена отсюда .
Попробуйте мою реализацию хеш-таблицы JavaScript: http://www.timdown.co.uk/jshashtable
Он ищет метод hashCode () для ключевых объектов, или вы может предоставить хеш-функцию при создании объекта Hashtable.
Я реализовал JavaScript HashMap, код которого можно получить с http://github.com / lambder / HashMapJS / tree / master
Вот код:
/*
=====================================================================
@license MIT
@author Lambder
@copyright 2009 Lambder.
@end
=====================================================================
*/
var HashMap = function() {
this.initialize();
}
HashMap.prototype = {
hashkey_prefix: "<#HashMapHashkeyPerfix>",
hashcode_field: "<#HashMapHashkeyPerfix>",
initialize: function() {
this.backing_hash = {};
this.code = 0;
},
/*
maps value to key returning previous assocciation
*/
put: function(key, value) {
var prev;
if (key && value) {
var hashCode = key[this.hashcode_field];
if (hashCode) {
prev = this.backing_hash[hashCode];
} else {
this.code += 1;
hashCode = this.hashkey_prefix + this.code;
key[this.hashcode_field] = hashCode;
}
this.backing_hash[hashCode] = value;
}
return prev;
},
/*
returns value associated with given key
*/
get: function(key) {
var value;
if (key) {
var hashCode = key[this.hashcode_field];
if (hashCode) {
value = this.backing_hash[hashCode];
}
}
return value;
},
/*
deletes association by given key.
Returns true if the assocciation existed, false otherwise
*/
del: function(key) {
var success = false;
if (key) {
var hashCode = key[this.hashcode_field];
if (hashCode) {
var prev = this.backing_hash[hashCode];
this.backing_hash[hashCode] = undefined;
if(prev !== undefined)
success = true;
}
}
return success;
}
}
//// Usage
// creation
var my_map = new HashMap();
// insertion
var a_key = {};
var a_value = {struct: "structA"};
var b_key = {};
var b_value = {struct: "structB"};
var c_key = {};
var c_value = {struct: "structC"};
my_map.put(a_key, a_value);
my_map.put(b_key, b_value);
var prev_b = my_map.put(b_key, c_value);
// retrieval
if(my_map.get(a_key) !== a_value){
throw("fail1")
}
if(my_map.get(b_key) !== c_value){
throw("fail2")
}
if(prev_b !== b_value){
throw("fail3")
}
// deletion
var a_existed = my_map.del(a_key);
var c_existed = my_map.del(c_key);
var a2_existed = my_map.del(a_key);
if(a_existed !== true){
throw("fail4")
}
if(c_existed !== false){
throw("fail5")
}
if(a2_existed !== false){
throw("fail6")
}