هل هاشماب جافا حقًا O(1)؟

Question

لقد رأيت بعض الادعاءات المثيرة للاهتمام حول خرائط تجزئة SO re Java و O(1) وقت البحث.هل يمكن لأحد أن يشرح لماذا يحدث هذا؟ما لم تكن خرائط التجزئة هذه مختلفة تمامًا عن أي من خوارزميات التجزئة التي تعلمت عليها، فيجب أن تكون هناك دائمًا مجموعة بيانات تحتوي على تصادمات.

في هذه الحالة، سيكون البحث O(n) بدلا من O(1).

يمكن للشخص أن يشرح ما إذا كانوا نكون س(1)، وإذا كان الأمر كذلك، كيف يتم تحقيق ذلك؟

Answer 1

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

ص_{الاصطدام} = ن / السعة

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

يا (ن) = يا (ك * ن)

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

ص_{الاصطدام × 2} = (ن / السعة)²

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

ص_{الاصطدام × ك} = (ن / السعة)^ك

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

نتحدث عن هذا بالقول أن خريطة التجزئة لديها وصول O(1). مع احتمال كبير

Answer 2

يبدو أنك تخلط بين سلوك الحالة الأسوأ ووقت تشغيل الحالة المتوسطة (المتوقع).الأول هو بالفعل O(n) لجداول التجزئة بشكل عام (أي.لا تستخدم التجزئة المثالية) ولكن هذا نادرًا ما يكون ذا صلة بالممارسة.

أي تنفيذ يمكن الاعتماد عليه لجدول التجزئة، إلى جانب تجزئة نصف لائقة، لديه أداء استرجاع لـ O(1) مع عامل صغير جدًا (2، في الواقع) في الحالة المتوقعة، ضمن هامش تباين ضيق جدًا.

Answer 3

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

وهكذا، وأحيانا سوف يكون لمقارنة ضد عدد قليل من البنود، ولكن عموما انها أقرب إلى O (1) من O (ن). لأغراض عملية، وهذا كل ما ينبغي عليك أن تعرف.

Answer 4

تذكر أن o(1) لا يعني أن كل عملية بحث تفحص عنصرًا واحدًا فقط - فهذا يعني أن متوسط ​​عدد العناصر التي تم فحصها يظل ثابتًا.عدد العناصر الموجودة في الحاوية.لذا، إذا كان الأمر يتطلب 4 مقارنات في المتوسط ​​للعثور على عنصر في حاوية تحتوي على 100 عنصر، فيجب أيضًا أن يستغرق الأمر 4 مقارنات في المتوسط ​​للعثور على عنصر في حاوية تحتوي على 10000 عنصر، ولأي عدد آخر من العناصر (هناك دائمًا قليل من التباين، خاصة حول النقاط التي يتم عندها إعادة صياغة جدول التجزئة، وعندما يكون هناك عدد صغير جدًا من العناصر).

لذا فإن الاصطدامات لا تمنع الحاوية من إجراء عمليات o(1)، طالما ظل متوسط ​​عدد المفاتيح لكل مجموعة ضمن حد ثابت.

Answer 5

وأعرف أن هذا هو السؤال القديم، ولكن هناك في الواقع إجابة جديدة لذلك.

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

ولكن ذلك لا يعني أن الوقت الحقيقي التعقيد O(n) - لأنه ليس هناك قاعدة تقول أن الدلاء يجب تنفيذ كقائمة الخطية.

في الواقع، جافا 8 تطبق دلاء كما TreeMaps بمجرد أن يتجاوز عتبة، الأمر الذي يجعل O(log n) الوقت الفعلي.

Answer 6

وإذا كان عدد المجموعات (نسميها ب) ثابتة (حالة المعتادة)، ثم البحث هو في الواقع O (ن).
ون يحصل كبير، وعدد من العناصر في كل المتوسطات دلو ن / ب. إذا لم يفعل قرار الاصطدام في واحدة من الطرق المعتادة (قائمة مرتبطة على سبيل المثال)، ثم البحث هو O (ن / ب) = O (ن).

