كتب hash parsing with string
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
تحليل الهاش مع سلسلة (معلومة)
عند إعطاءنا جدول T hg الذي يحوي على m خلايا و n قيم نعرف مقدم الكثافة(load factor) الخاص ب-T أو a=n/m اي معدل القيم المحفوظة في السلسلة الواحدة في السيناريو الأسوأ فعالية الهاش مع سلسلة جدا سيئة : كل n المفاتيح موزعين لنفس الخلية ونكون سلسلة طويلة جدا والبحث عندها سيكون (O(n +الوقت المطلوب لحساب دالة الهاش وهو ليس بأفضل من البحث في سلاسل عادية اما في السيناريو الوسط فعالية الهاش تقاس بمدى توزيع الدالة h للقيم بين المفاتيح سنفترض ان التوزيع سيكون بالتساوي اي ان الاحتمال بان قيمة معينة تذهب إلى مفتاح متساوية بين كل المفاتيح وكذلك سنفترض ان حساب دالة الهاش هو (O(1 قانون : في جدول هاش مع سلسلة فيه التوزيع متساو لكل المفاتيح بحث فاشل يقوم ب-(O(1+a فعاليات (وقت الفعالية) اثبات : بما ان التوزيع متساو لكل المفاتيح الاحتمال بان مفتاح K يذهب لخلية معينة متساو لكل الخلايا (m خلايا) لذا الوقت المتوسط للبحث الفاشل عن k مساو تماما للوقت المتوسط لبحث أحد السلاسل والطول المتوقع لسلسلة كهذه هو مقدم الكثافة أو a اي ان وقت البحث المتوسط هو a ومع حساب دالة الهاش : الوقت المتوقع هو : (O(1+a. قانون : في جدول هاش مع تشابك وفي الجدول التوزيع للمفاتيح متساو, بحث ناجح متوسط وقت البحث هو: (O(1+a. ومن القانونين في الأعلى نستنتج ان كبر الجدول يجب أن يكون مشابها لعدد القيم المراد تخزينها اي بحالة وجود (O(n قيم عندها كبر الجدول هو (O(n وعندها تكون العلمليات كل واحد منها تنفذ ب-(O(1 وقت
