ما هي الفراش المناسب لهذا الموقف؟

Question

أحاول أن أقرر بيانات البيانات التي تستخدمها لتخزين أزواج القيمة الرئيسية عندما تكون الميزات المطلوبة فقط

• إدراج
• ابحث عن

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

المفاتيح هي tuples عدد صحيح، والقيم هي مؤشرات (المراجع، أيا كان). أنا فقط تخزين زوجين مليون أزواج تنتشر فوق الكائنات (الكثير).

حاليا أنا أفكر في استخدام إما

• جدول التجزئة
• شجرة KD
• شجرة ب

أنا أتميل نحو جدول التجزئة (ل O(1) وقت الإدراج / البحث)، لكنني أردت تأكيد ميول بلدي.

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

Answer 1

ستكون Hashtable الخيار الأفضل هنا كجميع العمليات التي تهمك أنت O (1) (وكما يجب أن لا داعي للقلق بشأن إنشاء Hashtables متعددة).

Answer 2

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

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

Answer 3

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

Answer 4

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