סיבוכיות של HashTable

[arik23m]

סיבוכיות של HashTable

יש מבנה נתונים כזה ב-.NET השאלה שלי האם מישהו יכול לשכנע אותי מדוע הסיבוכיות קבועה שם o(1) g ? http://msdn2.microsoft.com/en-us/library/system.collections.hashtable.aspx כמו שכתוב גם פה (להגיע לפיסקה של Hashtable ) http://www.cs.aau.dk/~normark/oop-07/html/notes/collections_themes-dictionary-sect.html

 

[vinney]

זה מבנה די סטנדרטי

עקרונית הסיבוכיות שלו לא בהכרך O של 1 (בחיפוש), אלא אם כן תחום פונקצית הגיבוב קטן (קטן שווה) מהטווח, מה שבד"כ לא קורה. אבל ברמה העקרונית, אם הפונקציה טובה מספיק, הסיבוכיות תהיה נמוכה, אם כי במקרה הגרוע ביותר תהיה O של N. פסקת המפתח לצורך העניין היא:

The load factor of a Hashtable determines the maximum ratio of elements to buckets. Smaller load factors cause faster average lookup times at the cost of increased memory consumption. The default load factor of 1.0 generally provides the best balance between speed and size. A different load factor can also be specified when the Hashtable is created.​

 

[arik23m]

יפה .

כמו שהסקתי שהסיבוכיות תלויה ב-פונקציית ה-hash ואיננה קבועה.(הבוקר היה לי פרויקט להציג וכך הסברתי) תודה על הטרחה.

 

[KarNaF המקורי]

לפי ניתוח לשיעורין

לפי ניתוח לשיעורין Amortized Anlasys - הסיבוכיות היא O(1) בממוצע. אני מציע לפתוח את מבוא של אלגוריתמים של קורמן...

 

[vinney]

ציטוט מקורמן

פרק 12.0:

A hash table is an effective data structure for implementing dictionaries. Although searching for an element in a hash table can take as long as searching for an element in a linked list-- time in the worst case--in practice, hashing performs extremely well. Under reasonable assumptions, the expected time to search for an element in a hash table is O(1).​

הניתוח לשיעורין טוב למקרה ה"ממוצע" של פיזור אחיד, אבל לא הייתי קורה לזה "סיבוכיות קבועה", גם במקרים גרועים צריך להתחשב, במיוחד בשלב בדיקת מבני הנתונים.

 

[KarNaF המקורי]

פשוט הוצאת לי את המילים מהפה ../images/Emo8.gif

 

[dotandvir]

Hash tables

I think most people never implemented a hash table on their own so it seems like a little bit of magic when it actually works. Of course O(1) notations are so error prone - I would say it is sometimes irrelvent if the constant cost is too high. I would also add the cost of the hash function as no one claimed it would be trivial. In cases where the domain of the objects to be stoed in known in advance it is possible to have near perfect hashing or even perfect hashing. It is also interesting to study the concept of rehashing a hash table once a certain number of buckets is over full. Definetely a topic that could fill a whole job interview and with which no CS graduate should claim ignorance., Dotan Dvir