الانتقال من التحقيق الخطي إلى التحقيق التربيعي (هاش كوليسون)

Question

يستخدم تنفيذي الحالي لجدول التجزئة التحقيق الخطي ، والآن أريد الانتقال إلى التحقيق التربيعي (وبعد ذلك إلى التسلسل وربما مزدوج التجزئة أيضًا). لقد قرأت بعض المقالات والدروس التعليمية ، ويكيبيديا ، إلخ ... لكنني ما زلت لا أعرف بالضبط ما يجب علي فعله.

التحقيق الخطي ، في الأساس ، لديه خطوة 1 ومن السهل القيام بذلك. عند البحث أو إدراج أو إزالة عنصر من جدول التجزئة ، أحتاج إلى حساب تجزئة ولهذا أقوم بذلك:

index = hash_function(key) % table_size;

بعد ذلك ، أثناء البحث أو الإدخال أو الإزالة في الجدول حتى أجد دلوًا مجانيًا ، مثل هذا:

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + 1) % table_size;
    }
while(/* LOOP UNTIL IT'S NECESSARY */);

بالنسبة للتحقيق التربيعي ، أعتقد أن ما أحتاج إلى فعله هو تغيير كيف يتم حساب حجم خطوة "الفهرس" ، لكن هذا ما لا أفهمه كيف يجب أن أفعل ذلك. لقد رأيت قطعًا مختلفة من التعليمات البرمجية ، وكلها مختلفة إلى حد ما.

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

تعديل:بعد قراءة كل شيء أشار إليه إيلي بيندرسكي أدناه ، أعتقد أنني حصلت على الفكرة العامة. إليك جزء من الكود في http://eternallyconfuzzled.com/tuts/datuctures/jsw_tut_hashtable.aspx:

15   for ( step = 1; table->table[h] != EMPTY; step++ ) {
16     if ( compare ( key, table->table[h] ) == 0 )
17       return 1;
18 
19     /* Move forward by quadratically, wrap if necessary */
20     h = ( h + ( step * step - step ) / 2 ) % table->size;
21   }

هناك شيئان لا أحصل عليهما ... يقولان إن التحقيق التربيعي عادة ما يتم استخدامه c(i)=i^2. ومع ذلك ، في الكود أعلاه ، فإنه يفعل شيئًا أكثر مثل c(i)=(i^2-i)/2

كنت مستعدًا لتنفيذ هذا على الكود الخاص بي ، لكنني سأفعل ببساطة:

index = (index + (index^index)) % table_size;

...و لا:

index = (index + (index^index - index)/2) % table_size;

إذا كان أي شيء ، سأفعل:

index = (index + (index^index)/2) % table_size;

... لأنني رأيت أمثلة رمز أخرى تغوص بمقدار اثنين. على الرغم من أنني لا أفهم لماذا ...

1) لماذا يطرح الخطوة؟
2) لماذا يغوصها بحلول 2؟

Answer 1

ليس عليك تعديل وظيفة التجزئة للتحقيق التربيعي. أبسط أشكال التحقيق التربيعي هو في الحقيقة مجرد إضافة المربعات المترتبة على الموضع المحسوب بدلاً من الخطي 1 ، 2 ، 3.

هناك مورد جيد هنا. ما يلي مأخوذ من هناك. هذا هو أبسط شكل من أشكال التحقيق التربيعي عندما يكون متعدد الحدود البسيط c(i) = i^2 يستخدم:

في الحالة الأكثر عمومية ، تكون الصيغة هي:

ويمكنك اختيار ثوابتك.

ومع ذلك ، ضع في اعتبارك أن التحقيق التربيعي مفيد فقط في بعض الحالات. كما دخول ويكيبيديا تنص على:

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

---

تعديل: مثل أشياء كثيرة في علوم الكمبيوتر ، فإن الثوابت الدقيقة والعديد من التحقيق التربيعي هي مجريات الأمور. نعم ، أبسط أشكال هو i^2, ، ولكن يمكنك اختيار أي كثير الحدود. ويكيبيديا يعطي المثال مع h(k,i) = (h(k) + i + i^2)(mod m).

