שיחה:טבלת גיבוב

גיבוב?

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

ערןב 18:21, 24 בספטמבר 2006 (IDT)

אני לא נתקלתי עד כה בשם אחר. טרול רפאים 18:23, 24 בספטמבר 2006 (IDT)

עד כמה שאני זוכר, בספר הלימוד של האוניברסיטה הפתוחה (מבוא למדעי המחשב ולשפת בייסיק. יחידה 4 אא"ט) משתמשים במלה "ערבול". ערןב 18:25, 24 בספטמבר 2006 (IDT)

בגוגל החיפוש של שתיהן מניב בערך אותו מספר של תוצאות (~87), כך גם עבור פונקציית גיבוב/ערבול. ערןב 18:27, 24 בספטמבר 2006 (IDT)

ועיון בהיסטוריית הערך מעלה שהערך אכן הועבר מהשם טבלת ערבול על ידי יובל מדר. ערןב 18:28, 24 בספטמבר 2006 (IDT)

בתרגום של הפתוחה לספר של קורמן, לייזרסון וריבסט משתמשים במילה "גיבוב", אם זכרוני אינו מטעני. גדי אלכסנדרוביץ' 09:09, 10 בינואר 2007 (IST)

הוא אינו מטעה אותך תומר א. - שיחה 20:52, 22 בינואר 2009 (IST)

שכתוב הערך

עברתי על טבלת הגיבוב, שיפרתי מעט בקצוות, הערך היה מצוין לדעתי. גיבוב הוא המושג שלמדתי מקורמן, ובהתאם באוניברסיטת ת"א, אני מציע להשאיר אותו. Assafsh 22:04, 21 ביולי 2007 (IDT)

אין התייחסות למקדם העומס, ולסיבוכיות זמן ממוצע הנגזרת ממנו. כמו כן חסר הסבר מפורט יותר על פתרון התנגשויות- שרשור/גיבוב כפול וכו' הדס 22:14, 21 ביולי 2007 (IDT)

אני מסכים שיש אפשרות לפרט ברמה עמוקה יותר, אך יש יתרון יחסי בערך מתומצת. פתרון התנגשויות מתואר במבנה טבלת גיבוב בסיסית, למשל, ולמרות שישנם בודאי פתרונות נוספים אני לא בטוח שכדאי להרחיב על כל אחד. גיבוב כפול צוין בטבלת גיבוב מושלמת, כל הרחבה שלה תגרום לסטיה מהנושא.Assafsh 22:25, 21 ביולי 2007 (IDT)

טעות בהגדרה

ההגדרה שניתנת בראש הערך היא ממש לא ההגדרה של טבלת גיבוב - היא הגדרה של מילון (באנגלית נקרא גם: Associative Array או Map). מילון הוא מבנה נתונים אבסטרקטי שמאפשר לבצע פעולת הכנסה, חיפוש ומחיקה בעזרת מפתחות ולא בעזרת אינדקסים. טבלת גיבוב היא אחד מהמימושים שקיימים למילון, אבל קיימים מימושים רבים נוספים: עץ חיפוש, עץ AVL וכו'. ליאור ג - שיחה 17:05, 7 ביולי 2010 (IDT)

אני נוטה להסכים איתך שההגדרה פשטנית מדי. מה ההגדרה שאתה מציע? תומר א. - שיחה - _{משנה ויקיפדית} 18:47, 7 ביולי 2010 (IDT)

אני מציע לכתוב ערך חדש - מילון (מבנה נתונים), שיהיה תרגום של הערך Associative array בויקיפדיה האנגלית בשילוב עם חלק מהמידע שמופיע בערך הזה ולא אמור להיות פה, ואז להגדיר מחדש את טבלת גיבוב כאחד מהמימושים של מילון (ספציפית - לציין שטבלת גיבוב היא מימוש של מילון שמאפשר הוספה וחיפוש בזמן $O\left(1\right)$ בתוחלת ו- $O\left(n\right)$ במקרה הגרוע. אני כמובן לא רק מציע, אני גם אעשה את זה ברגע שיתפנה לי מעט זמן. ליאור ג - שיחה 02:55, 9 ביולי 2010 (IDT)

מצוין. רק חשוב להתייחס לרעיון שהייחוד בטבלת גיבוב הוא שהיא אמורה לפזר באופן שווה את הערכים על פני כל המבנה). תומר א. - שיחה - _{משנה ויקיפדית} 12:54, 9 ביולי 2010 (IDT)

התנגשויות

אני חושבת שכדאי להוסיף לערך את נושא ההתנגשויות בטבלאות גיבוב. מהם הפתרונות השונים וכולי.

תהליך מחיקת מפתח בתוך טבלת גיבוב

מה תהליך מחיקת מפתח בתוך טבלת גיבוב? אני נעזרת בויקיפדיה לעיתים קרובות ואני מאוד מרוצה. ידע רחב ומאוד אובייקטיבי. אמין מאוד ורמת כתיבה טובה מאוד ומתאימה מאוד לרמת הבנה. תודה רבה הודעה זו נכתבה באמצעות מערכת המשוב. 
46.116.41.241 20:40, 8 בספטמבר 2013 (IST)

הפסקה "מבנים לטבלת גיבוב מתקדמת"

― הועבר מהדף ויקיפדיה:הכה את המומחה/שאלות במדעים מדויקים
מופיע שם בערך פסקה בשם "מבנים לטבלת גיבוב מתקדמת" שלדעתי היא בליל של שטויות. המידע בפסקה הזאת נמצא בערך מהתחלתו וזה היה כל התוכן שלו בהתחלה. נראה לי שזאת השחתה בגלל "הנתונים נשמרים בתבנית של עץ ברוש מצוי"(?!?!), לא מצאתי אזכור לשיטות האלו באינטרנט בעברית או באנגלית, בעריכה הראשונה המשפט "זמן החיפוש של פעולת חיפוש בטבלה זו הוא לינארי" התייחס לhash table עצמו מה שכמובן לא נכון. זמן חיפוש ממוצע קבוע..., הערך נפתח על ידי אלמוני. אני רוצה לשמוע חוות דעת שנייה לפני שאני מוחק את הפסקה. יש כאן מישהו שיכול לאשר שמה שכתוב שם זה לא שטויות או לחילופין שכן? Badidipedia - שיחה 12:50, 4 במאי 2015 (IDT)

לא שאני כל כך מצוי בתחום של עצי ברוש מצוי, אבל לדעתי - הפיסקה הדנה בטבלת גיבוב מתקדמת - אינה (כפי שחשבת) גיבוב של שטויות, אלא מסתבר - שבביטוי (המושאל) "תבנית של עץ ברוש מצוי" - הכוונה הייתה לתת תיאור אינטואיטיבי קומפקטי למבנה של עץ בינארי שבו כמעט לכל צומת אין יותר מבן אחד שאינו עלה. כל עץ בינארי כזה, הוא "מוארך" (כפי שזה גם נקרא מפורשות שם בתחילת המשפט), בעל מבנה ציורי אשר די דומה אפוא למבנה הציורי של עץ ברוש מצוי (שהרי "ברוש מצוי" הוא באמת מוארך). זאת בניגוד אל מה שנדון שם במשפט הבא - אודות מבנה של "ערימה" (גם כן ביטוי מושאל אם כי יותר שימושי בהקשר של מבני נתונים), בעלת מבנה ציורי "שטוח" - שהנו במובן מסויים ההפך מהמבנה הציורי "המוארך" של ברוש מצוי. איך שלא יהיה, אם משום-מה לא נוח הביטוי האינטואיטיבי "ברוש מצוי" (שגם אני טרם נתקלתי בו בהקשר של עץ בינארי יש להודות), אולי אפשר להחליף אותו בביטוי יותר פורמלי (אם כי קצת יותר מסורבל): "עץ שבו כמעט לכל צומת אין יותר מבן אחד שאינו עלה" (בהנחה שאכן לכך התכוון העורך האנונימי). על כל פנים, הבה נמתין לחוות דעת יותר מקצועית, ואז נהיה חכמים יותר באשר לכוונה המקורית. סמי20 - שיחה 16:45, 4 במאי 2015 (IDT)

תודה שיחה. אני מניח שהתכוונת לעץ AVL שהוא מבנה נתונים מסוג עץ חיפוש בינארי. כל הפסקה הנ"ל משתמשת בכל מיני דימויים ומשלים כאשר יש מושגים מוכרים בתחום. בשיטה השנייה שהאנונימי קרא לה "שיטת הקיפול הכפול", הוא כותב: "הנתונים נשמרים בצורת נדבכים/ערימה". אכן קיים מבנה נתונים ערימה אבל למה לכתוב "בצורת ...ערימה" ומה הקשר נדבכים אם כבר נרשם השם המקצועי?! לגבי העץ - גם אם הוא ידע לתאר את השיטה ברמה של ילד בן 4 צריך לטעון גם שהוא המציא את שם השיטות כי אם הכוונה היא לעץ (בתורת הגרפים) אני בספק אם מישהו יכנה שיטה כזאת "העץ המוארך". יש כאן המון נורות אדומות וקיימות מעבר למה שכתבתי. אי אפשר להוכיח שאין לך אחות אבל אם גם פה אף אחד לא יגיד שהוא מכיר שיטות בשמות הנ"ל אני אאלץ להניח שכל הפסקה שם היא השחתה. שמות השיטות של המבנים לטבלאות הגיבוב הם:

• "שיטת העץ המאורך"
• "שיטת הקיפול הכפול" (משחק מילים עם "גיבוב כפול"?!)
• "שיטת יוהאן" (שמו של האלמוני המשחיט שקרא את השיטה על שמו?!)

מישהו מכיר?!

Badidipedia - שיחה 21:02, 4 במאי 2015 (IDT)

לא התכוונתי בהכרח לעץ AVL קלאסי, שהרי מספיק - שלצומת אחד (מתוך מאות צמתים של העץ) יהיו לפחות שני בנים - כדי שהעץ לא יוכל להיחשב כעץ AVL, למרות שהוא עדין יוכל להיחשב כעץ בעל "מבנה של ברוש מצוי" (אם ננקוט בלשונו הציורית של האנונימי).

זה שהניסוח שם הנו חובבני ביותר, זה ברור, אבל מכאן ועד לכנות ניסוח בלתי מקצועי כ"השחתה" - רחוקה הדרך (השחתה היא פעולה זדונית בעוד שניסוח חובבני נעשה בדרך כלל בשוגג). על כל פנים, לפני שהייתי דן את האנונימי כמשחית (אגב לא "משחיט" כפי שבשוגג כתבת), הייתי מציע קודם כל לפנות אל מי שהוסיף את הכותרת "מבנים לטבלת גיבוב מתקדמת", הלא הוא: משתמש:Assafsh. יתכן שהוא יוכל לפתור לנו לא מעט שאלות, הלא כן? סמי20 - שיחה 23:48, 4 במאי 2015 (IDT)

השחתה או לא (סביר להניח שלא), הערך כולו כתוב בצורה רעה (הגשה רעה, ניסוחים בעייתיים, לא מדוייקים וכנראה אף שגויים, מונחים חשודים והיעדר גמור של מקורות חיצוניים) ודורש שכתוב. R.G. - שיחה 23:57, 4 במאי 2015 (IDT)

דומני שעל זה אין מחלוקת. סמי20 - שיחה 01:09, 5 במאי 2015 (IDT)

סמי20, לא הבנתי מה כתבת על עץ AVL ש"מספיק שלצומת אחד יהיו לפחות שני בנים כדי שהעץ לא יוכל להיחשב כעץ AVL". למיטב ידיעתי, עבור כל צומת בעץ AVL יכולים להיות עד 2 בנים כולל. תקן אותי אם אני טועה כי לפני כמה ימים עשיתי עריכה רצינית בערך ואני מקווה של כתבתי שטויות. רעיון טוב לגבי הכותרת. אני מתייג את Assafsh כדי שיחווה דעתו אם כי לדעתי הוא פשוט שינה את הכותרת שתהיה יותר ברורה. אני רק אבהיר שלא באתי להאשים את האנונימי בהשחתה ולהשתלח בו ואני מתנצל אם מישהו נפגע. לגופו של עניין - גם אם זו לא השחתה, אין טעם שיישאר מידע שאף אחד לא יכול להבין אותו. אם אין כאן מישהו שיכול להפיק מידע משמעותי מהפסקה הזאת אז אפשר להניח שאף אחד לא יוכל להפיק ממנו מידע ואפשר להסיר את הפסקה. הניסוח בעריכה הראשונה הוא: "טבלת גיבוב הינה מודל לשמירת נתונים בצורות שונות. ישנן כמה צורות בולטות כגון:..."

R.G.,יש לך קצת ידע בנושא?

Badidipedia - שיחה 01:56, 5 במאי 2015 (IDT)

התנאי שציינת (שיהיו מקסימום שני בנים לכל צומת) תקף לכל עץ בינארי ולא רק לעץ AVL.

בהערה הראשונה שלי על עץ AVL - שעליה תמהת - התהפכו הרישא והסיפא. צריך אם כן להופכן שם בחזרה, וגם להוסיף שם שתי מילים קריטיות שנשמטו בטעות, ולגרוס אפוא כך:

"מספיק - שלצומת אחד (מתוך מאות צמתים של העץ) יהיו לפחות שני בנים שאינם עלים - כדי שהעץ לא יוכל להיחשב כעץ בעל 'מבנה של ברוש מצוי' (אם ננקוט בלשונו הציורית של האנונימי), למרות שהוא עדין יוכל להיחשב כעץ AVL".

סמי20 - שיחה 03:10, 5 במאי 2015 (IDT)

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

סמי20, אולי כאן בינינו אין מחלוקת על הצורך בשכתוב הערך, אבל Assafsh שאותו הזכרת כתב בדף שיחת הערך שהערך היה מצוין לדעתו עוד לפני שהוא ערך אותו. R.G. - שיחה 09:45, 8 במאי 2015 (IDT)

― סוף העברה
Badidipedia - שיחה 12:17, 12 במאי 2015 (IDT) אני מצטער אם דיברתי בלשון מעט קשה. לא התכוונתי לפגוע בעורך האנונימי Badidipedia - שיחה 12:18, 12 במאי 2015 (IDT)

R.G. וסמי20, אתם מוזמנים לקרוא ולתת חוות דעת. Badidipedia - שיחה 13:15, 18 ביוני 2015 (IDT)

שיטת השרשור O(n) ?

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