قم بإنشاء جدول تجزئة مع صفيفتين

Question

هل يعرف أي شخص كيفية القيام بذلك وما هو رمز الزائفة الذي سيبدو عليه؟

كما نعلم جميعًا مفتاح تخزين جدول التجزئة ، وأزواج القيمة ، وعندما يتم استدعاء المفتاح ، ستعيد الوظيفة القيمة المرتبطة بهذا المفتاح. ما أريد القيام به هو فهم الهيكل الأساسي في إنشاء وظيفة التعيين هذه. على سبيل المثال ، إذا عشنا في عالم لا توجد فيه وظائف محددة مسبقًا باستثناء المصفوفات ، فكيف يمكننا تكرار hashmaps التي لدينا اليوم؟

Answer 1

في الواقع ، فإن بعض نواري هاشماب اليوم مصنوعة بالفعل من المصفوفات كما تقترح. اسمحوا لي أن أرسم كيف يعمل هذا:

دالة تجزئةتقوم دالة التجزئة بتحويل مفاتيحك إلى فهرس للمصفوفة الأولى (Array K). يمكن استخدام وظيفة التجزئة مثل MD5 أو وظيفة أبسط ، بما في ذلك مشغل Modulo ، لهذا الغرض.

دلاءيمكن أن يستخدم تطبيق HashMap البسيط المستند إلى مجموعة الدلاء للتعامل مع التجميع. يحتوي كل عنصر ("دلو") في Array K على صفيف (صفيف P) من الأزواج. عند إضافة أو الاستعلام عن عنصر ما ، تشيرك وظيفة التجزئة إلى الدلو الصحيح في K ، والذي يحتوي على صفيفك المطلوب P. ثم تكرر العناصر في P حتى تجد مفتاح مطابقة ، أو تقوم بتعيين عنصر جديد في نهاية P.

رسم خرائط للدلو باستخدام التجزئةيجب عليك التأكد من أن عدد الدلاء (أي حجم K) هو قوة 2 ، دعنا نقول 2^ب. للعثور على فهرس الجرافة الصحيح لبعض المفاتيح ، حساب التجزئة (مفتاح) ولكن فقط احتفظ بتات B الأولى. هذا هو الفهرس الخاص بك عندما يلقي إلى عدد صحيح.

إعادة القياسحساب تجزئة المفتاح وإيجاد الدلو الصحيح سريع للغاية. ولكن بمجرد أن يصبح الدلو أكمل ، سيتعين عليك تكرار المزيد والمزيد من العناصر قبل أن تصل إلى العناصر الصحيحة. لذلك من المهم أن يكون لديك ما يكفي من الدلاء لتوزيع الكائنات بشكل صحيح ، أو ستصبح HashMap بطيئة.

نظرًا لأنك لا تعرف عمومًا مقدار الكائنات التي ستحتاج إلى تخزينها في HashMap مقدمًا ، فمن المستحسن نمو الخريطة أو تقليصها ديناميكيًا. يمكنك الاحتفاظ بعدد عدد الكائنات المخزنة ، وبمجرد أن تتجاوز عتبة معينة ، تقوم بإعادة إنشاء الهيكل بأكمله ، ولكن هذه المرة بحجم أكبر أو أصغر للمصفوفة K. بهذه الطريقة سوف يكون الآن عناصرها كاملة عن عناصرها بين العديد من الدلاء ، بحيث يكون الأداء أفضل.

بدائليمكنك أيضًا استخدام صفيف ثنائي الأبعاد بدلاً من مجموعة من المباراة ، أو يمكنك تبادل Array P للحصول على قائمة مرتبطة. علاوة على ذلك ، بدلاً من الاحتفاظ بعدد إجمالي للكائنات المخزنة ، يمكنك ببساطة اختيار إعادة إنشاء (أي Rescale) HashMap بمجرد أن يحتوي أحد الدلاء على أكثر من عدد من العناصر المكوّنة.

تم وصف تباين ما تطلبه على أنه "جدول التجزئة" في جدول التجزئة ويكيبيديا.

شفرةلعينات الرمز ، ألقِ نظرة هنا.

أتمنى أن يساعدك هذا.

Answer 2

هل يمكن أن تكون أكثر دقة؟ هل تحتوي مجموعة واحدة على المفاتيح ، والآخر القيم؟

إذا كان الأمر كذلك ، فإليك مثال في Java (ولكن هناك عدد قليل من خصائص هذه اللغة هنا):

for (int i = 0; i < keysArray.length; i++) {
    map.put(keysArray[i], valuesArray[i]);
}

بالطبع ، سيتعين عليك إنشاء مثيل لك map كائن (إذا كنت تستخدم Java ، أقترح استخدام أ HashMap<Object, Object> بدلا من عتيقة HashTable) ، وكذلك اختبار المصفوفات الخاصة بك لتجنب null الكائنات وتحقق مما إذا كان لديهم نفس الحجم.

Answer 3

عينة التفسير:

في المصدر أدناه ، في الأساس شيئين:

1. تمثيل الخريطة

• بعض (عدد x من القائمة) من القوائم
• X كونه 2 Power N عدد القوائم أمر سيء. A (2 Power N) -1 ، أو (2 Power N) +1 ، أو عدد رئيسي جيد.

مثال:

List myhashmap [hash_table_size];
// an array of (short) lists
// if its long lists, then there are more collisions

ملاحظة: هذه مجموعة من المصفوفات ، وليس صفيفتين (لا يمكنني رؤية hashmap عام محتمل ، بطريقة جيدة مع صفيفتين فقط)

إذا كنت تعرف الخوارزميات> نظرية الرسم البياني> قائمة متاخمة ، فهذه تبدو بالضبط نفس.

2. وظيفة التجزئة

وتحول دالة التجزئة السلسلة (الإدخال) إلى رقم (قيمة التجزئة) ، وهو فهرس صفيف

• تهيئة قيمة التجزئة إلى First Char (بعد تحويلها إلى INT)
• لكل شار آخر ، التحول الأيسر 4 بت ، ثم أضف char (بعد تحويله إلى int)

مثال،

int hash = input[0];
for (int i=1; i<input.length(); i++) {
    hash = (hash << 4) + input[i]
}

hash = hash % list.size()
// list.size() here represents 1st dimension of (list of lists)
//      that is 1st dimension size of our map representation from point #1
//      which is hash_table_size

انظر في الرابط الأول:

int HTable::hash (char const * str) const

مصدر:
http://www.relisoft.com/book/lang/pointer/8hash.html
كيف يعمل جدول التجزئة؟

تحديث
هذا هو أفضل مصدر: http://algs4.cs.princeton.edu/34hash/

Answer 4

تقصد مثل هذا؟

ما يلي يستخدم روبي irb كتوضيح:

 cities = ["LA", "SF", "NY"]
 => ["LA", "SF", "NY"] 

 items = ["Big Mac", "Hot Fudge Sundae"]
 => ["Big Mac", "Hot Fudge Sundae"] 

 price = {}
 => {} 

 price[[cities[0], items[1]]] = 1.29
 => 1.29 

 price
 => {["LA", "Hot Fudge Sundae"]=>1.29} 

 price[[cities[0], items[0]]] = 2.49
 => 2.49 

 price[[cities[1], items[0]]] = 2.99
 => 2.99 

 price
 => {["LA", "Hot Fudge Sundae"]=>1.29, ["LA", "Big Mac"]=>2.49, ["SF", "Big Mac"]=>2.99} 

 price[["LA", "Big Mac"]]
 => 2.49