لذلك ، من الصعب الإجابة على سؤال "لماذا". "لماذا" الوحيد هنا هو لماذا تحتاج إلى تحقيق تربيعي على الإطلاق؟ هل لديك مشاكل مع أشكال أخرى من التحقيق والحصول على طاولة مجمعة؟ أم أنها مجرد واجب منزلي أم تعلم الذات؟

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

Answer 2

هناك طريقة بسيطة وأنيقة بشكل خاص لتنفيذ التحقيق التربيعي إذا كان حجم الجدول الخاص بك قوة 2:

step = 1;

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + step) % table_size;
        step++;
    }
} while(/* LOOP UNTIL IT'S NECESSARY */);

بدلاً من النظر إلى الإزاحة 0 ، 1 ، 2 ، 3 ، 4 ... من الفهرس الأصلي ، فإن هذا سوف ينظر إلى الإزاحة 0 ، 1 ، 3 ، 6 ، 10 ...^ذ التحقيق في الإزاحة (i*(i+1))/2 ، أي أنه تربيعي).

هذا مضمون لضرب كل موقف في جدول التجزئة (لذلك أنت مضمون للعثور على دلو فارغ إذا كان هناك واحد) قدمت حجم الجدول هو قوة 2.

---

هنا رسم لدليل:

1. بالنظر إلى حجم جدول N ، نريد أن نظهر أننا سنحصل على قيم مميزة لـ (i*(i+1))/2 (mod n) مع i = 0 ... n-1.
2. يمكننا إثبات هذا عن طريق التناقض. افترض أن هناك أقل من قيم متميزة: إذا كان الأمر كذلك ، فيجب أن يكون هناك على الأقل قيمتان صحيحتان متميزتان لـ I في النطاق [0 ، N-1] بحيث (i*(i+1))/2 (mod n ) هو نفسه. استدعاء هذه p و q ، حيث p <q.
3. IE (P * (P+1)) / 2 = (Q * (Q+1)) / 2 (Mod N)
4. => (ص² + P) / 2 = (Q² + Q) / 2 (mod n)
5. => ص² + p = q² + س (وزارة الدفاع 2N)
6. => س² - ص² + q - p = 0 (mod 2n)
7. Factorise => (Q - P) (P + Q + 1) = 0 (Mod 2n)
8. (q - p) = 0 هي الحالة التافهة p = q.
9. (p + q + 1) = 0 (mod 2n) مستحيل: يجب أن تكون قيمنا من p و q في النطاق [0 ، n-1] ، و q> p ، لذلك (p + q + 1) يجب أن تكون في النطاق [2 ، 2n-2].
10. نظرًا لأننا نعمل Modulo 2n ، يجب علينا أيضًا التعامل مع الحالة الصعبة حيث يكون كلا العاملين غير صفريين ، لكنهما مضاعفان لإعطاء 0 (Mod 2n):
    • لاحظ أن الفرق بين العاملين (Q - P) و (P + Q + 1) هو (2p + 1) ، وهو رقم فردي - لذلك يجب أن يكون أحد العوامل متساوية ، والآخر يجب أن يكون غريبًا.
    • (q - p) (p + q + 1) = 0 (mod 2n) => (q - p) (p + q + 1) قابلة للقسمة على 2n. إذا كانت n (وبالتالي 2n) قوة 2, ، هذا يتطلب من العامل حتى أن يكون مضاعف 2N (لأن جميع العوامل الأولية 2N هي 2 ، في حين أن أي من العوامل الأولية لعاملنا الغريب هي).
    • ولكن (Q-P) لها قيمة أقصى لـ N-1 ، و (P + Q + 1) لها قيمة أقصى قدرها 2N-2 (كما هو موضح في الخطوة 9) ، لذلك لا يمكن أن يكون مضاعف 2N.
    • لذلك هذه الحالة مستحيلة كذلك.
11. لذلك ، يجب أن يكون الافتراض أن هناك أقل من قيم متميزة (في الخطوة 2) خاطئة.

(إذا كان حجم الجدول ليس قوة 2 ، هذا ينهار في الخطوة 10.)