معلمات تهيئة hashmap (التحميل / السعة الأولية)

Question

ما هي القيم التي يجب أن أمرها لإنشاء كفاءة HashMap / HashMap الهياكل القائمة على العناصر n؟

في ArrayList, ، العدد الفعال هو n (n يفترض بالفعل نمو المستقبل). ماذا يجب أن يكون المعلمات ل HashMap؟ ((int) (n * 0.75d) ، 0.75d)؟ أكثر؟ أقل؟ ما هو تأثير تغيير عامل الحمل؟

Answer 1

فيما يتعلق بعامل التحميل ، سأقتبس ببساطة من Hashmap Javadoc:

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

بمعنى ، لا ينبغي تغيير عامل التحميل من .75 ، ما لم يكن لديك بعض التحسين المحدد الذي ستفعله. السعة الأولية هي الشيء الوحيد الذي تريد تغييره ، وتعيينه وفقًا لـ الخاص بك N القيمة - المعنى (N / 0.75) + 1, أو شيء في هذا المجال. سيضمن ذلك أن يكون الجدول دائمًا كبيرًا بما يكفي ولن يحدث أي إعادة صياغة.

Answer 2

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

(int) Math.ceil(requiredCapacity / loadFactor);

لأن السعة الأولية تعطي ما تريده إما HashMap أو أ Hashtable. من خلال "ما تريد" أعني ذلك إضافة requiredCapacity لن تتسبب عناصر الخريطة في الصفيف الذي يلفه تغيير الحجم ولن يكون الصفيف أكبر من المطلوب. نظرًا لأن سعة التحميل الافتراضية هي 0.75 ، فإن تهيئة hashmap مثل So Works:

... = new HashMap<KeyType, ValueType>((int) Math.ceil(requiredCapacity / 0.75));

نظرًا لأن مجموعة التجزئة هي مجرد غلاف ل hashmap ، فإن نفس المنطق ينطبق أيضًا على هناك ، أي يمكنك إنشاء مجموعة من التجزئة بكفاءة مثل هذا:

.... = new HashSet<TypeToStore>((int) Math.ceil(requiredCapacity / 0.75));

إجابة yuval آدم صحيحة لجميع الحالات إلا في أي مكان (requiredCapacity / 0.75) هي قوة 2 ، وفي هذه الحالة يخصص الكثير من الذاكرة.
تستخدم إجابة @Notedible الكثير من الذاكرة في كثير من الحالات ، حيث أن مُنشئ HashMap نفسه يتعامل مع المشكلات التي يريد أن يكون لها مجموعة الخرائط حجمها 2.

Answer 3

في ال مكتبات الجوافة من Google ، هناك وظيفة تنشئ HashMap محسّنة لعدد متوقع من العناصر: NewhashMapWithExpectedSize

من المستندات:

يخلق مثيل Hashmap ، مع "السعة الأولية" عالية بما فيه الكفاية والتي يجب أن تحمل عناصر متوقعة دون نمو ...

Answer 4

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

HashMap<Foo> myMap = new HashMap<Foo>(numberOfElements * 2);

لا تتردد في الاختلاف ، في الواقع أود التحقق من هذه الفكرة أو التخلص منها.

Answer 5

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

  // Find a power of 2 >= initialCapacity
  int capacity = 1;
  while (capacity < initialCapacity)
  capacity <<= 1;

لذلك ، على الرغم من أن عامل التحميل البالغ 0.75F لا يزال هو نفسه بين علامة التجزئة و hashmap ، يجب عليك استخدام سعة أولية n*2 حيث N هو عدد العناصر التي تخطط لتخزينها في hashmap. هذا سيضمن أسرع سرعات الحصول على/وضع.

Answer 6

في قائمة ArrayList ، يكون الرقم الفعال N (N يفترض بالفعل نمو المستقبل).

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

إذا كنت تتحدث من ناحية أخرى ، فأنت تتحدث عن قيمتك لـ N مع الأخذ في الاعتبار النمو - ثم نعم ، إذا كان بإمكانك ضمان أن القيمة فلن تتجاوز هذا ، فإن استدعاء مُنشئ قائمة ArrayList مناسب. وفي هذه الحالة ، كما أشار هانك ، سيكون المُنشئ المماثل للخريطة هو N و 1.0F. يجب أن يؤدي هذا بشكل معقول حتى لو حدث أن تتجاوز N (على الرغم من أنك إذا كنت تتوقع أن يحدث هذا بشكل منتظم ، فقد ترغب في تمرير رقم أكبر للحجم الأولي).

عامل التحميل ، في حال لم تكن على دراية ، هو النقطة التي ستزداد فيها الخريطة ، كجزء من السعة الإجمالية.

يحرر: ربما يكون Yuval محقًا في أنه من الأفضل ترك عامل الحمل حوالي 0.75 لخريطة للأغراض العامة. من شأن عامل التحميل 1.0 أداءً رائعًا إذا كانت مفاتيحك تحتوي على علامات ترميز متسلسلة (مثل مفاتيح عدد صحيح متسلسل) ، ولكن لأي شيء آخر من المحتمل أن تصطدم بتصادمات مع دلاء التجزئة ، مما يعني أن عمليات البحث تستغرق وقتًا أطول لبعض العناصر. سيؤدي إنشاء دلاء أكثر مما هو ضروري للغاية إلى تقليل فرصة التصادم هذه ، مما يعني أن هناك فرصة أكبر لوجود العناصر في الدلاء الخاصة بها ، وبالتالي يمكن استردادها في أقصر وقت. كما تقول المستندات ، هذا هو الوقت مقابل مفاضلة الفضاء. إذا كان إما مهمين بشكل خاص لك (كما هو موضح من قبل Profiler بدلاً من التحسين قبل الأوان!) يمكنك التأكيد على ذلك ؛ خلاف ذلك ، التمسك مع الافتراضي.

Answer 7

الإشارة إلى رمز المصدر HashMap سوف يساعد.

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

Answer 8

إنه آمن في معظم حالات List و Map التهيئة لجعل List أو Map مع المعاملات الحجم التالية.

List<T>(numElements + (numElements / 2));
Map<T,T>(numElements + (numElements / 2));

هذا يتبع .75 القاعدة وكذلك ينقذ القليل من النفقات العامة على * 2 العملية الموضحة أعلاه.

Answer 9

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

collectionspy (collectionspy.com) هي شركة Java Profiler الجديدة التي تتيح لك رؤية في غمضة العين التي تقترب من Hashmaps من الحاجة إلى إعادة صياغة ، وعدد المرات التي تم إعادة صياغتها في الماضي ، وأكثر من ذلك. أداة مثالية لتحديد وسيطات السعة الأولية الآمنة لمقاعد الحاويات القائمة على القدرات.