في هذه المقالة ، بدأنا في تحليل رمز المصدر لـ LinkedHashMap. يرث LinkedHashMap hashmap ، مما يعني أن LinkedHashMap تم تمديده بناءً على hashmap. لذلك ، قبل النظر إلى رمز المصدر لـ LinkedHashMap ، يحتاج القراء إلى فهم رمز المصدر لـ HashMap. يمكنك التحقق من مقالتي السابقة "Java Collection Series [3] ---- تحليل رمز المصدر HashMap". طالما أن لديك فهمًا عميقًا لمبدأ التنفيذ لـ HashMap ، ثم انظر إلى رموز المصدر لـ LinkedHashMap و Hashset و LinkedHashset كلها بسيطة للغاية. لذلك ، يجب أن يكون القراء صبورًا ودراسة رمز مصدر HASHMAP. هذا عمل جيد لشراء واحدة الحصول على ثلاثة مجاني. عند تحليل رمز مصدر HASHMAP في وقت سابق ، استخدمت التحليل الموجهة للمشكلات للرمز المصدري حتى لا أقوم بتحليله بشكل عشوائي مثل ذبابة بدون رأس ، ويمكن أن يكون للقراء أيضًا فهم أعمق للمشكلة. في هذه المقالة ، قررت استخدام هذه الطريقة لتحليل LinkedHashMap.
1. أي نوع من الهيكل يستخدم داخل LinkedHashMap؟
كما ترون ، نظرًا لأن LinkedHashMap يرث من HashMap ، فلا يزال هناك جدول تجزئة داخل LinkedHashMap ، لكن LinkeDhashMap أعاد كتابة إدخال وأضاف متغيرين عضويين إلى إدخال HashMap الأصلي ، وهما مرجع العقدة السابق ومرجع العقدة الخلف. وبهذه الطريقة ، يتم ربط جميع العقد معًا لتشكيل قائمة مرتبطة ثنائية الاتجاه. عند الحصول على العناصر ، فقط اجتياز القائمة المرتبطة ثنائية الاتجاه مباشرة. دعونا نرى كيف يبدو تطبيق LinkedHashMap للدخول.
إدخال الفئة الثابتة الخاصة <k ، v> يمتد hashmap.entry <k ، v> {// المرجع للعقدة السابقة للعقدة الحالية في إدخال القائمة المرتبطة ثنائية الاتجاه <k ، v> قبل ؛ // مرجع العقدة اللاحقة للعقدة الحالية في إدخال القائمة المرتبطة ثنائية الاتجاه <k ، v> بعد ؛ إدخال (int hash ، k key ، v value ، hashmap.entry <k ، v> next) {super (hash ، key ، value ، next) ؛ }. بعد. قبل = قبل ؛ } // أدخل العقدة الحالية في عقدة موجودة في قائمة ثنائية الاتجاه المرتبطة باطنية خاصة addbefore (الإدخال <k ، v> arugentingentry) {// مرجع العقدة التالية من النقاط العقدة الحالية إلى العقدة المحددة بعد = موجودة ؛ // يشير مرجع العقدة السابقة للعقدة الحالية إلى العقدة السابقة للعقدة المحددة قبل = forngentry.before ؛ // مرجع العقدة التالية للعقدة المحددة يشير إلى العقدة الحالية قبل. بعد ذلك = هذا ؛ // مرجع العقدة السابقة للعقدة المحددة يشير إلى العقدة الحالية بعد ذلك. } // تم فرزها بترتيب الوصول ، سجل في كل مرة يتم فيها الحصول على سجل الفراغ (hashmap <k ، v> m) {linkedHashMap <k ، v> lm = (linkedhashmap <k ، v>) m ؛ // إذا تم فرزه بترتيب الوصول إذا (lm.AccessOrder) {lm.modcount ++ ؛ // أخرج نفسك من القائمة المرتبطة ثنائية الاتجاه أولاً ؛ // ضع نفسك في ذيل القائمة المرتبطة ثنائية الاتجاه AddBefore (LM.Header) ؛ }} void recordRemoval (hashMap <k ، v> m) {remove () ؛ }}2. كيف ينفذ LinkedHashMap الفرز في أمر الإدراج؟
. // العملية التالية مريحة لتنفيذ ذاكرة التخزين المؤقت LRU. إذا كانت سعة ذاكرة التخزين المؤقت غير كافية ، فقم بإزالة إدخال العناصر الأقدم <K ، V> كبار السن = header.after ؛ if (removeEldestentry (endest)) {removeentryforkey (endest.key) ؛ }} // طريقة createentry method (int hash ، k ، vale ، int bucketIndex) {// أولاً احصل على hashmap من hashmap.entry <k ، v> old = table [bucketIndex] ؛ // لفه بإدخال LinkedHashMap الخاص <k ، v> e = إدخال جديد <> (التجزئة ، المفتاح ، القيمة ، القديم) ؛ الجدول [bucketIndex] = e ؛ // أدخل العقدة الحالية لذيل القائمة المرتبطة ثنائية الاتجاه e.addbefore (header) ؛ Size ++ ؛}يتغلب LinkedHashMap على أساليب الإضافات والخلق من فئة الأم HashMap. عندما ترغب في إدخال زوج من القيمة الرئيسية ، سيتم استدعاء طريقة وضع HashMap من الفئة الأم أولاً. في طريقة PUT ، سوف نتحقق مما إذا كان المفتاح المقابل موجودًا في جدول التجزئة. إذا كان موجودًا ، فما عليك سوى استبدال قيمتها مباشرة. إذا لم يكن موجودًا ، فاتصل بالطريقة الإضافية لإنشاء إدخال جديد. لاحظ أنه في هذا الوقت ، تسمى طريقة Addentry الخاصة بـ LinkedHashMap. نرى الكود أعلاه. بالإضافة إلى استدعاء طريقة AddEldestentry للفئة الأصل ، سيقوم هذا AddEldestentry أيضًا باستدعاء RemoveEldestentry لإزالة العنصر الأقدم. تتمثل هذه العملية بشكل أساسي في تنفيذ خوارزمية LRU ، والتي ستتم مناقشتها أدناه. نرى أن LinkedHashMap يعيد كتابة طريقة إنشاء. عندما تريد إنشاء إدخال جديد ، سيتم استدعاء هذه الطريقة. بعد كل مرة يتم وضع الإدخال في جدول التجزئة ، سيتم استدعاء طريقة AddBefore لإدراج العقدة الحالية في ذيل القائمة المرتبطة ثنائية الاتجاه. وبهذه الطريقة ، تسجل القائمة المرتبطة ثنائية الاتجاه ترتيب كل عقدة تم إدخالها. عند الحصول على العناصر ، فقط اجتياز القائمة المرتبطة ثنائية الاتجاه. يوضح الشكل التالي تشغيل كل مكالمة إلى AddBefore. نظرًا لأنها قائمة مرتبطة ثنائية الاتجاه ، قبل إدخال العقدة الحالية في عقدة الرأس ، فإنها تقوم بالفعل بإدخال العقدة الحالية في ذيل القائمة المرتبطة ثنائية الاتجاه.
3. كيفية استخدام LinkedHashMap لتنفيذ ذاكرة التخزين المؤقت LRU؟
نحن نعلم أن تنفيذ ذاكرة التخزين المؤقت يعتمد على ذاكرة الكمبيوتر ، وموارد الذاكرة محدودة للغاية ، ومن المستحيل تخزين العناصر دون حد. لذلك ، نحن بحاجة إلى حذف بعض العناصر بشكل مناسب عندما تكون السعة غير كافية. إذن أي عنصر من الأفضل حذفه؟ فكرة خوارزمية LRU هي أنه إذا تم الوصول إلى البيانات مؤخرًا ، فإن فرص الوصول إلى المستقبل أعلى أيضًا. لذلك يمكننا حذف البيانات التي لا يتم الوصول إليها في كثير من الأحيان. بعد ذلك ، دعونا نلقي نظرة على كيفية تنفيذ LinkedHashMap لآلية LRU.
الطبقة العامة LinkedHashMap <k ، v> يمتد HashMap <k ، v> تنفيذ خريطة <k ، v> {// extly listed list header private transient express <k ، v> ؛ // فرز خاص نهائي AccessOrder من أجل الوصول ؛ ... Public LinkedHashMap (int initialcapacity ، float loadfactor ، accessorder boolean) {super (initialCapacity ، loadFactor) ؛ this.AccessOrder = AccessOrder ؛ } // احصل على قيمة وفقًا للمفتاح العام v get (مفتاح الكائن) {// استدعاء طريقة الفئة الأصل للحصول على إدخال الإدخال المقابل <k ، v> e = (الإدخال <k ، v>) getentry (مفتاح) ؛ if (e == null) {return null ؛ } // إذا تم فرزه بترتيب الوصول ، فسيتم وضع العقدة بعد كل استخدام في نهاية القائمة المرتبطة ثنائية الاتجاه E.ReCordAccess (هذا) ؛ إرجاع E.Value ؛ } إدخال الفئة الثابتة الخاصة <k ، v> يمتد hashmap.entry <k ، v> {... // أدخل العقدة الحالية في مقدمة العقدة الموجودة في القائمة الثنائية المرتبطة بالفراغ الخاص addBefore (الإدخال <k ، v> nergententry) {// مرجع العقد التالي لنقاط العقل الحالية إلى العائل المعطى بعد الحالي ؛ // يشير مرجع العقدة السابقة للعقدة الحالية إلى العقدة السابقة للعقدة المحددة قبل = forngentry.before ؛ // مرجع العقدة التالية للعقدة المحددة يشير إلى العقدة الحالية قبل. بعد ذلك = هذا ؛ // مرجع العقدة السابقة للعقدة المحددة يشير إلى العقدة الحالية بعد ذلك. } // تم فرزها بترتيب الوصول ، سجل في كل مرة يتم فيها تشغيل التشغيل Void RecordAccess (HashMap <k ، v> m) {LinkedHashMap <k ، v> lm = (linkedhashmap <k ، v>) m ؛ // إذا تم فرزه بترتيب الوصول إذا (lm.AccessOrder) {lm.modcount ++ ؛ // أخرج نفسك من القائمة المرتبطة ثنائية الاتجاه أولاً ؛ // ضع نفسك في ذيل القائمة المرتبطة ثنائية الاتجاه AddBefore (LM.Header) ؛ }} ...} // سيتم استدعاء هذه الطريقة في الفئة الأصل method method addentry (int hash ، k key ، v value ، int bucketindex) {// حساب طريقة إضافة الفئة الأصل super.addentry (التجزئة ، المفتاح ، القيمة ، bucketIndex) ؛ // العملية التالية مريحة لتنفيذ ذاكرة التخزين المؤقت LRU. إذا كانت سعة ذاكرة التخزين المؤقت غير كافية ، فقم بإزالة إدخال العناصر الأقدم <K ، V> كبار السن = header.after ؛ if (removeEldestentry (endest)) {removeEldestForKey (endest.key) ؛ }} // أين تحذف أقدم عنصر؟ تم تصميم هذه الطريقة ليتم كتابتها فوقها بواسطة فئات فرعية محمية Boolean RemoveEldestentry (map.entry <k ، v> olderly) {return false ؛ }}لكي أكون أكثر سهولة ، حذفت بعض التعليمات البرمجية غير ذات الصلة في الكود المنشور أعلاه. يمكننا أن نرى أن LinkedHashMap لديه متغير عضو ، والذي يسجل ما إذا كان يحتاج إلى فرزه بترتيب الوصول. يوفر مُنشئًا يمكنه تحديد قيمة AccessOrder نفسها. في كل مرة تقوم فيها بالاتصال بالطريقة GET للحصول على العنصر ، يتم استدعاء E.ReCordAccess (هذا) ، والتي ستنقل العقدة الحالية إلى نهاية القائمة المرتبطة ثنائية الاتجاه. الآن نعلم أنه إذا كان AccessOrder صحيحًا ، في كل مرة نحصل فيها على العنصر ، سننقل هذا العنصر إلى نهاية قائمة الارتباطات ثنائية الاتجاه. الغرض من هذه الخطوة هو التمييز بين العناصر الأكثر استخدامًا عن تلك غير المستخدمة في كثير من الأحيان ، ويتم وضع العناصر المستخدمة في كثير من الأحيان في النهاية ويتم وضع العناصر الأقل استخدامًا في الرأس. دعنا نعود إلى الكود أعلاه ونرى أنه في كل مرة يتم فيها استدعاء طريقة الإضافات ، سنحدد ما إذا كان يجب حذف العنصر الأقدم. يتم تنفيذ منطق الحكم بواسطة RemoveEldestentry ، والذي تم تصميمه ليتم تجاوزه بواسطة الفئات الفرعية وإعادة كتابة المنطق في الداخل. لاحظ أنه منذ نقل العقد التي تمت زيارتها مؤخرًا إلى ذيل القائمة المرتبطة ثنائية الاتجاه ، يتم إخراج أقدم العقدة من رأس القائمة المرتبطة ثنائية الاتجاه للحذف. المثال التالي ينفذ ذاكرة التخزين المؤقت LRU بسيطة.
الطبقة العامة lrumap <k ، v> يمتد LinkedHashMap <k ، v> {private int cute ؛ lrumap (السعة int) {// استدعاء مُنشئ الفئة الأصل ، تم تعيينه على الفرز بترتيب الوصول الفائق (السعة ، 1f ، true) ؛ this.capacity = السعة ؛ } Override public boolean removeeldestentry (map.entry <k ، v> olderly) {// عندما يكون زوج القيمة المفتاح أكبر من أو يساوي سعة جدول التجزئة إلى هذا. size ()> = السعة ؛ } الفراغ الثابت العام (سلسلة [] args) {lrumap <integer ، string> map = new lrumap <integer ، string> (4) ؛ map.put (1 ، "a") ؛ map.put (2 ، "b") ؛ map.put (3 ، "C") ؛ System.out.println ("المجموعة الأصلية:" + خريطة) ؛ سلسلة s = map.get (2) ؛ System.out.println ("Get element:" + map) ؛ map.put (4 ، "D") ؛ System.out.println ("بعد الإدراج:" + خريطة) ؛ }}النتائج كما يلي:
ملاحظة: يعتمد جميع التحليلات المذكورة أعلاه على JDK1.7 ، وستكون هناك اختلافات بين الإصدارات المختلفة ، يحتاج القراء إلى الانتباه.
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.