جافا سكريبت Hashmap يعادل
https://stackoverflow.com/questions/368280
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
كما هو موضح في التحديث 3 بتاريخ هذه الإجابة, ، هذا التدوين:
var hash = {};
hash[X]
لا يقوم فعليًا بتجزئة الكائن X;إنه في الواقع مجرد تحويل X إلى سلسلة (عبر .toString() إذا كان كائنًا، أو بعض التحويلات المضمنة الأخرى لأنواع بدائية مختلفة) ثم يبحث عن تلك السلسلة، دون تجزئتها، في "hash".لم يتم أيضًا التحقق من مساواة الكائنات - إذا كان هناك كائنين مختلفين لهما نفس تحويل السلسلة، فسوف يقومان بالكتابة فوق بعضهما البعض.
بالنظر إلى هذا - هل هناك أي تطبيقات فعالة لخرائط التجزئة في جافا سكريبت؟(على سبيل المثال، نتيجة Google الثانية لـ javascript hashmap ينتج عنه تنفيذ وهو O(n) لأي عملية.تتجاهل النتائج الأخرى المختلفة حقيقة أن الكائنات المختلفة ذات تمثيلات السلسلة المكافئة تقوم بالكتابة فوق بعضها البعض.
المحلول
لماذا لا تقوم بتجزئة الكائنات بنفسك يدويًا، وتستخدم السلاسل الناتجة كمفاتيح لقاموس جافا سكريبت العادي؟بعد كل شيء، أنت في أفضل وضع لمعرفة ما الذي يجعل الأشياء الخاصة بك فريدة من نوعها.هذا ما افعله.
مثال:
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 دون زيادة كبيرة في تخصيص الذاكرة والتعامل مع الفائض.
بالطبع، إذا كنت تريد حقًا "الحل الصناعي"، فيمكنك إنشاء فئة محددة بواسطة الوظيفة الرئيسية، ومع كل واجهة برمجة التطبيقات الضرورية للحاوية، ولكن ... نحن نستخدم JavaScript، ونحاول أن نكون بسيطين وخفيفين الوزن، لذلك هذا الحل الوظيفي بسيط وسريع.
يمكن أن تكون وظيفة المفتاح بسيطة مثل اختيار السمات الصحيحة للكائن، على سبيل المثال، مفتاح أو مجموعة من المفاتيح، التي تكون فريدة بالفعل، أو مجموعة من المفاتيح، التي تكون فريدة معًا، أو معقدة مثل استخدام بعض تجزئات التشفير مثل في ترميز دوجوكس, ، أو دوجوكس UUID.في حين أن الحلول الأخيرة قد تنتج مفاتيح فريدة، فأنا شخصيًا أحاول تجنبها بأي ثمن، خاصة إذا كنت أعرف ما الذي يجعل كائناتي فريدة من نوعها.
التحديث في عام 2014: تمت الإجابة على هذا الحل البسيط في عام 2008 ولا يزال يتطلب المزيد من التوضيحات.اسمحوا لي أن أوضح الفكرة في شكل سؤال وجواب.
الحل الخاص بك لا يحتوي على تجزئة حقيقية.أين هي؟؟؟
جافا سكريبت هي لغة عالية المستوى.بدائية أساسية (هدف) يتضمن جدول التجزئة للحفاظ على الخصائص.عادةً ما يتم كتابة جدول التجزئة بلغة منخفضة المستوى من أجل الكفاءة.باستخدام كائن بسيط مع مفاتيح سلسلة، نستخدم جدول تجزئة تم تنفيذه بكفاءة دون بذل أي جهد من جانبنا.
كيف تعرف أنهم يستخدمون التجزئة؟
هناك ثلاث طرق رئيسية للاحتفاظ بمجموعة من الكائنات قابلة للعنونة بواسطة مفتاح:
- غير مرتبة.في هذه الحالة، لاسترداد كائن ما بواسطة مفتاحه، علينا مراجعة جميع المفاتيح التي تتوقف عند العثور عليه.في المتوسط، سيستغرق الأمر مقارنات n/2.
- أمر.
- مثال 1:مصفوفة مرتبة - عند إجراء بحث ثنائي، سنجد مفتاحنا بعد مقارنات ~log2(n) في المتوسط.أفضل بكثير.
- المثال رقم 2:شجرة.مرة أخرى ستكون محاولات ~log(n).
- جدول التجزئة.في المتوسط، يتطلب الأمر وقتًا ثابتًا.يقارن:يا (ن) مقابل.O(سجل ن) مقابل.يا(1).فقاعة.
من الواضح أن كائنات JavaScript تستخدم جداول التجزئة بشكل ما للتعامل مع الحالات العامة.
هل يستخدم بائعو المتصفح جداول التجزئة حقًا؟؟؟
حقًا.
- كروم/node.js/V8: JSObject.بحثقاموس الاسم واسم القاموس الشكل مع التفاصيل ذات الصلة في كائنات.ccو الكائنات-inl.h.
- ثعلب النار/وزغة: JSObject, NativeObject, ، وكائن عادي مع التفاصيل ذات الصلة فيjsobj.cpp وvm/NativeObject.cpp.
هل يتعاملون مع الاصطدامات؟
نعم.أنظر فوق.إذا وجدت تضاربًا في سلاسل غير متساوية، فيرجى عدم التردد في الإبلاغ عن خطأ إلى أحد البائعين.
إذن ما هي فكرتك؟
إذا كنت تريد تجزئة كائن ما، فابحث عن ما يجعله فريدًا واستخدمه كمفتاح.لا تحاول حساب التجزئة الحقيقية أو محاكاة جداول التجزئة - فقد تم التعامل معها بكفاءة بالفعل بواسطة كائن JavaScript الأساسي.
استخدم هذا المفتاح مع JavaScript Object للاستفادة من جدول التجزئة المدمج الخاص به مع الابتعاد عن التعارضات المحتملة مع الخصائص الافتراضية.
أمثلة للبدء:
- إذا كانت كائناتك تتضمن اسم مستخدم فريدًا - فاستخدمه كمفتاح.
- إذا كان يتضمن رقم عميل فريدًا - فاستخدمه كمفتاح.
- إذا كان يتضمن أرقامًا فريدة صادرة عن الحكومة مثل رقم التأمين الاجتماعي (SSN) أو رقم جواز السفر، وكان نظامك لا يسمح بالنسخ المكررة - فاستخدمه كمفتاح.
- إذا كانت مجموعة الحقول فريدة من نوعها، فاستخدمها كمفتاح.
- يعد اختصار الولاية + رقم رخصة القيادة مفتاحًا ممتازًا.
- يعد اختصار البلد + رقم جواز السفر مفتاحًا ممتازًا أيضًا.
- يمكن لبعض الوظائف في الحقول، أو كائن كامل، إرجاع قيمة فريدة - استخدمها كمفتاح.
لقد استخدمت اقتراحك وقمت بتخزين جميع الكائنات مؤقتًا باستخدام اسم المستخدم.لكن هناك رجل حكيم يُدعى "toString"، وهي خاصية مدمجة!ماذا يجب ان افعل الان؟
من الواضح أنه إذا كان من الممكن، ولو ولو ولو بشكل بسيط، أن يتكون المفتاح الناتج حصريًا من أحرف لاتينية، فيجب عليك أن تفعل شيئًا حيال ذلك.على سبيل المثال، أضف أي حرف Unicode غير لاتيني تريده في البداية أو في النهاية لإلغاء التعارض مع الخصائص الافتراضية:"#toString"، "#MarySmith".إذا تم استخدام مفتاح مركب، فافصل المكونات الرئيسية باستخدام نوع من المحددات غير اللاتينية:"الاسم، المدينة، الولاية".
بشكل عام، هذا هو المكان الذي يجب أن نكون فيه مبدعين، وأن نختار المفاتيح الأسهل ذات القيود المحددة (التفرد، والاشتباكات المحتملة مع الخصائص الافتراضية).
ملحوظة:المفاتيح الفريدة لا تتعارض بحكم التعريف، في حين سيتم التعامل مع تعارضات التجزئة المحتملة بواسطة العناصر الأساسية Object.
لماذا لا تحب الحلول الصناعية؟
IMHO، أفضل رمز هو عدم وجود رمز على الإطلاق:فهو لا يحتوي على أخطاء، ولا يتطلب صيانة، وسهل الفهم، ويتم تنفيذه على الفور.جميع "جداول التجزئة في JavaScript" التي رأيتها كانت عبارة عن أكثر من 100 سطر من التعليمات البرمجية، وتتضمن كائنات متعددة.قارنها مع: dict[key] = value.
نقطة اخرى:هل من الممكن حتى التغلب على أداء كائن بدائي مكتوب بلغة منخفضة المستوى، باستخدام جافا سكريبت ونفس الكائنات البدائية لتنفيذ ما تم تنفيذه بالفعل؟
ما زلت أرغب في تجزئة الكائنات الخاصة بي دون أي مفاتيح!
نحن محظوظون:يحدد ECMAScript 6 (المقرر إصداره في منتصف عام 2015، أو يزيد أو يستغرق سنة أو سنتين بعد ذلك ليصبح منتشرًا على نطاق واسع)خريطة وتعيين.
انطلاقًا من التعريف، يمكنهم استخدام عنوان الكائن كمفتاح، مما يجعل الكائنات متميزة على الفور بدون مفاتيح صناعية.سيتم تعيين OTOH، وهما كائنان مختلفان ولكن متطابقان، على أنهما مختلفان.
تفصيل المقارنة من MDN:
تشبه الكائنات الخرائط التي يتيح لك كلاهما تعيين مفاتيح للقيم ، واسترداد تلك القيم ، وحذف المفاتيح ، واكتشاف ما إذا كان يتم تخزين شيء ما في المفتاح.لهذا السبب (ولأنه لم تكن هناك بدائل مدمجة) ، فقد تم استخدام الأشياء كخرائط تاريخياً ؛ومع ذلك ، هناك اختلافات مهمة تجعل استخدام خريطة أفضل في بعض الحالات:
- مفاتيح الكائن هي سلاسل ورموز، في حين أنها يمكن أن تكون أي قيمة للخريطة، بما في ذلك الوظائف والكائنات وأي شيء بدائي.
- يتم ترتيب المفاتيح الموجودة في الخريطة بينما لا يتم ترتيب المفاتيح المضافة إلى الكائن.وبالتالي ، عند التكرار فوقه ، يقوم كائن MAP بإرجاع المفاتيح بترتيب الإدراج.
- يمكنك الحصول على حجم الخريطة بسهولة باستخدام خاصية الحجم، بينما يجب تحديد عدد الخصائص في الكائن يدويًا.
- الخريطة هي أمر غير قابل للتكرار ، وبالتالي يمكن تكراره مباشرة ، في حين أن التكرار على كائن يتطلب الحصول على مفاتيحها بطريقة ما وتكرار عليها.
- يحتوي الكائن على نموذج أولي، لذا توجد مفاتيح افتراضية في الخريطة يمكن أن تتصادم مع مفاتيحك إذا لم تكن حذرًا.اعتبارًا من ES5 ، يمكن تجاوز هذا باستخدام map = object.create (null) ، ولكن نادراً ما يتم ذلك.
- قد يكون أداء الخريطة أفضل في السيناريوهات التي تتضمن إضافة وإزالة أزواج المفاتيح بشكل متكرر.
نصائح أخرى
وصف المشكلة
جافا سكريبت ليس لديه المدمج في العام خريطة اكتب (يسمى أحيانًا مصفوفة متصلة أو قاموس) والذي يسمح بالوصول إلى القيم التعسفية عن طريق مفاتيح عشوائية.بنية البيانات الأساسية لجافا سكريبت هي هدف, ، نوع خاص من الخرائط التي تقبل فقط السلاسل كمفاتيح ولها دلالات خاصة مثل الميراث النموذجي، والحروف والمحددات وبعض الشعوذة الإضافية.
عند استخدام الكائنات كخرائط، عليك أن تتذكر أنه سيتم تحويل المفتاح إلى قيمة سلسلة عبر toString(), ، مما يؤدي إلى رسم الخرائط 5 و '5' إلى نفس القيمة وجميع الكائنات التي لا تقوم بالكتابة فوق toString() طريقة القيمة المفهرسة بواسطة '[object Object]'.يمكنك أيضًا الوصول بشكل لا إرادي إلى خصائصه الموروثة إذا لم تقم بالتحقق hasOwnProperty().
جافا سكريبت المدمج في مجموعة مصفوفة النوع لا يساعد بت واحد:مصفوفات JavaScript ليست مصفوفات ترابطية، ولكنها مجرد كائنات ذات خصائص خاصة قليلة.إذا كنت تريد معرفة سبب عدم إمكانية استخدامها كخرائط، انظر هنا.
حل يوجين
وصف يوجين لازوتكين بالفعل الفكرة الأساسية لاستخدام دالة تجزئة مخصصة لإنشاء سلاسل فريدة يمكن استخدامها للبحث عن القيم المرتبطة كخصائص لكائن القاموس.من المرجح أن يكون هذا هو الحل الأسرع، لأنه يتم تنفيذ الكائنات داخليًا على أنها جداول التجزئة.
- ملحوظة: جداول التجزئة (تسمى أحيانًا خرائط التجزئة) هي تطبيق خاص لمفهوم الخريطة باستخدام مصفوفة دعم والبحث عبر قيم التجزئة الرقمية.قد تستخدم بيئة وقت التشغيل هياكل أخرى (مثل ابحث عن الأشجار أو تخطي القوائم) لتنفيذ كائنات JavaScript، ولكن نظرًا لأن الكائنات هي بنية البيانات الأساسية، فيجب تحسينها بشكل كافٍ.
من أجل الحصول على قيمة تجزئة فريدة للكائنات العشوائية، يتمثل أحد الاحتمالات في استخدام عداد عام وتخزين قيمة التجزئة مؤقتًا في الكائن نفسه (على سبيل المثال، في خاصية مسماة __hash).
دالة التجزئة التي تقوم بذلك وتعمل مع كل من القيم والكائنات البدائية هي:
function hash(value) {
return (typeof value) + ' ' + (value instanceof Object ?
(value.__hash || (value.__hash = ++arguments.callee.current)) :
value.toString());
}
hash.current = 0;
يمكن استخدام هذه الوظيفة كما وصفها يوجين.للراحة، سنقوم بتغليفها أيضًا في ملف 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, ، وهو ما يعتبره بعض الأشخاص (وأنا لست منهم). محظور.
يحرر: الإصدار الحالي من بلدي Map التنفيذ بالإضافة إلى أشياء أخرى جيدة في JavaScript يمكن الحصول عليها من هنا.
أعلم أن هذا السؤال قديم جدًا، ولكن هناك بعض الحلول الرائعة حقًا في الوقت الحاضر مع المكتبات الخارجية.
جافا سكريبت لديها أيضا لغتها المقدمة Map أيضًا.
إليك طريقة سهلة ومريحة لاستخدام شيء مشابه لخريطة جافا:
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 .....
يمكنك استخدام ES6 WeakMap أو Map:
WeakMaps عبارة عن خرائط للمفاتيح/القيم تكون فيها المفاتيح كائنات.
Mapالكائنات عبارة عن خرائط مفاتيح/قيمة بسيطة.يمكن استخدام أي قيمة (سواء الكائنات أو القيم الأولية) كمفتاح أو قيمة.
انتبه إلى أن أيًا منهما غير مدعوم على نطاق واسع، ولكن يمكنك استخدامه ES6 شيم (يتطلب ES5 الأصلي أو ES5 شيم) من أجل دعم Map, ، لكن لا WeakMap (شاهد لماذا).
وفقًا لـ ECMAScript 2015 (ES6)، تحتوي جافا سكريبت القياسية على تطبيق Map.المزيد حول ما يمكن العثور عليه هنا
الاستخدام الأساسي:
var myMap = new Map();
var keyString = "a string",
keyObj = {},
keyFunc = function () {};
// setting the values
myMap.set(keyString, "value associated with 'a string'");
myMap.set(keyObj, "value associated with keyObj");
myMap.set(keyFunc, "value associated with keyFunc");
myMap.size; // 3
// getting the values
myMap.get(keyString); // "value associated with 'a string'"
myMap.get(keyObj); // "value associated with keyObj"
myMap.get(keyFunc); // "value associated with keyFunc"
سيتعين عليك تخزين بعض مقاطع الحالة الداخلية لأزواج الكائنات/القيمة
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).أمثلة يوجين أعلاه هي الطريقة الوحيدة للحصول على تجزئة تعمل بأي نوع من السرعة التي تتوقعها من تجزئة حقيقية.
تحديث:
هناك طريقة أخرى، على غرار إجابة يوجين، تتمثل في إرفاق معرف فريد لجميع الكائنات بطريقة أو بأخرى.إحدى الطرق المفضلة لدي هي استخدام إحدى الطرق المضمنة الموروثة من فئة الكائن الفائقة، واستبدالها بعبور وظيفة مخصصة وإرفاق خصائص بكائن الوظيفة هذا.إذا كنت تريد إعادة كتابة أسلوب 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];
}
ويبدو أن هذا الإصدار أسرع قليلاً فقط، ولكنه من الناحية النظرية سيكون أسرع بشكل ملحوظ بالنسبة لمجموعات البيانات الكبيرة.
لسوء الحظ، لم تكن أي من الإجابات المذكورة أعلاه جيدة لحالتي:قد تحتوي الكائنات الرئيسية المختلفة على نفس رمز التجزئة.لذلك، كتبت إصدارًا بسيطًا يشبه Java مثل HashMap:
function HashMap() {
this.buckets = {};
}
HashMap.prototype.put = function(key, value) {
var hashCode = key.hashCode();
var bucket = this.buckets[hashCode];
if (!bucket) {
bucket = new Array();
this.buckets[hashCode] = bucket;
}
for (var i = 0; i < bucket.length; ++i) {
if (bucket[i].key.equals(key)) {
bucket[i].value = value;
return;
}
}
bucket.push({ key: key, value: value });
}
HashMap.prototype.get = function(key) {
var hashCode = key.hashCode();
var bucket = this.buckets[hashCode];
if (!bucket) {
return null;
}
for (var i = 0; i < bucket.length; ++i) {
if (bucket[i].key.equals(key)) {
return bucket[i].value;
}
}
}
HashMap.prototype.keys = function() {
var keys = new Array();
for (var hashKey in this.buckets) {
var bucket = this.buckets[hashKey];
for (var i = 0; i < bucket.length; ++i) {
keys.push(bucket[i].key);
}
}
return keys;
}
HashMap.prototype.values = function() {
var values = new Array();
for (var hashKey in this.buckets) {
var bucket = this.buckets[hashKey];
for (var i = 0; i < bucket.length; ++i) {
values.push(bucket[i].value);
}
}
return values;
}
ملحوظة:يجب أن تقوم الكائنات الرئيسية "بتنفيذ" أساليب hashCode() وequals().
في ECMA6 يمكنك استخدامه خريطة ضعيفة
مثال:
var wm1 = new WeakMap(),
wm2 = new WeakMap(),
wm3 = new WeakMap();
var o1 = {},
o2 = function(){},
o3 = window;
wm1.set(o1, 37);
wm1.set(o2, "azerty");
wm2.set(o1, o2); // a value can be anything, including an object or a function
wm2.set(o3, undefined);
wm2.set(wm1, wm2); // keys and values can be any objects. Even WeakMaps!
wm1.get(o2); // "azerty"
wm2.get(o2); // undefined, because there is no value for o2 on wm2
wm2.get(o3); // undefined, because that is the set value
wm1.has(o2); // true
wm2.has(o2); // false
wm2.has(o3); // true (even if the value itself is 'undefined')
wm3.set(o1, 37);
wm3.get(o1); // 37
wm3.clear();
wm3.get(o1); // undefined, because wm3 was cleared and there is no value for o1 anymore
wm1.has(o1); // true
wm1.delete(o1);
wm1.has(o1); // false
لكن:
Because of references being weak, WeakMap keys are not enumerable (i.e. there is no method giving you a list of the keys).
لقد قمت بتطبيق 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")
}
لا يقوم جافا سكريبت ببناء Map/hashmap.ينبغي أن يسمى مصفوفة متصلة.
hash["X"] يساوي hash.X, ، لكن اسمح بـ "X" كمتغير سلسلة.بعبارة أخرى، hash[x] يساوي وظيفيا ل eval("hash."+x.toString())
وهو يشبه إلى حد كبير object.properties بدلاً من تعيين قيمة المفتاح.إذا كنت تبحث عن تعيين أفضل للمفتاح/القيمة في Javascript، فيرجى استخدام كائن الخريطة الذي يمكنك العثور عليه على الويب.
جرب تنفيذ جدول تجزئة JavaScript الخاص بي: http://www.timdown.co.uk/jshashtable
فهو يبحث عن طريقة hashCode() للكائنات الرئيسية، أو يمكنك توفير وظيفة التجزئة عند إنشاء كائن Hashtable.
يبدو أن هذا حل قوي جدًا: https://github.com/flesler/hashmap .بل إنها ستعمل بشكل جيد مع الوظائف والكائنات التي تبدو متطابقة.الاختراق الوحيد الذي يستخدمه هو إضافة عضو غامض إلى كائن للتعرف عليه.إذا لم يقوم برنامجك بالكتابة فوق هذا المتغير الغامض (إنه شيء من هذا القبيل حاشد)، أنت ذهبي.
إذا لم يكن الأداء حرجًا (على سبيل المثال.كمية المفاتيح صغيرة نسبيًا) ولا تريد تلويث كائناتك (أو ربما ليس كائناتك) بحقول إضافية مثل _hash, _id, وما إلى ذلك، فيمكنك الاستفادة من حقيقة ذلك Array.prototype.indexOf يستخدم المساواة الصارمة.هنا تنفيذ بسيط:
var Dict = (function(){
// IE 8 and earlier has no Array.prototype.indexOf
function indexOfPolyfill(val) {
for (var i = 0, l = this.length; i < l; ++i) {
if (this[i] === val) {
return i;
}
}
return -1;
}
function Dict(){
this.keys = [];
this.values = [];
if (!this.keys.indexOf) {
this.keys.indexOf = indexOfPolyfill;
}
};
Dict.prototype.has = function(key){
return this.keys.indexOf(key) != -1;
};
Dict.prototype.get = function(key, defaultValue){
var index = this.keys.indexOf(key);
return index == -1 ? defaultValue : this.values[index];
};
Dict.prototype.set = function(key, value){
var index = this.keys.indexOf(key);
if (index == -1) {
this.keys.push(key);
this.values.push(value);
} else {
var prevValue = this.values[index];
this.values[index] = value;
return prevValue;
}
};
Dict.prototype.delete = function(key){
var index = this.keys.indexOf(key);
if (index != -1) {
this.keys.splice(index, 1);
return this.values.splice(index, 1)[0];
}
};
Dict.prototype.clear = function(){
this.keys.splice(0, this.keys.length);
this.values.splice(0, this.values.length);
};
return Dict;
})();
مثال للاستخدام:
var a = {}, b = {},
c = { toString: function(){ return '1'; } },
d = 1, s = '1', u = undefined, n = null,
dict = new Dict();
// keys and values can be anything
dict.set(a, 'a');
dict.set(b, 'b');
dict.set(c, 'c');
dict.set(d, 'd');
dict.set(s, 's');
dict.set(u, 'u');
dict.set(n, 'n');
dict.get(a); // 'a'
dict.get(b); // 'b'
dict.get(s); // 's'
dict.get(u); // 'u'
dict.get(n); // 'n'
// etc.
بالمقارنة مع ES6 WeakMap، هناك مشكلتان:O(n) وقت البحث وعدم الضعف (أيسوف يتسبب في تسرب الذاكرة إذا لم تستخدمه delete أو clear لتحرير المفاتيح).
تنفيذ خريطتي، مستمد من مثال كريستوف:
مثال للاستخدام:
var map = new Map(); //creates an "in-memory" map
var map = new Map("storageId"); //creates a map that is loaded/persisted using html5 storage
function Map(storageId) {
this.current = undefined;
this.size = 0;
this.storageId = storageId;
if (this.storageId) {
this.keys = new Array();
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)];
if (item === undefined) {
if (this.storageId) {
try {
var itemStr = localStorage.getItem(this.storageId + key);
if (itemStr && itemStr !== 'undefined') {
item = JSON.parse(itemStr);
this[this.hash(key)] = item;
this.keys.push(key);
++this.size;
}
} catch (e) {
console.log(e);
}
}
}
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;
if (this.storageId) {
this.keys.push(key);
try {
localStorage.setItem(this.storageId + key, JSON.stringify(this[hash]));
} catch (e) {
console.log(e);
}
}
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];
}
if (this.storageId) {
try {
localStorage.setItem(this.storageId + key, undefined);
} catch (e) {
console.log(e);
}
}
return this;
};
// only works if linked
Map.prototype.removeAll = function() {
if (this.storageId) {
for (var i=0; i<this.keys.length; i++) {
this.remove(this.keys[i]);
}
this.keys.length = 0;
} else {
while(this.size)
this.remove(this.key());
}
return this;
};
// --- linked list helper functions
Map.prototype.link = function(item) {
if (this.storageId) {
return;
}
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.storageId) {
return;
}
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() {
if (this.storageId) {
return undefined;
} else {
return this.current.key;
}
};
Map.prototype.value = function() {
if (this.storageId) {
return undefined;
}
return this.current.value;
};
إضافة حل آخر: HashMap هي إلى حد كبير الدرجة الأولى التي قمت بنقلها من Java إلى Javascript.يمكنك القول أن هناك الكثير من النفقات العامة، ولكن التنفيذ يعادل تقريبًا 100% تنفيذ Java ويتضمن جميع الواجهات والفئات الفرعية.
يمكن العثور على المشروع هنا: https://github.com/Airblader/jsavaسأقوم أيضًا بإرفاق كود المصدر (الحالي) لفئة HashMap، ولكن كما هو مذكور فإنه يعتمد أيضًا على الفئة الفائقة وما إلى ذلك.إطار عمل OOP المستخدم هو qooxdoo.
يحرر: يرجى ملاحظة أن هذا الرمز قديم بالفعل والرجوع إلى مشروع جيثب للعمل الحالي.حتى كتابة هذا المقال، هناك أيضًا ArrayList تطبيق.
qx.Class.define( 'jsava.util.HashMap', {
extend: jsava.util.AbstractMap,
implement: [jsava.util.Map, jsava.io.Serializable, jsava.lang.Cloneable],
construct: function () {
var args = Array.prototype.slice.call( arguments ),
initialCapacity = this.self( arguments ).DEFAULT_INITIAL_CAPACITY,
loadFactor = this.self( arguments ).DEFAULT_LOAD_FACTOR;
switch( args.length ) {
case 1:
if( qx.Class.implementsInterface( args[0], jsava.util.Map ) ) {
initialCapacity = Math.max( ((args[0].size() / this.self( arguments ).DEFAULT_LOAD_FACTOR) | 0) + 1,
this.self( arguments ).DEFAULT_INITIAL_CAPACITY );
loadFactor = this.self( arguments ).DEFAULT_LOAD_FACTOR;
} else {
initialCapacity = args[0];
}
break;
case 2:
initialCapacity = args[0];
loadFactor = args[1];
break;
}
if( initialCapacity < 0 ) {
throw new jsava.lang.IllegalArgumentException( 'Illegal initial capacity: ' + initialCapacity );
}
if( initialCapacity > this.self( arguments ).MAXIMUM_CAPACITY ) {
initialCapacity = this.self( arguments ).MAXIMUM_CAPACITY;
}
if( loadFactor <= 0 || isNaN( loadFactor ) ) {
throw new jsava.lang.IllegalArgumentException( 'Illegal load factor: ' + loadFactor );
}
var capacity = 1;
while( capacity < initialCapacity ) {
capacity <<= 1;
}
this._loadFactor = loadFactor;
this._threshold = (capacity * loadFactor) | 0;
this._table = jsava.JsavaUtils.emptyArrayOfGivenSize( capacity, null );
this._init();
},
statics: {
serialVersionUID: 1,
DEFAULT_INITIAL_CAPACITY: 16,
MAXIMUM_CAPACITY: 1 << 30,
DEFAULT_LOAD_FACTOR: 0.75,
_hash: function (hash) {
hash ^= (hash >>> 20) ^ (hash >>> 12);
return hash ^ (hash >>> 7) ^ (hash >>> 4);
},
_indexFor: function (hashCode, length) {
return hashCode & (length - 1);
},
Entry: qx.Class.define( 'jsava.util.HashMap.Entry', {
extend: jsava.lang.Object,
implement: [jsava.util.Map.Entry],
construct: function (hash, key, value, nextEntry) {
this._value = value;
this._next = nextEntry;
this._key = key;
this._hash = hash;
},
members: {
_key: null,
_value: null,
/** @type jsava.util.HashMap.Entry */
_next: null,
/** @type Number */
_hash: 0,
getKey: function () {
return this._key;
},
getValue: function () {
return this._value;
},
setValue: function (newValue) {
var oldValue = this._value;
this._value = newValue;
return oldValue;
},
equals: function (obj) {
if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.HashMap.Entry ) ) {
return false;
}
/** @type jsava.util.HashMap.Entry */
var entry = obj,
key1 = this.getKey(),
key2 = entry.getKey();
if( key1 === key2 || (key1 !== null && key1.equals( key2 )) ) {
var value1 = this.getValue(),
value2 = entry.getValue();
if( value1 === value2 || (value1 !== null && value1.equals( value2 )) ) {
return true;
}
}
return false;
},
hashCode: function () {
return (this._key === null ? 0 : this._key.hashCode()) ^
(this._value === null ? 0 : this._value.hashCode());
},
toString: function () {
return this.getKey() + '=' + this.getValue();
},
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
_recordAccess: function (map) {
},
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
_recordRemoval: function (map) {
}
}
} )
},
members: {
/** @type jsava.util.HashMap.Entry[] */
_table: null,
/** @type Number */
_size: 0,
/** @type Number */
_threshold: 0,
/** @type Number */
_loadFactor: 0,
/** @type Number */
_modCount: 0,
/** @implements jsava.util.Set */
__entrySet: null,
/**
* Initialization hook for subclasses. This method is called
* in all constructors and pseudo-constructors (clone, readObject)
* after HashMap has been initialized but before any entries have
* been inserted. (In the absence of this method, readObject would
* require explicit knowledge of subclasses.)
*/
_init: function () {
},
size: function () {
return this._size;
},
isEmpty: function () {
return this._size === 0;
},
get: function (key) {
if( key === null ) {
return this.__getForNullKey();
}
var hash = this.self( arguments )._hash( key.hashCode() );
for( var entry = this._table[this.self( arguments )._indexFor( hash, this._table.length )];
entry !== null; entry = entry._next ) {
/** @type jsava.lang.Object */
var k;
if( entry._hash === hash && ((k = entry._key) === key || key.equals( k )) ) {
return entry._value;
}
}
return null;
},
__getForNullKey: function () {
for( var entry = this._table[0]; entry !== null; entry = entry._next ) {
if( entry._key === null ) {
return entry._value;
}
}
return null;
},
containsKey: function (key) {
return this._getEntry( key ) !== null;
},
_getEntry: function (key) {
var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() );
for( var entry = this._table[this.self( arguments )._indexFor( hash, this._table.length )];
entry !== null; entry = entry._next ) {
/** @type jsava.lang.Object */
var k;
if( entry._hash === hash
&& ( ( k = entry._key ) === key || ( key !== null && key.equals( k ) ) ) ) {
return entry;
}
}
return null;
},
put: function (key, value) {
if( key === null ) {
return this.__putForNullKey( value );
}
var hash = this.self( arguments )._hash( key.hashCode() ),
i = this.self( arguments )._indexFor( hash, this._table.length );
for( var entry = this._table[i]; entry !== null; entry = entry._next ) {
/** @type jsava.lang.Object */
var k;
if( entry._hash === hash && ( (k = entry._key) === key || key.equals( k ) ) ) {
var oldValue = entry._value;
entry._value = value;
entry._recordAccess( this );
return oldValue;
}
}
this._modCount++;
this._addEntry( hash, key, value, i );
return null;
},
__putForNullKey: function (value) {
for( var entry = this._table[0]; entry !== null; entry = entry._next ) {
if( entry._key === null ) {
var oldValue = entry._value;
entry._value = value;
entry._recordAccess( this );
return oldValue;
}
}
this._modCount++;
this._addEntry( 0, null, value, 0 );
return null;
},
__putForCreate: function (key, value) {
var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
i = this.self( arguments )._indexFor( hash, this._table.length );
for( var entry = this._table[i]; entry !== null; entry = entry._next ) {
/** @type jsava.lang.Object */
var k;
if( entry._hash === hash
&& ( (k = entry._key) === key || ( key !== null && key.equals( k ) ) ) ) {
entry._value = value;
return;
}
}
this._createEntry( hash, key, value, i );
},
__putAllForCreate: function (map) {
var iterator = map.entrySet().iterator();
while( iterator.hasNext() ) {
var entry = iterator.next();
this.__putForCreate( entry.getKey(), entry.getValue() );
}
},
_resize: function (newCapacity) {
var oldTable = this._table,
oldCapacity = oldTable.length;
if( oldCapacity === this.self( arguments ).MAXIMUM_CAPACITY ) {
this._threshold = Number.MAX_VALUE;
return;
}
var newTable = jsava.JsavaUtils.emptyArrayOfGivenSize( newCapacity, null );
this._transfer( newTable );
this._table = newTable;
this._threshold = (newCapacity * this._loadFactor) | 0;
},
_transfer: function (newTable) {
var src = this._table,
newCapacity = newTable.length;
for( var j = 0; j < src.length; j++ ) {
var entry = src[j];
if( entry !== null ) {
src[j] = null;
do {
var next = entry._next,
i = this.self( arguments )._indexFor( entry._hash, newCapacity );
entry._next = newTable[i];
newTable[i] = entry;
entry = next;
} while( entry !== null );
}
}
},
putAll: function (map) {
var numKeyToBeAdded = map.size();
if( numKeyToBeAdded === 0 ) {
return;
}
if( numKeyToBeAdded > this._threshold ) {
var targetCapacity = (numKeyToBeAdded / this._loadFactor + 1) | 0;
if( targetCapacity > this.self( arguments ).MAXIMUM_CAPACITY ) {
targetCapacity = this.self( arguments ).MAXIMUM_CAPACITY;
}
var newCapacity = this._table.length;
while( newCapacity < targetCapacity ) {
newCapacity <<= 1;
}
if( newCapacity > this._table.length ) {
this._resize( newCapacity );
}
}
var iterator = map.entrySet().iterator();
while( iterator.hasNext() ) {
var entry = iterator.next();
this.put( entry.getKey(), entry.getValue() );
}
},
remove: function (key) {
var entry = this._removeEntryForKey( key );
return entry === null ? null : entry._value;
},
_removeEntryForKey: function (key) {
var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
i = this.self( arguments )._indexFor( hash, this._table.length ),
prev = this._table[i],
entry = prev;
while( entry !== null ) {
var next = entry._next,
/** @type jsava.lang.Object */
k;
if( entry._hash === hash
&& ( (k = entry._key) === key || ( key !== null && key.equals( k ) ) ) ) {
this._modCount++;
this._size--;
if( prev === entry ) {
this._table[i] = next;
} else {
prev._next = next;
}
entry._recordRemoval( this );
return entry;
}
prev = entry;
entry = next;
}
return entry;
},
_removeMapping: function (obj) {
if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.Map.Entry ) ) {
return null;
}
/** @implements jsava.util.Map.Entry */
var entry = obj,
key = entry.getKey(),
hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
i = this.self( arguments )._indexFor( hash, this._table.length ),
prev = this._table[i],
e = prev;
while( e !== null ) {
var next = e._next;
if( e._hash === hash && e.equals( entry ) ) {
this._modCount++;
this._size--;
if( prev === e ) {
this._table[i] = next;
} else {
prev._next = next;
}
e._recordRemoval( this );
return e;
}
prev = e;
e = next;
}
return e;
},
clear: function () {
this._modCount++;
var table = this._table;
for( var i = 0; i < table.length; i++ ) {
table[i] = null;
}
this._size = 0;
},
containsValue: function (value) {
if( value === null ) {
return this.__containsNullValue();
}
var table = this._table;
for( var i = 0; i < table.length; i++ ) {
for( var entry = table[i]; entry !== null; entry = entry._next ) {
if( value.equals( entry._value ) ) {
return true;
}
}
}
return false;
},
__containsNullValue: function () {
var table = this._table;
for( var i = 0; i < table.length; i++ ) {
for( var entry = table[i]; entry !== null; entry = entry._next ) {
if( entry._value === null ) {
return true;
}
}
}
return false;
},
clone: function () {
/** @type jsava.util.HashMap */
var result = null;
try {
result = this.base( arguments );
} catch( e ) {
if( !qx.Class.isSubClassOf( e.constructor, jsava.lang.CloneNotSupportedException ) ) {
throw e;
}
}
result._table = jsava.JsavaUtils.emptyArrayOfGivenSize( this._table.length, null );
result.__entrySet = null;
result._modCount = 0;
result._size = 0;
result._init();
result.__putAllForCreate( this );
return result;
},
_addEntry: function (hash, key, value, bucketIndex) {
var entry = this._table[bucketIndex];
this._table[bucketIndex] = new (this.self( arguments ).Entry)( hash, key, value, entry );
if( this._size++ >= this._threshold ) {
this._resize( 2 * this._table.length );
}
},
_createEntry: function (hash, key, value, bucketIndex) {
var entry = this._table[bucketIndex];
this._table[bucketIndex] = new (this.self( arguments ).Entry)( hash, key, value, entry );
this._size++;
},
keySet: function () {
var keySet = this._keySet;
return keySet !== null ? keySet : ( this._keySet = new this.KeySet( this ) );
},
values: function () {
var values = this._values;
return values !== null ? values : ( this._values = new this.Values( this ) );
},
entrySet: function () {
return this.__entrySet0();
},
__entrySet0: function () {
var entrySet = this.__entrySet;
return entrySet !== null ? entrySet : ( this.__entrySet = new this.EntrySet( this ) );
},
/** @private */
HashIterator: qx.Class.define( 'jsava.util.HashMap.HashIterator', {
extend: jsava.lang.Object,
implement: [jsava.util.Iterator],
type: 'abstract',
/** @protected */
construct: function (thisHashMap) {
this.__thisHashMap = thisHashMap;
this._expectedModCount = this.__thisHashMap._modCount;
if( this.__thisHashMap._size > 0 ) {
var table = this.__thisHashMap._table;
while( this._index < table.length && ( this._next = table[this._index++] ) === null ) {
// do nothing
}
}
},
members: {
__thisHashMap: null,
/** @type jsava.util.HashMap.Entry */
_next: null,
/** @type Number */
_expectedModCount: 0,
/** @type Number */
_index: 0,
/** @type jsava.util.HashMap.Entry */
_current: null,
hasNext: function () {
return this._next !== null;
},
_nextEntry: function () {
if( this.__thisHashMap._modCount !== this._expectedModCount ) {
throw new jsava.lang.ConcurrentModificationException();
}
var entry = this._next;
if( entry === null ) {
throw new jsava.lang.NoSuchElementException();
}
if( (this._next = entry._next) === null ) {
var table = this.__thisHashMap._table;
while( this._index < table.length && ( this._next = table[this._index++] ) === null ) {
// do nothing
}
}
this._current = entry;
return entry;
},
remove: function () {
if( this._current === null ) {
throw new jsava.lang.IllegalStateException();
}
if( this.__thisHashMap._modCount !== this._expectedModCount ) {
throw new jsava.lang.ConcurrentModificationException();
}
var key = this._current._key;
this._current = null;
this.__thisHashMap._removeEntryForKey( key );
this._expectedModCount = this.__thisHashMap._modCount;
}
}
} ),
_newKeyIterator: function () {
return new this.KeyIterator( this );
},
_newValueIterator: function () {
return new this.ValueIterator( this );
},
_newEntryIterator: function () {
return new this.EntryIterator( this );
},
/** @private */
ValueIterator: qx.Class.define( 'jsava.util.HashMap.ValueIterator', {
extend: jsava.util.HashMap.HashIterator,
construct: function (thisHashMap) {
this.base( arguments, thisHashMap );
},
members: {
next: function () {
return this._nextEntry()._value;
}
}
} ),
/** @private */
KeyIterator: qx.Class.define( 'jsava.util.HashMap.KeyIterator', {
extend: jsava.util.HashMap.HashIterator,
construct: function (thisHashMap) {
this.base( arguments, thisHashMap );
},
members: {
next: function () {
return this._nextEntry().getKey();
}
}
} ),
/** @private */
EntryIterator: qx.Class.define( 'jsava.util.HashMap.EntryIterator', {
extend: jsava.util.HashMap.HashIterator,
construct: function (thisHashMap) {
this.base( arguments, thisHashMap );
},
members: {
next: function () {
return this._nextEntry();
}
}
} ),
/** @private */
KeySet: qx.Class.define( 'jsava.util.HashMap.KeySet', {
extend: jsava.util.AbstractSet,
construct: function (thisHashMap) {
this.base( arguments );
this.__thisHashMap = thisHashMap;
},
members: {
__thisHashMap: null,
iterator: function () {
return this.__thisHashMap._newKeyIterator();
},
size: function () {
return this.__thisHashMap._size;
},
contains: function (obj) {
return this.__thisHashMap.containsKey( obj );
},
remove: function (obj) {
return this.__thisHashMap._removeEntryForKey( obj ) !== null;
},
clear: function () {
this.__thisHashMap.clear();
}
}
} ),
/** @private */
Values: qx.Class.define( 'jsava.util.HashMap.Values', {
extend: jsava.util.AbstractCollection,
construct: function (thisHashMap) {
this.base( arguments );
this.__thisHashMap = thisHashMap;
},
members: {
__thisHashMap: null,
iterator: function () {
return this.__thisHashMap._newValueIterator();
},
size: function () {
return this.__thisHashMap._size;
},
contains: function (obj) {
return this.__thisHashMap.containsValue( obj );
},
clear: function () {
this.__thisHashMap.clear();
}
}
} ),
/** @private */
EntrySet: qx.Class.define( 'jsava.util.HashMap.EntrySet', {
extend: jsava.util.AbstractSet,
construct: function (thisHashMap) {
this.base( arguments );
this.__thisHashMap = thisHashMap;
},
members: {
__thisHashMap: null,
iterator: function () {
return this.__thisHashMap._newEntryIterator();
},
size: function () {
return this.__thisHashMap._size;
},
contains: function (obj) {
if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.Map.Entry ) ) {
return false;
}
/** @implements jsava.util.Map.Entry */
var entry = obj,
candidate = this.__thisHashMap._getEntry( entry.getKey() );
return candidate !== null && candidate.equals( entry );
},
remove: function (obj) {
return this.__thisHashMap._removeMapping( obj ) !== null;
},
clear: function () {
this.__thisHashMap.clear();
}
}
} )
}
} );
تنفيذ خريطة أخرى بواسطتي.باستخدام أداة التوزيع العشوائي و"الأدوية العامة" و"المكرر" =)
var HashMap = function (TKey, TValue) {
var db = [];
var keyType, valueType;
(function () {
keyType = TKey;
valueType = TValue;
})();
var getIndexOfKey = function (key) {
if (typeof key !== keyType)
throw new Error('Type of key should be ' + keyType);
for (var i = 0; i < db.length; i++) {
if (db[i][0] == key)
return i;
}
return -1;
}
this.add = function (key, value) {
if (typeof key !== keyType) {
throw new Error('Type of key should be ' + keyType);
} else if (typeof value !== valueType) {
throw new Error('Type of value should be ' + valueType);
}
var index = getIndexOfKey(key);
if (index === -1)
db.push([key, value]);
else
db[index][1] = value;
return this;
}
this.get = function (key) {
if (typeof key !== keyType || db.length === 0)
return null;
for (var i = 0; i < db.length; i++) {
if (db[i][0] == key)
return db[i][1];
}
return null;
}
this.size = function () {
return db.length;
}
this.keys = function () {
if (db.length === 0)
return [];
var result = [];
for (var i = 0; i < db.length; i++) {
result.push(db[i][0]);
}
return result;
}
this.values = function () {
if (db.length === 0)
return [];
var result = [];
for (var i = 0; i < db.length; i++) {
result.push(db[i][1]);
}
return result;
}
this.randomize = function () {
if (db.length === 0)
return this;
var currentIndex = db.length, temporaryValue, randomIndex;
while (0 !== currentIndex) {
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex--;
temporaryValue = db[currentIndex];
db[currentIndex] = db[randomIndex];
db[randomIndex] = temporaryValue;
}
return this;
}
this.iterate = function (callback) {
if (db.length === 0)
return false;
for (var i = 0; i < db.length; i++) {
callback(db[i][0], db[i][1]);
}
return true;
}
}
مثال:
var a = new HashMap("string", "number");
a.add('test', 1132)
.add('test14', 666)
.add('1421test14', 12312666)
.iterate(function (key, value) {console.log('a['+key+']='+value)});
/*
a[test]=1132
a[test14]=666
a[1421test14]=12312666
*/
a.randomize();
/*
a[1421test14]=12312666
a[test]=1132
a[test14]=666
*/
