Jak wyjaśniono w aktualizacji 3 tej odpowiedzi , notacja ta:
var hash = {};
hash[X]
tak naprawdę nie haszy obiektu X
; w rzeczywistości po prostu konwertuje X
na ciąg (poprzez, .toString()
jeśli jest to obiekt lub inne wbudowane konwersje dla różnych typów pierwotnych), a następnie wyszukuje ten ciąg, bez mieszania go, w „ hash
”. Równość obiektów również nie jest sprawdzana - jeśli dwa różne obiekty mają taką samą konwersję łańcucha, po prostu się nawzajem zastąpią.
Biorąc to pod uwagę - czy są jakieś wydajne implementacje skrótów w javascript? (Na przykład drugi wynik Google javascript hashmap
daje implementację, która jest O (n) dla każdej operacji. Różne inne wyniki ignorują fakt, że różne obiekty z równoważnymi reprezentacjami ciągu zastępują się nawzajem.
Odpowiedzi:
Dlaczego nie haszować obiektów samodzielnie i używać wynikowych ciągów jako kluczy do zwykłego słownika JavaScript? W końcu jesteś w najlepszej pozycji, aby wiedzieć, co czyni twoje obiekty wyjątkowymi. To jest to co robię.
Przykład:
W ten sposób możesz kontrolować indeksowanie wykonywane przez JavaScript bez nadmiernego zwiększania alokacji pamięci i obsługi przepełnienia.
Oczywiście, jeśli naprawdę chcesz „rozwiązania klasy przemysłowej”, możesz zbudować klasę sparametryzowaną kluczową funkcją i wszystkimi niezbędnymi interfejsami API kontenera, ale… używamy JavaScript i staramy się być proste i lekkie, więc to funkcjonalne rozwiązanie jest proste i szybkie.
Funkcja klucza może być tak prosta, jak wybranie odpowiednich atrybutów obiektu, np. Klucza lub zestawu kluczy, które są już unikalne, kombinacji kluczy, które są unikalne razem, lub tak złożonej, jak użycie niektórych skrótów kryptograficznych, takich jak w Kodowaniu DojoX lub UUID DojoX . Podczas gdy te ostatnie rozwiązania mogą wytwarzać unikalne klucze, osobiście staram się ich unikać za wszelką cenę, zwłaszcza jeśli wiem, co czyni moje obiekty wyjątkowymi.
Aktualizacja w 2014 roku: Odpowiedzi w 2008 roku to proste rozwiązanie wciąż wymaga dodatkowych wyjaśnień. Pozwól, że wyjaśnię ten pomysł w formie pytań i odpowiedzi.
Twoje rozwiązanie nie ma prawdziwego skrótu. Gdzie to jest???
JavaScript jest językiem wysokiego poziomu. Jego podstawowa operacja podstawowa ( Obiekt ) zawiera tablicę skrótów, aby zachować właściwości. Ta tablica skrótów jest zwykle napisana w języku niskiego poziomu w celu zwiększenia wydajności. Używając prostego obiektu z kluczami łańcuchowymi, używamy wydajnie zaimplementowanej tabeli skrótów bez żadnego wysiłku z naszej strony.
Skąd wiesz, że używają skrótu?
Istnieją trzy główne sposoby utrzymywania kolekcji obiektów możliwych do adresowania za pomocą klucza:
Oczywiście obiekty JavaScript używają tabel skrótów w jakiejś formie do obsługi ogólnych przypadków.
Czy dostawcy przeglądarek naprawdę używają tabel skrótów?
Naprawdę.
Czy radzą sobie z kolizjami?
Tak. Patrz wyżej. Jeśli znalazłeś kolizję na nierównych ciągach, nie wahaj się zgłosić błędu do dostawcy.
Jaki masz pomysł?
Jeśli chcesz zaszyfrować obiekt, znajdź jego wyjątkowość i użyj go jako klucza. Nie próbuj obliczać rzeczywistego skrótu ani emulować tabel skrótów - jest już skutecznie obsługiwany przez podstawowy obiekt JavaScript.
Użyj tego klucza w JavaScript,
Object
aby wykorzystać wbudowaną tabelę skrótów, jednocześnie unikając możliwych kolizji z domyślnymi właściwościami.Przykłady na początek:
Wykorzystałem twoją sugestię i zbuforowałem wszystkie obiekty przy użyciu nazwy użytkownika. Ale jakiś mądry facet nazywa się „toString”, co jest wbudowaną właściwością! Co mam teraz zrobić?
Oczywiście, jeśli jest nawet możliwe, że wynikowy klucz będzie składał się wyłącznie ze znaków łacińskich, powinieneś coś z tym zrobić. Na przykład dodaj dowolny znak spoza alfabetu łacińskiego, który lubisz na początku lub na końcu, aby usunąć niezgodność z domyślnymi właściwościami: „#toString”, „#MarySmith”. Jeśli używany jest klucz złożony, należy oddzielić komponenty klucza za pomocą pewnego rodzaju niełacińskiego separatora: „nazwa, miasto, stan”.
Ogólnie jest to miejsce, w którym musimy być kreatywni i wybierać najłatwiejsze klucze z podanymi ograniczeniami (unikalność, potencjalne kolizje z domyślnymi właściwościami).
Uwaga: unikalne klucze nie kolidują z definicji, podczas gdy potencjalne konflikty skrótów będą obsługiwane przez instrument bazowy
Object
.Dlaczego nie lubisz rozwiązań przemysłowych?
IMHO, najlepszy kod w ogóle nie jest kodem: nie zawiera błędów, nie wymaga konserwacji, jest łatwy do zrozumienia i wykonuje się natychmiast. Wszystkie „tabele skrótów w JavaScript”, które widziałem, zawierały> 100 wierszy kodu i obejmowały wiele obiektów. Porównaj go z:
dict[key] = value
.Kolejna kwestia: czy w ogóle można pokonać wydajność pierwotnego obiektu napisanego w języku niskiego poziomu, używając JavaScript i tych samych pierwotnych obiektów, aby zaimplementować to, co już zostało zaimplementowane?
Nadal chcę mieszać moje obiekty bez żadnych kluczy!
Mamy szczęście: ECMAScript 6 (zaplanowany na wydanie w połowie 2015 r., Upowszechnienie lub potrwa 1-2 lata) definiuje mapę i zestaw .
Sądząc po definicji, mogą używać adresu obiektu jako klucza, dzięki czemu obiekty są natychmiast odróżniane bez sztucznych kluczy. OTOH, dwa różne, ale identyczne obiekty, zostaną zamapowane jako odrębne.
Zestawienie porównawcze z MDN :
źródło
Opis problemu
JavaScript nie ma wbudowanego ogólnego typu mapy (zwanego czasem tablicą asocjacyjną lub słownikiem ), który umożliwia dostęp do dowolnych wartości za pomocą dowolnych kluczy. Podstawową strukturą danych JavaScript jest obiekt , specjalny typ mapy, która akceptuje tylko ciągi jako klucze i ma specjalną semantykę, taką jak dziedziczenie prototypowe, metody pobierające i ustawiające oraz kilka innych voodoo.
Kiedy używasz obiektów jako map, musisz pamiętać, że klucz zostanie przekonwertowany na wartość ciągu poprzez
toString()
, co spowoduje mapowanie5
i'5'
na tę samą wartość oraz wszystkie obiekty, które nie nadpisujątoString()
metody na wartość indeksowaną przez'[object Object]'
. Możesz również nieświadomie uzyskać dostęp do jego odziedziczonych właściwości, jeśli nie zaznaczyszhasOwnProperty()
.Wbudowane funkcje Javascript w tablicy typu nie pomaga ani trochę: tablice JavaScript nie są asocjacyjnych, ale tylko obiekty z kilkoma właściwościami bardziej wyjątkowym. Jeśli chcesz wiedzieć, dlaczego nie można ich używać jako map, spójrz tutaj .
Rozwiązanie Eugene'a
Eugene Lazutkin już opisał podstawową ideę używania niestandardowej funkcji skrótu do generowania unikatowych ciągów, których można użyć do wyszukiwania powiązanych wartości jako właściwości obiektu słownika. Najprawdopodobniej będzie to najszybsze rozwiązanie, ponieważ obiekty są wewnętrznie implementowane jako tabele skrótów .
Aby uzyskać unikalną wartość skrótu dla dowolnych obiektów, jedną z możliwości jest użycie globalnego licznika i buforowanie wartości skrótu w samym obiekcie (np. W nazwie o nazwie
__hash
).Funkcja skrótu, która to robi i działa zarówno dla pierwotnych wartości, jak i obiektów, to:
Z tej funkcji można korzystać zgodnie z opisem Eugene'a. Dla wygody dodatkowo zawiniemy go w
Map
klasę.Mój
Map
realizacjaPoniższa implementacja będzie dodatkowo przechowywać pary klucz-wartość na podwójnie połączonej liście, aby umożliwić szybką iterację zarówno kluczy, jak i wartości. Aby podać własną funkcję skrótu, możesz zastąpić
hash()
metodę instancji po utworzeniu.Przykład
Poniższy skrypt
generuje ten wynik:
Dalsze uwagi
PEZ zaproponował zastąpienie
toString()
metody, prawdopodobnie za pomocą naszej funkcji skrótu. Nie jest to możliwe, ponieważ nie działa dla prymitywnych wartości (zmianatoString()
na prymitywy to bardzo zły pomysł). Jeśli chcemytoString()
zwrócić znaczące wartości dla dowolnych obiektów, musielibyśmy zmodyfikowaćObject.prototype
, co niektórzy ludzie (ja nie wliczając) uważają za dosłowne .Edycja: bieżącą wersję mojej
Map
implementacji, a także inne dodatki JavaScript można uzyskać tutaj .źródło
Map._counter = 0
i w Konstruktorze map takthis._hash = 'object ' + Map._counter++
. Następnie hash () staje sięreturn (value && value._hash) || (typeof(value) + ' ' + String(value));
Wiem, że to pytanie jest dość stare, ale istnieją obecnie naprawdę świetne rozwiązania z bibliotekami zewnętrznymi.
JavaScript ma również swój język
Map
.źródło
Oto prosty i wygodny sposób korzystania z czegoś podobnego do mapy Java:
Aby uzyskać wartość:
źródło
Według ECMAScript 2015 (ES6) standardowy javascript ma implementację mapy. Więcej o tym można znaleźć tutaj
Podstawowe użycie:
źródło
Możesz użyć ES6
WeakMap
lubMap
:Pamiętaj, że żadna z nich nie jest szeroko obsługiwana, ale możesz używać ES6 Shim (wymaga natywnego ES5 lub ES5 Shim ) do obsługi
Map
, ale nieWeakMap
( zobacz dlaczego ).źródło
Będziesz musiał przechowywać w parach wewnętrznych par par obiekt / wartość
I użyj go jako takiego:
Oczywiście, ta implementacja jest również gdzieś na linii O (n). Powyższe przykłady Eugene'a to jedyny sposób na uzyskanie skrótu, który działa z dowolną prędkością, jakiej można oczekiwać od prawdziwego skrótu.
Aktualizacja:
Innym podejściem, zgodnym z odpowiedzią Eugene'a, jest jakoś dołączyć unikalny identyfikator do wszystkich obiektów. Jednym z moich ulubionych podejść jest pobranie jednej z wbudowanych metod odziedziczonych po nadklasie Object, zastąpienie jej funkcją przejścia niestandardowego i dołączenie właściwości do tego obiektu funkcji. Jeśli miałbyś przepisać moją metodę HashMap, aby to zrobić, wyglądałoby to tak:
Ta wersja wydaje się być tylko nieco szybsza, ale teoretycznie będzie znacznie szybsza w przypadku dużych zestawów danych.
źródło
Niestety, żadna z powyższych odpowiedzi nie była dobra w moim przypadku: różne kluczowe obiekty mogą mieć ten sam kod skrótu. Dlatego napisałem prostą wersję HashMap w stylu Java:
Uwaga: kluczowe obiekty muszą „implementować” metody hashCode () i equals ().
źródło
new Array()
przejęcia[]
jest zapewnienie absolutnej java-podobieństwo kodu? :)Zaimplementowałem JavaScript HashMap, którego kod można uzyskać ze strony http://github.com/lambder/HashMapJS/tree/master
Oto kod:
źródło
HashMap
sach.W ECMA6 możesz użyć WeakMap
Przykład:
Ale:
źródło
JavaScript nie buduje mapy / mapy skrótów. Powinien być nazywany tablicą asocjacyjną .
hash["X"]
jest równahash.X
, ale pozwala „X” jako zmienną łańcuchową. Innymi słowy,hash[x]
jest funkcjonalnie równaeval("hash."+x.toString())
Jest bardziej podobny do object.properties niż do mapowania klucz-wartość. Jeśli szukasz lepszego mapowania Klucz / wartość w JavaScript, użyj obiektu Map, który możesz znaleźć w Internecie.
źródło
Wypróbuj moją implementację tabeli skrótów JavaScript: http://www.timdown.co.uk/jshashtable
Wyszukuje metodę hashCode () kluczowych obiektów lub można podać funkcję haszującą podczas tworzenia obiektu Hashtable.
źródło
Wygląda to na całkiem solidne rozwiązanie: https://github.com/flesler/hashmap . Będzie nawet działał dobrze dla funkcji i obiektów, które wyglądają identycznie. Jedynym włamaniem, jakiego używa, jest dodanie do obiektu niejasnego elementu członkowskiego w celu jego identyfikacji. Jeśli twój program nie zastąpi tej niejasnej zmiennej (jej czegoś w rodzaju hashid ), jesteś złoty.
źródło
Jeżeli wydajność nie jest krytyczna (np ilość klawiszy jest stosunkowo niewielka) i nie chcesz, aby zanieczyścić (lub może nie swojej) obiektów z dodatkowych pól, takich jak
_hash
,_id
itp, to można skorzystać z faktu, żeArray.prototype.indexOf
zatrudnia ścisła równość. Oto prosta implementacja:Przykład użycia:
W porównaniu do ES6 WeakMap ma dwa problemy: O (n) czas wyszukiwania i brak słabości (tj. Spowoduje wyciek pamięci, jeśli nie użyjesz
delete
lubclear
nie zwolnisz klawiszy).źródło
Implementacja mojej mapy, pochodząca z przykładu Christopha:
Przykładowe użycie:
źródło
Dodanie kolejnego rozwiązania:
HashMap
to właściwie pierwsza klasa, którą przeniosłem z Javy na JavaScript. Można powiedzieć, że istnieje duży narzut, ale implementacja jest prawie w 100% równa implementacji Java i obejmuje wszystkie interfejsy i podklasy.Projekt można znaleźć tutaj: https://github.com/Airblader/jsava Dołączę również (aktualny) kod źródłowy dla klasy HashMap, ale jak już wspomniano, zależy to również od superklasy itp. Użyty framework OOP jest qooxdoo.
Edycja: Pamiętaj, że ten kod jest już przestarzały i zapoznaj się z projektem github dla bieżącej pracy. W chwili pisania tego jest również
ArrayList
implementacja.źródło
Jeszcze jedna implementacja mapy przeze mnie. Z randomizerem, „rodzajami” i „iteratorem” =)
Przykład:
źródło