لماذا يستخدم hashCode() الخاص بـ Java في السلسلة 31 كمضاعف؟

Question

وفقًا لوثائق Java، فإن رمز التجزئة ل String يتم حساب الكائن على النحو التالي:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

استخدام int الحسابية، حيث s[i] هل أناالحرف العاشر من السلسلة، n هو طول الخيط، و ^ يدل على الأسي.

لماذا يتم استخدام 31 كمضاعف؟

أفهم أن المضاعف يجب أن يكون عددًا أوليًا كبيرًا نسبيًا.فلماذا لا يكون 29 أو 37 أو حتى 97؟

Answer 1

ووفقا ل الفعالة جافا (والكتاب الذي لا يمكن أن يكون أوصى بما فيه الكفاية، والتي اشتريت بفضل المستمر يذكر على ستاكوفيرفلوو):

<اقتباس فقرة>   

وقد تم اختيار قيمة 31 لأنه هو رئيس الوزراء الغريب. لو كان حتى وفاضت الضرب، سوف تضيع المعلومات، والضرب 2 وتعادل التحول. وميزة استخدام رئيس الحكومة هو أقل وضوحا، ولكنها التقليدي. خاصية جميلة من 31 هي أن الضرب يمكن الاستعاضة عن التحول والطرح للحصول على أداء أفضل: 31 * i == (i << 5) - i. نظام رصد السفن الحديثة تفعل هذا النوع من التحسين تلقائيا.

(من الفصل 3، البند 9: تجاوز دائما شفرة التجزئة عند تجاوز متساوين، صفحة 48)

Answer 2

غوودريتش وTamassia نشير، إذا كنت تأخذ أكثر من 50،000 الكلمات الإنجليزية (كما شكلت الاتحاد من قوائم الكلمات الواردة في نوعين مختلفين من يونكس)، وذلك باستخدام الثوابت 31، 33، 37، 39، و 41 سوف تنتج أقل من 7 التصادم في كل حالة. هذا مع العلم، فإنه ينبغي أن يكون مفاجئا أن العديد من تطبيقات جافا اختيار واحد من هذه الثوابت.

ومن قبيل الصدفة، كنت في منتصف قراءة قسم "رموز التجزئة متعدد الحدود" عندما رأيت هذا السؤال.

وتحرير: هنا هو ارتباط إلى ~ كتاب 10MB PDF انا مشيرا إلى أعلاه. انظر القسم 10.2 جداول التجزئة (صفحة 413) من <لأ href = "http://coltech.vnu.edu.vn/~sonpb/DSA/Data٪20Structures٪20and٪20Algorithms٪20in٪20Java،٪206th٪20Edition،٪ 202014.pdf "يختلط =" noreferrer "> هياكل البيانات والخوارزميات في جاوة

Answer 3

في (في الغالب) المعالجات القديمة، وضرب من قبل 31 يمكن أن تكون رخيصة نسبيا. على ARM، على سبيل المثال، فمن تعليمة واحدة فقط:

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

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

وانها ليست خوارزمية البعثرة كبيرة، ولكن من الجيد بما فيه الكفاية وأفضل من رمز 1.0 (وأفضل بكثير جدا من المواصفات 1.0!).

Answer 4

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

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

ووn * 31 التعبير ما يعادل (n << 5) - n.

Answer 5

يمكنك قراءة المنطق الأصلي لـ Bloch ضمن "التعليقات" في http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622.لقد قام بالتحقيق في أداء وظائف التجزئة المختلفة فيما يتعلق بـ "متوسط ​​حجم السلسلة" الناتج في جدول التجزئة. P(31) كانت إحدى الوظائف الشائعة خلال تلك الفترة والتي وجدها في كتاب K&R (ولكن حتى كيرنيغان وريتشي لم يستطيعا تذكر مصدرها).في النهاية كان عليه أن يختار واحدًا، وقد اختاره P(31) لأنه يبدو أنه يعمل بشكل جيد بما فيه الكفاية.بالرغم من P(33) لم يكن الأمر أسوأ حقًا وكان حساب الضرب في 33 سريعًا بنفس القدر (مجرد إزاحة بمقدار 5 وإضافة)، فقد اختار 31 نظرًا لأن 33 ليس عددًا أوليًا:

من الباقي أربعة ، ربما أختار P (31) ، لأنه أرخص حساب على RISC آلة (لأن 31 هو الفرق بين قوتين من اثنين).P (33) هو رخيصة بالمثل لحساب ، ولكن الأداء أسوأ بشكل هامشي ، و 33 مركب ، مما يجعلني متوترا بعض الشيء.

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

Answer 6

في الواقع، 37 سيكون جيدًا جدًا!z := 37 * x يمكن حسابها كـ y := x + 8 * x; z := x + 4 * y.تتوافق كلتا الخطوتين مع تعليمات LEA x86، لذا فإن هذا سريع للغاية.