والتدوين O هو حول ما يحدث عندما يحصل ن أكبر وأكبر. ويمكن أن يكون مضللا عندما يطبق على بعض الخوارزميات، والجداول التجزئة هي مثال على ذلك. علينا أن نختار عدد المجموعات بناء على عدد العناصر نتوقع للتعامل معها. عندما n هي تقريبا نفس حجم وب، ثم البحث هو تقريبا وقت ثابت، ولكننا لا يمكن أن نسميها O (1) لأنه يتم تعريف O من حيث الحد كما ن → ∞.

Answer 7

وO(1+n/k) حيث k هو عدد المجموعات.

إذا مجموعات تنفيذ k = n/alpha فمن O(1+alpha) = O(1) منذ alpha هو ثابت.

Answer 8

لقد أثبتنا أن الوصف القياسي لعمليات البحث في جدول التجزئة هو O(1) يشير إلى متوسط ​​الوقت المتوقع للحالة، وليس الأداء الصارم لأسوأ الحالات.بالنسبة لجدول التجزئة الذي يحل التصادمات مع التسلسل (مثل خريطة التجزئة الخاصة بـ Java) فإن هذا من الناحية الفنية هو O(1+α) مع وظيفة تجزئة جيدة, ، حيث α هو عامل تحميل الجدول.يظل ثابتًا طالما أن عدد الكائنات التي تقوم بتخزينها لا يزيد عن عامل ثابت أكبر من حجم الجدول.

لقد تم أيضًا توضيح أنه من الممكن بالمعنى الدقيق للكلمة إنشاء مدخلات تتطلب O(ن) عمليات البحث عن أي دالة تجزئة حتمية.ولكن من المثير للاهتمام أيضًا التفكير في أسوأ الحالات مُتوقع الوقت، وهو يختلف عن متوسط ​​وقت البحث.باستخدام التسلسل يكون O(1 + طول أطول سلسلة)، على سبيل المثال Θ(log ن / سجل السجل ن) عندما α=1.

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

Answer 9

ومن O (1) إلا إذا وظيفة التجزئة الخاصة بك جيدة جدا. تنفيذ جدول التجزئة جافا لا يحمي ضد ظائف تجزئة سيئة.

وإذا كنت بحاجة الى ان تنمو الجدول عند إضافة عناصر أو لا فلا أهمية لمسألة لأنه حان الوقت البحث.

Answer 10

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

location = (arraylength - 1) & keyhashcode

وهنا ويمثل أحادي المعامل AND المشغل.

وعلى سبيل المثال: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

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

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

في حالة جافا 8، يتم استبدال قائمة دلو مرتبط مع TreeMap إذا كان حجم ينمو إلى أكثر من 8، وهذا يقلل من كفاءة أسوأ بحث القضية إلى O (سجل ن).

Answer 11

وهذا ينطبق أساسا لمعظم تطبيقات جدول التجزئة في معظم لغات البرمجة، والخوارزمية نفسها لا تتغير حقا.

وإذا لم تكن هناك اصطدام الموجودة في الجدول، لديك فقط للقيام احد نظرة المتابعة، وبالتالي فإن إدارة الوقت هو O (1). إذا كان هناك اصطدام الحالية، ما عليك القيام به أكثر من نظرة المتابعة الذي يحرك باستمرار على أداء نحو O (ن).

Answer 12

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

Answer 13

والأكاديميين جانبا، من الناحية العملية، ينبغي قبول HashMaps وجود تأثير الأداء غير منطقي (ما لم يخبرك التعريف الخاص بك على خلاف ذلك).

Answer 14

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

Answer 15

وبطبيعة الحال أداء hashmap سيعتمد على أساس الجودة وظيفة شفرة التجزئة () لكائن معين. ومع ذلك، إذا تم تنفيذ وظيفة هذا أن احتمال اصطدام منخفضة جدا، وسوف يكون لها أداء جيد جدا (وهذا ليس حصرا (O 1) في كل حالة محتملة لكنه في <م > أكثر الحالات).

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