هيكل التخزين
أولاً ، يتم تخزين HashMap على أساس جدول التجزئة. هناك صفيف بداخله. عندما يتم تخزين عنصر ما ، قم أولاً بحساب قيمة التجزئة الخاصة بمفتاحه وإيجاد المركز الفردي المقابل للعنصر في الصفيف بناءً على قيمة التجزئة. إذا لم يكن هناك عنصر في هذا الموضع ، فضع العنصر الحالي مباشرة. إذا كان هناك عنصر (يتم تذكره كـ A هنا) ، فقم بربط العنصر الحالي إلى مقدمة العنصر A ثم ضع العنصر الحالي في الصفيف. لذلك في HashMap ، يحفظ المصفوفة بالفعل العقدة الأولى من القائمة المرتبطة. فيما يلي صورة من موسوعة Baidu:
كما هو موضح في الشكل أعلاه ، يكون كل عنصر كائن إدخال ، حيث يتم حفظ مفتاح وقيمة العنصر ، وهناك مؤشر يمكن استخدامه للإشارة إلى الكائن التالي. جميع المفاتيح ذات قيمة التجزئة نفسها (أي ، الصراع) تربطها معًا باستخدام قائمة مرتبطة ، وهي طريقة السوستة.
المتغيرات الداخلية
// السعة الافتراضية الأولية ثابتة int int default_initial_capacity = 16 ؛ // الحد الأقصى للسعة الثابتة النهائية int maximum_capacity = 1 << 30 ؛ عامل تحميل من صفيف التجزئة النهائي loadFactor ؛
في المتغيرات المذكورة أعلاه ، تشير السعة إلى طول جدول التجزئة ، أي حجم الجدول ، والافتراضي هو 16.
عامل التحميل هو مقياس لكم يسمح لجدول التجزئة بالوصول إلى قبل زيادة قدرته تلقائيًا. عندما يتجاوز عدد الإدخالات في جدول التجزئة منتج عامل التحميل والقدرة الحالية ، يتم إعادة صياغة جدول التجزئة (أي ، يتم إعادة بناء هياكل البيانات الداخلية) بحيث يكون لجدول التجزئة حوالي ضعف عدد الدلاء.
المعنى العام هو: عامل التحميل هو مقياس مدى امتلاء جدول التجزئة قبل التوسع. عندما يتجاوز عدد "أزواج القيمة الرئيسية" في جدول التجزئة ناتج السعة الحالية وعامل التحميل ، وتجزئة الجدول التجزئة (أي ، يتم إعادة بناء بنية البيانات الداخلية) ، ويصبح سعة جدول التجزئة حوالي ضعف الأصل.
كما يتضح من التعريف المتغير أعلاه ، فإن عامل التحميل الافتراضي Default_Load_Factor هو 0.75. كلما زادت هذه القيمة ، زاد معدل استخدام المساحة ، لكن سرعة الاستعلام (بما في ذلك GET و PUT) سوف تبطئ. بعد فهم عامل التحميل ، يمكن أن يفهم ذلك العتبة أيضًا. إنه في الواقع يساوي عامل التحميل*.
مُنشئ
HASHMAP العام (int initialcapacity ، float loadFactor) {if (initialCapacity <0) رمي غير alfictalargumentException ("السعة الأولية غير القانونية:" + initialCapacity) ؛ إذا (initialCapacity> maximum_capacity) initialCapacity = maximum_capacity ؛ if (loadFactor <= 0 || float.isnan (loadFactor)) رمي غير alficalaRgumentException جديد ("عامل التحميل غير القانوني:" + loadFactor) ؛ // ابحث عن قوة 2> = السعة initalcapacity int = 1 ؛ بينما (السعة <initialcapacity) // احسب أصغر قوة من 2 التي تكون أكبر من سعة السعة المحددة << = 1 ؛ this.loadFactor = loadFactor ؛ عتبة = (int) math.min (السعة * loadFactor ، maximum_capacity + 1) ؛ جدول = إدخال جديد [السعة] ؛ // تخصيص مساحة لجدول التجزئة usealthing = sun.misc.vm.iSbooted () && (السعة> = holder.alternative_hashing_threshold) ؛ init () ؛}هناك العديد من المنشئين ، وسوف يطلقون على ما سبق في النهاية. يقبل معلمتين ، إحداها هي السعة الأولية والآخر هو عامل التحميل. في البداية ، نحدد أولاً ما إذا كانت مجموعة القيمة قانونية ، وإذا كان هناك أي مشكلة ، فسيتم طرح استثناء. المهم هو حساب السعة أدناه ، فإن منطقه هو حساب أصغر طاقة من 2 أكبر من السعة الأولية. في الواقع ، الغرض من ذلك هو جعل القدرة أكثر من أو تساوي السعة الأولية المحددة ، ولكن يجب أن تكون هذه القيمة مضاعفًا أسيًا 2 ، وهي مشكلة رئيسية. والسبب في ذلك هو بشكل أساسي لتعيين قيم التجزئة. دعونا نلقي نظرة أولاً على طريقة التجزئة في HashMap:
HING int hash (Object k) {int h = 0 ؛ if (UsealthAshing) {if (k eastyof string) {return sun.misc.hashing.stringhash32 ((string) k) ؛ } h = hassheed ؛ } h ^= k.hashCode () ؛ // تضمن هذه الوظيفة أن الترميزات التي تختلف فقط عن طريق // مضاعفات ثابتة في كل موضع بت لها عدد من الاصطدامات // (حوالي 8 في عامل التحميل الافتراضي). H ^ = (H >>> 20) ^ (H >>> 12) ؛ إرجاع H ^ (H >>> 7) ^ (H >>> 4) ؛} int index for (int h ، int) {return h & (length-1) ؛}تقوم طريقة التجزئة () بإعادة حساب قيمة التجزئة للمفتاح وتستخدم عمليات بت معقدة نسبيًا. لا أعرف المنطق المحدد. على أي حال ، إنها بالتأكيد طريقة أفضل ، والتي يمكن أن تقلل من النزاعات أو شيء من هذا القبيل.
indexfor () أدناه هو تراكم العنصر في جدول التجزئة استنادًا إلى قيمة التجزئة. بشكل عام ، في جدول التجزئة ، يمكنك استخدام قيم التجزئة لتعديل طول الجدول. عندما يكون الطول (أي السعة) قوة 2 ، H & (Length-1) هو نفس التأثير. علاوة على ذلك ، يجب أن تكون قوة 2 رقمًا متساويًا ، ثم بعد طرح 1 ، هو رقم غريب ، ويجب أن يكون الجزء الأخير من الثنائي 1. ثم قد يكون الجزء الأخير من H & (الطول 1) 1 أو 0 ، والذي يمكن تجسيده بالتساوي. إذا كان الطول رقمًا غريبًا ، فإن الطول 1 هو رقم زوجي وآخر شيء هو 0. في هذا الوقت ، قد يكون الجزء الأخير من H & (Length-1) هو 0 فقط ، وجميع المشتركين الناتج حتى ، لذلك يتم إهدار نصف المساحة. لذلك ، يجب أن تكون السعة في hashmap قوة 2. يمكنك أن ترى أن الافتراض الافتراضي default_initial_capacity = 16 و Maximum_Capacity = 1 << 30 هما هما هما هذا.
كائن الدخول
يتم تغليف أزواج القيمة الرئيسية في hashmap في كائنات دخول ، وهي فئة داخلية في hashmap. دعونا نلقي نظرة على تنفيذها:
إدخال الفئة الثابت <K ، V> ينفذ map.entry <k ، v> {Final K Key ؛ V قيمة ؛ الدخول <K ، V> التالي ؛ التجزئة إدخال (int h ، k k ، v v ، entry <k ، v> n) {value = v ؛ التالي = ن ؛ المفتاح = k ؛ التجزئة = ح ؛ } النهائي العام K getKey () {return Key ؛ } public final v getValue () {return value ؛ } public final v setValue (v newValue) {v oldvalue = value ؛ القيمة = newValue ؛ إرجاع Oldvalue ؛ } Public Final Boolean يساوي (كائن O) {if (! (o مثيل من map.entry)) إرجاع false ؛ map.entry e = (map.entry) o ؛ الكائن k1 = getKey () ؛ كائن k2 = e.getKey () ؛ if (k1 == k2 || (k1! = null && k1.equals (k2))) {object v1 = getValue () ؛ كائن v2 = e.getValue () ؛ if (v1 == v2 || (v1! = null && v1.equals (v2))) return true ؛ } إرجاع خطأ ؛ } public final int hashcode () {return (key == null؟ 0: key.hashCode ()) ^ (value == null؟ 0: value.hashCode ()) ؛ } السلسلة النهائية العامة tostring () {return getKey () + "=" + getValue () ؛ } void recordAccess (hashmap <k ، v> m) {}}تنفيذ هذه الفئة بسيط وسهل الفهم. يتم توفير طرق مثل getKey () ، getValue () للاتصال. لتحديد المساواة ، من الضروري أن يكون كل من المفتاح والقيمة متساوية.
وضع العملية
ضع أولاً قبل أن تحصل عليه ، لذا انظر إلى طريقة PUT () أولاً:
public v put (k key ، v value) {if (key == null) return putfornullkey (value) ؛ int hash = hash (مفتاح) ؛ int i = indexfor (hash ، table.length) ؛ لـ (الإدخال <k ، v> e = table [i] ؛ e! = null ؛ e = e.next) {object k ؛ if ( e.value = القيمة ؛ eRecordAccess (هذا) ؛ إرجاع Oldvalue ؛ }} modcount ++ ؛ addentry (التجزئة ، المفتاح ، القيمة ، i) ؛ إرجاع فارغ ؛}في هذه الطريقة ، حدد أولاً ما إذا كان المفتاح فارغًا. إذا كانت الإجابة بنعم ، فاستدعاء طريقة Putfornullkey () ، مما يعني أن HashMap يسمح للمفتاح بأن يكون فارغًا (في الواقع ، يمكن أن تكون القيمة). إذا لم يكن فارغًا ، فاحسب قيمة التجزئة واحصل على المُخبر في الجدول. ثم انتقل إلى القائمة المرتبطة المقابلة للاستعلام عما إذا كان المفتاح نفسه موجودًا بالفعل. إذا كانت موجودة بالفعل ، فسيتم تحديث القيمة مباشرة. خلاف ذلك ، استدعاء طريقة Addentry () للإدراج.
ألقِ نظرة على طريقة putfornullkey ():
private v putfornullkey (v value) {for (intern <k ، v> e = table [0] ؛ e! = null ؛ e = e.next) {if ( e.value = القيمة ؛ eRecordAccess (هذا) ؛ إرجاع Oldvalue ؛ }} modcount ++ ؛ addentry (0 ، null ، value ، 0) ؛ إرجاع فارغ ؛}يمكن ملاحظة أنه عندما يكون المفتاح فارغًا ، سيتم تحديث القيمة إذا كانت موجودة ، وإلا سيتم استدعاء Addentry () لإدراجها.
فيما يلي تنفيذ طريقة الإضافة ():
addentry void (int hash ، k key ، v value ، int bucketIndex) {if ((size> = threshold) && (null! = table [bucketIndex])) {تغيير حجم (2 * table.length) ؛ hash = (null! = مفتاح)؟ التجزئة (مفتاح): 0 ؛ bucketIndex = indexfor (hash ، table.length) ؛ } CreateEntry (hash ، key ، value ، bucketIndex) ؛} void createentry (int hash ، k key ، v value ، int bucketIndex) {intern <k ، v> e = table [bucketIndex] ؛ الجدول [bucketIndex] = إدخال جديد <> (التجزئة ، المفتاح ، القيمة ، E) ؛ Size ++ ؛}أولاً ، حدد ما إذا كنت تريد توسيع السعة (ستوسيع سعة إعادة حساب القيمة التراكمية ونسخ العنصر) ، ثم احسب ترجمة الصفيف ، وأخيراً أدخل العنصر باستخدام طريقة إدخال الرأس في Createentry ().
الحصول على العملية
public v get (مفتاح الكائن) {if (key == null) return getFornullKey () ؛ الإدخال <k ، v> entry = getentry (مفتاح) ؛ إرجاع فارغ == الدخول؟ NULL: ENTROM.GETVALUE () ؛} private v getFornullKey () {for (intern <k ، v> e = table [0] ؛ e! = null ؛ e = e.next) {if ( } الإرجاع null ؛} الإدخال النهائي <k ، v> getentry (مفتاح الكائن) {int hash = (key == null)؟ 0: التجزئة (المفتاح) ؛ لـ (الإدخال <k ، v> e = table [indexfor (hash ، table.length)] ؛ e! = null ؛ e = e.next) {object k ؛ if ( } إرجاع فارغ ؛}هذا أبسط من PUT (). تحتاج أيضًا إلى تحديد ما إذا كان المفتاح فارغًا ، ثم الاستعلام عبر القائمة المرتبطة.
تحسين الأداء
Hashmap هي بنية بيانات فعالة وعالمية يمكن رؤيتها في كل مكان في كل برنامج Java. دعونا نقدم بعض المعرفة الأساسية أولاً. كما تعلم أيضًا ، يستخدم HashMap طرق HashCode () و equals () من مفتاح تقسيم القيم إلى دلاء مختلفة. عادة ما يكون عدد الدلاء أكبر قليلاً من عدد السجلات في الخريطة ، بحيث يتضمن كل دلو قيم أقل (يفضل أن يكون واحدًا واحدًا. عند البحث من خلال المفاتيح ، يمكننا تحديد موقع دلو (باستخدام Hashcode () بسرعة إلى Modulo لعدد الدلاء) والكائن الذي نبحث عنه في وقت ثابت.
يجب أن تعرف بالفعل كل هذه الأشياء. قد تعرف أيضًا أن تصادمات التجزئة يمكن أن يكون لها تأثير كارثي على أداء HashMap. إذا سقطت قيم HashCode () متعددة في نفس الدلو ، يتم تخزين هذه القيم في قائمة مرتبطة. في أسوأ الحالات ، يتم تعيين جميع المفاتيح في نفس الدلو ، وبالتالي فإن HashMap تنحرف إلى قائمة مرتبطة - وقت البحث من o (1) إلى o (n). دعنا أولاً نختبر أداء Hashmap في Java 7 و Java 8 في ظل الظروف العادية. من أجل التحكم في سلوك HashCode () ، نحدد فئة رئيسية على النحو التالي:
مفتاح الفئة ينفذ قابلة للمقارنة <kear> {private final int value ؛ key (int value) {this.value = value ؛}@overridepublic int compareto (key o) {return integer.compare (this.value ، o.value) ؛} outclaspublic equals (object o) {if (هذا = O.GetClass ()) إرجاع خطأ ؛ مفتاح المفتاح = (المفتاح) o ؛ قيمة الإرجاع == key.value ؛}@outridepublic int hashcode () {return value ؛}}إن تنفيذ الفئة الرئيسية هو قياسي إلى حد ما: إنه يعيد كتابة طريقة متساوية () ويوفر طريقة هاشد () لائقة إلى حد ما. لتجنب الإفراط في GC ، قمت بتخطيط كائن المفتاح الثابت بدلاً من البدء في إنشائه مرة أخرى في كل مرة:
مفتاح الفئة ينفذ مفتاح قابلة للمقارنة <kear> {مفاتيح الفئة العامة {public static final int max_key = 10_000_000 ؛ مفتاح نهائي ثابت خاص [] keys_cache = مفتاح جديد [max_key] ؛ static {for (int i = 0 ؛ i <max_key ؛ ++ i) {keys_cache [i] = new key ( keys_cache [value] ؛}الآن يمكننا البدء في الاختبار. يستخدم معيارنا قيمًا رئيسية مستمرة لإنشاء HashMaps بأحجام مختلفة (مضاعف لمدة 10 ، من 1 إلى 1 مليون). في الاختبار ، سنستخدم أيضًا مفاتيح للبحث وقياس الوقت الذي يستغرقه HashMaps بأحجام مختلفة:
استيراد com.google.caliper.param ؛ import com.google.caliper.runner ؛ import com.google.caliper.simpleBenchmark ؛ public class mapbenchmark يمتد SimpleBenchmark {private hashmap <key ، integer> map ؛ parampriprivate int mapsize ؛ overdeprotected setup () HashMap <> (خرائط) ؛ لـ (int i = 0 ؛ i <mapsize ؛ ++ i) {map.put (keys.of (i) ، i) ؛}} public void timemapget (int reps)ومن المثير للاهتمام ، في هذا hashmap.get () البسيط () ، Java 8 أسرع بنسبة 20 ٪ من Java 7. الأداء الكلي جيدًا أيضًا: على الرغم من وجود مليون سجل في HashMap ، فإن استعلامًا واحدًا لم يستغرق سوى أقل من 10 نانو ثانية ، وهو حوالي 20 دورة في وحدة المعالجة المركزية على الجهازي. مروع جدا! لكن هذا ليس ما نريد قياسه.
لنفترض أن هناك مفتاحًا سيئًا ، فهو يعيد دائمًا نفس القيمة. هذا هو أسوأ سيناريو ، ويجب ألا تستخدم HashMap على الإطلاق:
مفتاح الفئة ينفذ قابلة للمقارنة <kear> {//....overridepublic int hashcode () {return 0 ؛}}من المتوقع نتائج Java 7. مع نمو حجم hashmap ، تزداد حجم طريقة GET () أكبر وأكبر. نظرًا لأن جميع السجلات موجودة في القائمة المرتبطة الطويلة في نفس الدلو ، فإن البحث في متوسط سجل واحد يتطلب اجتياز نصف القائمة. لذلك ، يمكن أن نرى من الشكل أن تعقيد الوقت هو o (n).
ومع ذلك ، جافا 8 يؤدي أفضل بكثير! إنه منحنى سجل ، لذلك فإن أدائه هو أوامر الحجم بشكل أفضل. على الرغم من أسوأ سيناريو تصادمات التجزئة الشديدة ، فإن هذا المعيار نفسه له تعقيد زمني في JDK8 من O (logn). إذا نظرت إلى منحنى JDK 8 وحده ، فسيكون ذلك أكثر وضوحًا. هذا توزيع خطي لوغاريتمي:
لماذا يوجد مثل هذا التحسن الرائع في الأداء ، على الرغم من أن رمز O الكبير يستخدم هنا (يصف Big O الحد الأعلى المقارب)؟ في الواقع ، تم ذكر هذا التحسين في JEP-180. إذا كان السجل الموجود في دلو كبيرًا جدًا (حاليًا Treeify_Threshold = 8) ، فسيقوم HashMap باستبداله بشكل ديناميكي بتنفيذ Treemap خاص. سيؤدي ذلك إلى نتائج أفضل ، O (logn) ، وليس سيئًا O (n). كيف تعمل؟ يتم ببساطة إلحاق السجلات المقابلة للمفتاح الذي يحتوي على تعارضات في المقدمة بقائمة مرتبطة ، ويمكن العثور على هذه السجلات فقط من خلال اجتياز. ومع ذلك ، بعد تجاوز هذه العتبة ، يبدأ HashMap في ترقية القائمة إلى شجرة ثنائية ، باستخدام قيمة التجزئة كمتغير فرع للشجرة. إذا لم تكن قيمتي التجزئة متساوية ولكن الإشارة إلى نفس الدلو ، فسيتم إدراج القيم الأكبر في الشجرة الفرعية اليمنى. إذا كانت قيم التجزئة متساوية ، فإن HashMap تأمل أن يتم تنفيذ القيمة الرئيسية بشكل أفضل بواسطة الواجهة المماثلة بحيث يمكن إدراجها بالترتيب. هذا ليس ضروريًا لمفتاح HashMap ، ولكنه بالطبع هو الأفضل إذا تم تنفيذه. إذا لم يتم تنفيذ هذه الواجهة ، فلن تتوقع تحقيق تحسينات في الأداء في حالة تصادمات التجزئة الشديدة.
ما هو استخدام هذا التحسين الأداء؟ على سبيل المثال ، برنامج ضار ، إذا كان يعلم أننا نستخدم خوارزمية التجزئة ، فقد يرسل عددًا كبيرًا من الطلبات ، مما يؤدي إلى تصادمات تجزئة خطيرة. ثم يمكن أن يؤثر الوصول باستمرار على هذه المفاتيح بشكل كبير على أداء الخادم ، مما يؤدي إلى رفض هجوم الخدمة (DOS). يمكن للقفزة من O (n) إلى O (logn) في JDK 8 أن تمنع بشكل فعال هجمات مماثلة ، مع تعزيز القدرة على التنبؤ بأداء hashmap بشكل طفيف. آمل أن يقنع هذا التحسن في نهاية المطاف رئيسك في الموافقة على الترقية إلى JDK 8.
البيئة المستخدمة للاختبار هي: Intel Core I7-3635QM @ 2.4 GHz ، ذاكرة 8 جيجا بايت ، قرص SSD الثابت ، باستخدام معلمات JVM الافتراضية ، تعمل على نظام Windows 8.1 64 بت.
لخص
تم تحليل التنفيذ الأساسي لـ HashMap كما هو موضح أعلاه ، وأخيراً تم إجراء الملخص: