غالبًا ما واجهت مثل هذه الأسئلة خلال المقابلات في الماضي. للأسف ، أشعر بالخجل ، الأساس فقير للغاية ، لا توجد طريقة ، أشعر بالظلم
الآن علينا أن نتحدث عن الاختلافات والاتصالات بين هؤلاء الثلاثة: هذه الثلاثة تنفيذ واجهة القائمة ، وكلها لها طرق محددة في واجهة القائمة ، وكذلك لديها طرق لواجهة التجميع ؛
ArrayList: تستخدم طريقة الصفيف لتخزين البيانات والاستعلام والتعديل بسرعة ، لكن سرعة الإضافة والحذف بطيئة ؛
LinkedList: يستخدم طريقة القائمة المرتبطة لتخزين البيانات ، وسرعة الاستعلام والتعديل بطيئة ، ولكن سرعة الإضافة والحذف سريعة.
المتجهات: يستخدم أيضًا المصفوفات للتخزين. التكرار ، التعدادات ، الحصول على (int index) ، و indexof (int index) ، لكن ArrayList ليس لديها تعدادات
ArrayList و Vector استخدام المصفوفات لتخزين البيانات. يتم إدخال بيانات الفهرس بسرعة. أو اجتياز متخلف ، ولكن هذا العنصر مطلوب فقط عند إدخال البيانات الأمامية والخلفية ، لذا فإن إدخال عدة درجات أسرع!
الجداول الخطية ، والقوائم المرتبطة ، وجداول التجزئة هي هياكل بيانات شائعة الاستخدام. هذه الفئات كلها في حزمة java.util. تحاول هذه المقالة أن تشرح للقراء دور كل فصل وكيفية استخدامها بشكل صحيح من خلال وصف بسيط.
مجموعة ├list │ ├linkedlist │ ├arraylist │ └vector │ └stack └setmap ├hashtable ├hashmap └weakhashmap
واجهة جمع
المجموعة هي واجهة التجميع الأساسية. تسمح بعض المجموعات بنفس العناصر بينما لا تفعل ذلك. يمكن للبعض الفرز ولكن البعض الآخر لا يستطيع ذلك. لا توفر Java SDK فصولًا مملوءة مباشرة من المجموعة.
يجب أن توفر جميع الفئات التي تنفذ واجهة التجميع مُنشئين قياسيين: يتم استخدام مُنشئ المعلمة لإنشاء مجموعة فارغة ، ويتم استخدام مُنشئ معلمة مجموعة لإنشاء مجموعة جديدة ، هذه المجموعة الجديدة. نفس العنصر. يسمح المنشئ الأخير للمستخدم بنسخ مجموعة.
كيف تكرر من خلال كل عنصر في مجموعة؟ بغض النظر عن النوع الفعلي للمجموعة ، فإنه يدعم طريقة Iterator () ، التي تُرجع جهاز التكرار ، ويستخدم هذا التكرار للوصول إلى كل عنصر في المجموعة واحدة تلو الأخرى. الاستخدامات النموذجية هي كما يلي:
iterator it = collection.iterator () ؛
الواجهتان المستمدون من واجهة التجميع هي قائمة ومجموعة.
قائمة الواجهة
القائمة هي مجموعة مرتبة ، ويسمح لك استخدام هذه الواجهة بالتحكم بدقة في موضع كل عنصر إدراج. يمكن للمستخدمين استخدام الفهارس (موضع العناصر في القائمة ، على غرار مشتركات الصفيف) للوصول إلى العناصر في القائمة ، والتي تشبه صفائف Java.
على عكس المجموعة المذكورة أدناه ، تتيح القائمة نفس العناصر.
بالإضافة إلى طريقة ITerator () التي تحتوي على واجهة التجميع اللازمة ، توفر القائمة أيضًا طريقة ListIrator () ، والتي تُرجع واجهة ListiTerator. حذف ، تعيين العناصر ، ويمكن أيضا اجتياز إلى الأمام أو للخلف.
تتضمن الفئات الشائعة التي تنفذ واجهات قائمة LinkedList و ArrayList و Vector و Stack.
LinkedList Class
ينفذ LinkedList واجهة القائمة ، مما يسمح عناصر فارغة. بالإضافة إلى ذلك ، يوفر LinkedList GET ، إزالة ، إدراج طرق في رأس أو ذيل LinkedList. تتيح هذه العمليات استخدام LinkedList لاستخدامها كمكدس أو قائمة انتظار أو قائمة انتظار ثنائية الاتجاه.
لاحظ أن LinkedList ليس لديه طريقة متزامنة. إذا تصلت سلاسل الرسائل المتعددة إلى قائمة في نفس الوقت ، فيجب عليك تنفيذ تزامن الوصول بنفسك. أحد الحلول هو بناء قائمة متزامنة عند إنشائها:
قائمة قائمة = collections.synchronizedList (New LinkedList (...)) ؛
فئة ArrayList
ArrayList ينفذ صفائف متغيرة الحجم. يسمح لجميع العناصر ، بما في ذلك فارغة. لا يتم مزامنة ArrayList.
وقت التشغيل من الحجم ، isempty ، الحصول على الأساليب المحددة ثابتة. ومع ذلك ، فإن النفقات العامة لطريقة الإضافة ثابتة ، ويستغرق وقتًا طويلاً لإضافة عناصر N. الأساليب الأخرى لها وقت التشغيل الخطي.
كل مثيل ArrayList له سعة ، وهو حجم الصفيف المستخدم لتخزين العناصر. يمكن أن تزيد هذه السعة تلقائيًا مع إضافة عناصر جديدة باستمرار ، ولكن لم يتم تعريف خوارزمية النمو. عندما يلزم إدراج عدد كبير من العناصر ، يمكن استدعاء طريقة التأمين قبل الإدخال لزيادة قدرة قائمة ArrayList على تحسين كفاءة الإدراج.
مثل LinkedList ، ArrayList هو أيضا غير متزامن.
فئة المتجهات
المتجه يشبه إلى حد كبير ArrayList ، ولكن المتجه متزامن. إن ITerator التي تم إنشاؤها بواسطة Vector ، على الرغم من أن Iterator التي تم إنشاؤها بواسطة ArrayList ، هي نفس الواجهة التي تم إنشاؤها بواسطة ArrayList ، نظرًا لأن المتجه متزامن ، عند إنشاء أحد التكرار ويتم استخدامه ، يغير مؤشر ترابط آخر حالة المتجه (على سبيل المثال ، إضافة أو إزالة بعضها) في هذا الوقت ، سيتم إلقاء ConversedifificationException عند استدعاء طريقة التكرار ، لذلك يجب اكتشاف الاستثناء.
فئة المكدس
يرث Stack من Vector ، وتنفيذ مكدس آخر في الخارج. يوفر المكدس 5 طرق إضافية لتمكين المتجه لاستخدامه كمكدس. تحصل أساليب الدفع والبوب الأساسية ، وطريقة نظرة خاطفة على العناصر في الجزء العلوي من المكدس ، وتختبر الطريقة الفارغة ما إذا كانت المكدس فارغًا ، وتكتشف طريقة البحث موضع عنصر في المكدس. المكدس تم إنشاؤه للتو وهو مكدس فارغ.
تعيين واجهة
SET عبارة عن مجموعة لا تحتوي على عناصر مكررة ، أي أن هناك عنصرين e1 و e2 لهما e1.equals (e2) = false ، والمجموعة لديها على الأكثر عنصر فارغ واحد.
من الواضح أن مُنشئ المجموعة له قيد ، ولا يمكن أن تحتوي معلمة التجميع التي تم تمريرها على عناصر مكررة.
يرجى ملاحظة: يجب تشغيل الكائنات القابلة للتغيير بعناية. إذا قام عنصر قابل للتغيير في مجموعة بتغيير حالته الخاصة ، مما يسبب كائن.
واجهة الخريطة
يرجى ملاحظة أن الخريطة لا ترث واجهة التجميع ، وتوفر الخريطة رسم خرائط من مفتاح إلى قيم. لا يمكن أن تحتوي الخريطة على نفس المفتاح ، ويمكن لكل مفتاح فقط تعيين قيمة واحدة. توفر واجهة الخريطة ثلاثة أنواع من المشاهدات للمجموعة.
فئة الهاشت
يرث علامة التجزئة واجهة الخريطة وينفذ جدول التجزئة مع رسم خرائط القيمة الرئيسية. يمكن استخدام أي كائن غير فائق كمفتاح أو قيمة.
استخدم (المفتاح ، القيمة) لإضافة بيانات ، استخدم (مفتاح) لاسترداد البيانات.
يقوم علامة التجزئة بضبط الأداء من خلال معلمات السعة الأولية ومعلمات عامل التحميل. عادة ، يمكن لعامل التحميل الافتراضي 0.75 تحقيق توازن الوقت والمساحة بشكل أفضل. يمكن أن توفر زيادة عامل التحميل المساحة ولكن سيزداد وقت البحث المقابل ، مما سيؤثر على عمليات مثل Get and Put.
مثال بسيط على استخدام علامة التجزئة على النحو التالي: وضع 1 و 2 و 3 في علامة تجزئة ، ومفاتيحهم هي "واحدة" ، "اثنان" ، "ثلاثة" على التوالي:
أرقام hashtable = new hashtable () ؛
الأرقام.
الأرقام.
الأرقام.
لإخراج رقم ، مثل 2 ، استخدم المفتاح المقابل:
عدد صحيح n = (عدد صحيح) number.get ("اثنين") ؛
System.out.println ("two =" + n) ؛
نظرًا لأن كائن كمفتاح سيحدد موضع القيمة المقابلة عن طريق حساب وظيفة التجزئة الخاصة به ، يجب على أي كائن كمفتاح تنفيذ الأساليب ومتساوي. ترث الأساليب hashcode و equals من كائن فئة الجذر. ) = يجب أن يكون الرمز الهزلي الخاص بهم هو نفسه ، ولكن إذا كان الكائنات مختلفة ، فقد لا تكون الرموز المتجددة فيهما مختلفة. من تشغيل جداول التجزئة للزيادة.
إذا كان الكائن نفسه يحتوي على ترميزات مختلفة ، فإن العملية على جدول التجزئة سيكون لها نتائج غير متوقعة (طريقة الحصول على طريقة متوقعة خالية). في نفس الوقت.
تتم مزامنة الهاشتو.
فئة هاشماب
HashMap يشبه علامة التصنيف ، والفرق هو أن hashmap غير متزامن ويسمح فارغة ، أي القيمة الفارغة والمفتاح الفارغ. ، ولكن عندما يتم اعتبار HashMap عبارة عن مجموعة (طريقة القيم () يمكن أن تُرجع مجموعة) ، فإن وقت التكراري التكراري النفقات العامة يتناسب مع قدرة hashmap. لذلك ، إذا كان أداء عمليات التكرار أمرًا مهمًا للغاية ، فلا تضع سعة التهيئة لـ HashMap ليكون مرتفعًا جدًا أو أن عامل التحميل منخفض للغاية.
الفئة الضعيفة
DeferHashMap هو hashmap المحسّن الذي ينفذ "مرجعًا ضعيفًا" للمفتاح.
لخص
إذا كانت قائمة الانتظار والعمليات الأخرى متورطة ، فيجب عليك التفكير في القائمة.
إذا كان البرنامج في بيئة واحدة ، أو الوصول إلى موضوع واحد فقط ، مع الأخذ في الاعتبار فئات غير متزامنة ، فهو أكثر كفاءة.
إيلاء اهتمام خاص لتشغيل جداول التجزئة.
حاول إرجاع الواجهة بدلاً من النوع الفعلي ، مثل إرجاع القائمة بدلاً من قائمة ArrayList. هذا للبرمجة التجريدية.
التزامن
المتجه متزامن. بعض الطرق في هذه الفئة تضمن أن الكائنات في المتجه آمنة مؤشرات الترابط. ArrayList غير متزامن ، وبالتالي فإن الكائنات في ArrayList ليست آمنة مؤشر ترابط. نظرًا لأن متطلبات المزامنة ستؤثر على كفاءة التنفيذ ، فإن استخدام ArrayList هو خيار جيد إذا لم تكن بحاجة إلى مجموعات آمنة من مؤشرات الترابط ، والتي يمكن أن تتجنب النفقات العامة للأداء غير الضرورية بسبب التزامن.
نمو البيانات
من آلية التنفيذ الداخلية ، يستخدم كل من ArrayList و Vector المصفوفات (Array) للتحكم في الكائنات في المجموعة. عند إضافة عناصر إلى هذين النوعين ، إذا كان عدد العناصر يتجاوز الطول الحالي للمصفوفة الداخلية ، فإنها تحتاج إلى توسيع طول المصفوفة الداخلية أصلي 50 ٪ من ذلك ، وبالتالي فإن آخر مرة تحصل فيها على هذه المجموعة ستستغرق دائمًا مساحة أكبر مما تحتاجه بالفعل. لذلك إذا كنت ترغب في حفظ الكثير من البيانات في مجموعة ، فهناك بعض المزايا لاستخدام المتجه ، لأنه يمكنك تجنب النفقات العامة غير الضرورية للموارد عن طريق تحديد حجم التهيئة للمجموعة.
وضع الاستخدام
في ArrayList و Vector ، يستغرق الأمر نفس الوقت للعثور على بيانات من موقع محدد (عبر الفهرس) أو لإضافة عنصر في نهاية المجموعة. ومع ذلك ، إذا تمت إضافة العناصر أو إزالتها إلى مكان آخر في المجموعة ، فسوف ينمو الوقت الذي يقضيه خطيًا: O (Ni) ، حيث يمثل N عدد العناصر الموجودة في المجموعة ، وأمثل موضع الفهرس حيث تزيد العناصر أو إزالة العناصر. لماذا هذا يحدث؟ يُعتقد أنه عند إجراء العمليات المذكورة أعلاه ، يجب أن تقوم جميع العناصر بعد العناصر I-Th و I-Th في المجموعة بإجراء عمليات إزاحة. ماذا يعني كل هذا؟
هذا يعني أنك تبحث فقط عن عناصر في موضع معين أو مجرد إضافة وإزالة العناصر في نهاية المجموعة ، ثم يكون استخدام Vector أو ArrayList على ما يرام. إذا كانت عملية أخرى ، فمن الأفضل اختيار فئة تشغيل مجموعة أخرى. على سبيل المثال ، الوقت الذي يستغرقه فئة مجموعة LinkList لإضافة أو إزالة العناصر في أي موضع في المجموعة هو نفسه؟ هو موقع الفهرس. ستقوم LinkList أيضًا بإنشاء كائنات لكل عنصر إدراج ، وكل ما تحتاجه إلى فهمه سيؤدي أيضًا إلى تحقيق النفقات العامة الإضافية.
أخيرًا ، في كتاب Java العملي ، يقترح بيتر هاججار استخدام صفيف بسيط (صفيف) بدلاً من المتجه أو ArrayList. هذا صحيح بشكل خاص للبرامج ذات كفاءة التنفيذ العالية. لأن استخدام المصفوفات (صفيف) يتجنب المزامنة ، فإن مكالمات طريقة إضافية وإعادة تخصيص عمليات الفضاء غير الضرورية.