في الواقع، الضرب باستخدام عدد أولي أكبر 73 يمكن القيام به بنفس السرعة عن طريق الإعداد y := x + 8 * x; z := x + 8 * y.

قد يكون استخدام 73 أو 37 (بدلاً من 31) أفضل، لأنه يؤدي إلى كود أكثر كثافة:تأخذ تعليمات LEA 6 بايت فقط مقابل 6 بايت فقط.البايتات السبعة للتحرك+التحويل+الطرح للضرب في 31.أحد التحذيرات المحتملة هو أن تعليمات LEA المكونة من 3 وسيطات المستخدمة هنا أصبحت أبطأ في بنية الجسر الرملي من Intel، مع زيادة زمن الوصول إلى 3 دورات.

علاوة على ذلك، 73 هو الرقم المفضل لشيلدون كوبر.

Answer 7

ونيل كوفي يفسر لماذا يستخدم 31 تحت الكي خارج التحيز .

وأساسا باستخدام 31 يعطيك التوزيع الاحتمالي وضع بت أكثر حتى لوظيفة التجزئة.

Answer 8

من جدك-4045622, ، حيث يصف جوشوا بلوخ الأسباب التي أدت إلى ذلك (الجديد) بالذات String.hashCode() تم اختيار التنفيذ

يلخص الجدول أدناه أداء التجزئة المختلفة الوظائف الموضحة أعلاه ، لثلاث مجموعات بيانات:

1) جميع الكلمات والعبارات مع إدخالات في Merriam-Webster's 2nd Int'l Unashortd Dictionary (311,141 سلسلة ، متوسط طول 10 أحرف).

2) جميع السلاسل في /bin/, ، /أوسر/بن/, ، /أوسر/ليب/, ، /usr/ucb/و /usr/openwin/bin/* (66304 سلسلة، متوسط ​​طولها 21 حرفًا).

3) قائمة بعناوين URL التي تم جمعها بواسطة زاحف الويب والتي تم تشغيلها لعدة ساعات الليلة الماضية (28,372 سلسلة، متوسط طول 49 حرفا).

مقياس الأداء الموضح في الجدول هو "متوسط حجم السلسلة" على جميع العناصر في جدول التجزئة (أي القيمة المتوقعة ل عدد المفاتيح يقارن للبحث عن عنصر).

                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439

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

أستبعد وظيفة WAIS لأن مواصفاتها تحتوي على صفحات من الأرقام العشوائية ، وأدائها ليس أفضل من أي من وظائف أبسط بكثير.أي من الوظائف الست المتبقية تبدو مثل خيارات ممتازة ، ولكن علينا اختيار واحد.أفترض أنني سأستبعد متغير Vo ووظيفة Weinberger بسبب إضافتهما التعقيد ، وإن كان طفيفا.من بين الأربعة المتبقية ، ربما سأختار P (31) ، لأنه أرخص حساب على جهاز RISC (لأن 31 هو الفرق بين قوتين من اثنين).P (33) رخيصة بالمثل ل احسب ، لكن أدائه أسوأ بشكل هامشي ، و 33 هو مركب ، مما يجعلني متوترة بعض الشيء.

جوش

Answer 9

ولست متأكدا، ولكن أود أن أعتقد أنها اختبار بعض العينات من الأعداد الأولية، ووجدت أن 31 أعطى أفضل توزيع على بعض العينات من سلاسل الممكنة.

Answer 10

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

الأرقام التي تتكون من استخدام التجزئة هي عادة:

• معامل نوع البيانات الذي تضعه فيه (2 ^ 32 أو 2 ^ 64)
• معامل عدد الجرافات في جدول التجزئة الخاص بك (يختلف.في جافا كانت أولية، الآن 2^n)
• الضرب أو التحويل برقم سحري في وظيفة الخلط
• قيمة الإدخال

لا يمكنك التحكم إلا في اثنتين من هذه القيم، لذا يلزمك القليل من العناية الإضافية.

Answer 11

في أحدث إصدار من JDK، لا يزال الإصدار 31 مستخدمًا. https://docs.Oracle.com/en/java/javase/11/docs/api/java.base/java/lang/String.html#hashCode()

الغرض من سلسلة التجزئة هو

• فريد (دعنا نرى عامل التشغيل ^ في مستند حساب رمز التجزئة، فهو يساعد بشكل فريد)
• تكلفة رخيصة لحساب

31 هي القيمة القصوى التي يمكن وضعها في سجل 8 بت (= 1 بايت).هو أكبر عدد أولي يمكن وضعه في سجل 1 بايت، وهو رقم فردي.

ضرب 31 هو <<5 ثم طرح نفسه، وبالتالي يحتاج إلى موارد رخيصة.