הצגת המקור של הדף "תכנות מתקדם ב-Java/מבני נתונים מתקדמים"

{{תכנות מתקדם ב-Java}}
בפרק זה נלמד על נושאים שמתקרבים גם לענפים התיאורטיים יותר של מדעי המחשב, והם בעלי השלכות חשובות לתוכניות שתכתבו. נכיר כמה מושגים מעולם מדעי המחשב, ונראה כמה דרכים מתקדמות יותר לאחסון של מידע.

{{שימו לב|כל החישובים וההגדרות שמופיעים בפרק זה אינם פורמליים ומובאים אך ורק למטרת היכרות בסיסית עם הנושא. }}

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

===אלגוריתמים===
[[w:he:אלגוריתם|אלגוריתם]] - דרך שיטתית ומוגדרת היטב לפתרון של בעייה מסויימת. קיימים אינספור אלגוריתמים, החל מקצרים ופשוטים וכלה באלגוריתמים מסובכים ומורכבים. 

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

קל לראות שאם נשתמש באלגוריתם נוכל למצוא את המספר המקסימלי במערך נתון. אפשר גם לראות שאפשר להפוך בקלות יחסית את האלגוריתם הזה לשיטה בג'אווה שמקבלת מערך כזה ומחזירה את הדרוש.
למשל:
<div class="mw-content-ltr"><source lang="java">
public static int findMaxInt(int[] arr) {
    if(arr == null) return 0;
    int max = 0;
    for(int i=0; i<arr.length; i++) {
	if(arr[i] > max) max = arr[i];
    }
    return max;
}

</source>
</div>
{{משימה|כיצד תשנו את האלגוריתם כך שיעבוד גם בלי ההנחה שכל המספרים במערך הם חיוביים? חשבו על המקרה בו כל המספרים הם שליליים.}}

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

===סיבוכיות===
[[w:he:סיבוכיות|סיבוכיות]] היא דרך לאמוד את יעילותו של אלגוריתם, בהתאם לגודל הקלט הניתן לו. כאן נתמקד בעיקר במחיר '''זמן הריצה''' של אלגוריתם מסויים. קיימות כמה דרכים לאמוד סיבוכיות של זמן ריצה, אנו נעסוק כאן רק בדרך אחת - המאמץ הנדרש במקרה הגרוע ביותר (Worst case).  

====סימונים====
נהוג לסמן את גודל הקלט באות <math dir="ltr">\displaystyle n</math>. את פונקציית הסיבוכיות של המקרה הגרוע ביותר מסמנים באות <math dir="ltr">\displaystyle O</math> (אות O גדולה. אות o קטנה היא בעלת משמעות אחרת). 
אם נרצה לומר, לדוגמה, כי סיבוכיות של אלגוריתם מסויים היא <math dir="ltr">\displaystyle n^2</math> נסמן זאת ב-<math dir = "ltr">\displaystyle O(n^2)</math>

====חישוב הסיבוכיות====
=====מציאת המקסימלי במערך=====
נתבונן על האלגוריתם שראינו קודם, למציאת מספר מקסימלי במערך: תחילה, מכניסים ל-max ערך - זו פעולה בודדת. לאחר מכן, אנו עוברים על כל איברי המערך, ובכל שלב מבצעים השוואה בין המשתנים - פעולה בודדת, ואולי גם מבצעים השמה - מכניסים למשתנה max ערך. גם זו פעולה בודדת. לכן, בסך הכל, האלגוריתם דורש ביצוע של לכל היותר <math dir="ltr">\displaystyle n*2 + 1</math> פעולות (במקרה בו בכל שלב ביצענו השמה ל-max), כאשר n הוא גודל המערך בו רצינו למצוא את האיבר המקסימלי. בחישובי סיבוכיות, תמיד ניקח בחשבון רק את המצבים בהם גודל הקלט הוא עצום - שואף לאינסוף. במצב זה, אין משמעות למספרים קבועים. כאשר אנו מתעסקים עם מערך בגודל מיליון תאים, ההבדל בין 2 מיליון פעולות ל-2 מיליון ושתיים הוא זניח. יתר על כן, אפילו מכפלות במספר קבוע לא משנות לנו: לא משנה עבורנו אם יתבצעו שתי מיליון פעולות, שלוש מיליון, או 50 מיליון (ההסבר מדוע זה כך נובע מההגדרה המתמטית, בה לא נעסוק בספר זה). לכן, הסיבוכיות של האלגוריתם שראינו למציאת המקסימלי היא <math dir="ltr">\displaystyle O(n)</math>.

=====מיון בחירה=====
[[w:he:מיון בחירה|מיון בחירה]] הוא דרך פשוטה לסדר מערך. באופן מילולי, ניתן לתאר אותו בצורה הבאה:
# חפש את האיבר הקטן ביותר במערך והחלף אותו עם האיבר הראשון.
# חזור על התהליך עבור כל איברי המערך (כלומר - כעת עבור על כל איברי המערך פרט לראשון, חפש את המינימלי מביניהם והחלף עם השני, וכן הלאה).
כמה פעולות דורש המיון? עבור כל איבר במערך, מתבצעות כמה פעולות: 
* מציאת המינימלי, שהיא פעולה שכרוכה במעבר על כל איברי המערך (ליתר דיוק - איברי המערך, מאיבר זה והלאה) - מחיר פעולה זו הוא <math dir="ltr">\displaystyle O(n)</math>. שימו לב שגם כאן אנו מתעלמים בחישוב מהעובדה שבכל פעם אנו עוברים על פחות ופחות איברים (אפשר לראות שהחיסכון הכולל מכך הוא <math dir="ltr">\displaystyle n/2</math> פעולות, אבל זה כפל בקבוע, בו אין צורך להתחשב כאן).
* החלפת שני איברים היא פעולה שעלותה <math dir="ltr">\displaystyle O(1)</math>.
סך הכל, עבור כל איבר במערך (בו יש <math dir="ltr">\displaystyle n</math> איברים), מתבצעות פעולות שעלותן <math dir="ltr">\displaystyle O(n)</math>. לכן, העלות הכוללת של המיון היא <math dir="ltr">\displaystyle O(n^2)</math>.

=====חישובים כלליים=====
אופן החישוב של סיבוכיות אלגוריתם מסויים מבוסס על קצב הגידול במספר הפעולות של אלגוריתם מסויים ככל שהקלט גדל. לכן, בחישוב הסיבוכיות אפשר להתעלם מגדלים קבועים. לגבי פעולות בסיסיות כמו פעולות אריתמטיות פשוטות, השוואות בין משתנים וכדומה, נוכל להניח שהן דורשות פעולה בודדת - <math dir="ltr">\displaystyle O(1)</math>. זה לא מדוייק (למשל: למרות שנתייחס כך למרבית החישובים המתמטיים, יש מהם שדורשים מספר פעולות רב שתלוי באורך הקלט הניתן להם), אך מספיק לצרכינו. 

כעת חישוב הסיבוכיות (של המקרה הגרוע) מתבסס על מספר הפעולות הבסיסיות הדרושות לנו עד שהאלגוריתם מגיע לסיומו, בדומה לאופן בו חישבנו את הסיבוכיות בשתי הדוגמאות שלעיל. 

ההצדקה לאופן הגס של חישוב הסיבוכיות נובעת מכך שמטרת הסיבוכיות היא לאמוד '''סדרי גודל''': באיזו מהירות צומח מספר הפעולות הדרוש כאשר הקלט הולך וגדל. מספר הפעולות שידרוש אלגוריתם שהסיבוכיות שלו היא <math dir="ltr">\displaystyle O(n)</math> יגדל בצורה פרופורציונלית לגידול בקלט. מספר הפעולות שידרוש אלגוריתם שהסיבוכיות שלו היא <math dir="ltr">\displaystyle O(n^2)</math> יגדל באופן מהיר יותר (אך עדיין סביר, בדרך כלל), בעוד מספר הפעולות עבור אלגוריתם <math dir="ltr">\displaystyle O(Log(n))</math> יגדל במהירות קטנה יותר. אלגוריתם שסיבוכיותו היא <math dir="ltr">\displaystyle O(2^n)</math> יהיה כרוך בגידול עצום במספר הפעולות, ועבור קלטים גדולים מאוד הוא יהיה כמעט חסר תועלת.

נגענו כאן רק בקצה המזלג בנושא רחב. להבנה טובה יותר, מומלץ לעבור על ההגדרות מתמטיות המדויקות יותר, אותן ניתן לראות ב[[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים|ספר על מבני נתונים ואלגוריתמים]], בחלק העוסק באלגוריתמים. 

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

===תור ומחסנית===
תור ומחסנית הם מבני נתונים פשוטים מאוד, הדומים זה לזה דמיון רב. כשמם כן הם:
* '''תור''' (Queue) מאפשר הצצה לראש התור, הוצאת איבר מראש התור, הכנסת איבר לסוף התור. התור עובד בשיטה של "בא ראשון - יוצא ראשון" (First in first out - FIFO).
* '''מחסנית''' (Stack) מאפשרת הצצה לראש המחסנית, הוצאת איבר מתחילת המחסנית, והכנסת איבר לתחילת המחסנית. המחסנית עובדת בשיטה של "בא ראשון - יוצא אחרון" (First in last out - FILO).
בנוסף, מתאפשרת בדיקה האם התור/המחסנית ריקים. באופן מפתיע, למרות מספר הפעולות המצומצם שהם מאפשרים, תורים ומחסניות נמצאים בשימוש רחב, למשל:
* כאשר שולחים מספר עבודות להדפסה, נוצר תור של עבודות הממתינות להדפסה.
* כאשר פונקציה קוראת לפונקציה אחרת, המידע על מצב הפונקציה (והפונקציות שקראו לה) נשמר במחסנית מיוחדת.

המימוש של תורים ומחסניות אינו קבוע. התנאי הוא שכל מימוש חייב ליישם את הממשק שפורט למעלה (הכנסת איבר וכדומה). מימוש נפוץ הוא בעזרת רשימה מקושרת.

====יעילות====
תורים ומחסניות הם מבני נתונים מופשטים, שמימושם אינו קבוע. לכן, גם הסיבוכיות של השימוש בהם משתנה ותלויית מימוש. המימוש הנפוץ, בעזרת רשימה מקושרת (בתור - רשימה דו כיוונית), מאפשר הכנסה, הוצאה, ובדיקת ריקנות בעלות של <math dir="ltr">\displaystyle O(1)</math>. 

===עצים בינאריים===
[[תמונה:Binary tree.svg|left|thumb|250px|עץ בינארי לא סדור]]
ראינו כבר מבנה בשם רשימה מקושרת - שרשרת של חוליות, כאשר כל חוליה מחוברת רק לחוליה הבאה אחריה. [[w:he:עץ בינארי|עץ בינארי]] מזכיר בצורתו רשימה כזו, רק שכאן - כל חוליה עשויה להחזיק חיבור אחד, שני חיבורים, או - אף חיבור. חיבורים אלו מכונים "'''צאצאים'''". מעתה, נכנה את החוליות "'''קדקודים'''", ואת החוליה הראשונה - ה'''שורש''' של העץ. רשימה כזאת ניתן לסדר בצורה שמזכירה מעין עץ (בדרך כלל, עץ הפוך - השורש הוא הגבוה ביותר והעץ "צומח" לכיוון מטה). מבנה העץ עשוי לספק לנו כמה יתרונות, אותם נראה בהמשך. 
נעיר כי עצים אינם בהכרח בינאריים, אינם בהכרח סדורים, ואינם בהכרח ממומשים במבנה המזכיר רשימה מקושרת. אנו נתמקד כאן רק ב[[w:he:עץ חיפוש#עץ בינארי|עץ חיפוש בינארי]], מכיוון שהבנה שלו תעניק בסיס להבנה של מבנים מסובכים יותר המבוססים עליו (בדרך כלל, עם שינויים כאלה ואחרים).

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

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

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

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

====יעילות====
בפעולות של הכנסה, מחיקה, וחיפוש איבר בעץ, אפשר לראות שמתבצע מעבר על קדקודי העץ, מראש העץ ועד מציאת האיבר הרצוי (כמו שכבר הוסבר קודם, פעולת המחיקה אמנם עשויה לדרוש שני חיפושים ולא אחד, אך מבחינת הסיבוכיות אין הבדל). ההנחה היא שפעולות על הקדקודים כמו הדפסה, מחיקה, או מציאת הצאצאים (וההורה) של קדקוד מסויים מתבצעות בסיבוכיות של <math dir="ltr">\displaystyle O(1)</math>. אם כך, המקרה הגרוע ביותר עבורנו, בו כל קדקודי העץ ממוקמים בזה אחרי זה ידרוש מעבר על כל איברי העץ. אם n הוא גודל העץ, סיבוכיות המקרה הגרוע היא <math dir="ltr">\displaystyle O(n)</math>. עם זאת, זה לא מקרה נפוץ. במקרים רבים צורת העץ תהייה מאוזנת יותר, וכך נשיג סיבוכיות ממוצעת של <math dir="ltr">\displaystyle O(Log(n))</math>. כדי לשפר את ביצועי העצים הבינאריים, פותחו עצים מתקדמים יותר (למשל: עצים אדומים-שחורים), שבמחיר נמוך יחסית מבטיחים איזון של העץ. רוב המימושים הקיימים של עצים בינאריים מתבססים על עצים מאוזנים.
מעבר על כל העץ, מטבעו, דורש מעבר על כל האיברים בעץ, ולכן יעלה במחיר של <math dir="ltr">\displaystyle O(n)</math>.

===טבלת גיבוב===
[[w:he:טבלת גיבוב|טבלת גיבוב]] (Hash Table) היא מבנה נתונים המאפשר הכנסה ושליפה מהירה של נתונים, באופן הדומה למערך: עבור כל נתון (גם נתון שלא נמצא בטבלה) קיים מספר סידורי ידוע, אליו נכניס את הנתון, ואם נרצה לשלוף אותו - נדע ששם הוא צריך להיות. מסיבה זו, לפעמים מכונה טבלת גיבוב גם "מערך אסוציאיטיבי".
חלק קריטי בשימוש בטבלה כזו הוא מציאת הדרך בעזרתה נדע לחשב את אותו מספר סידורי עבור כל נתון. לשם כך, משתמשים בפונקציה מתמטית בשם "[[w:he:פונקציית גיבוב|פונקציית גיבוב]]", שבהינתן קלט מסויים - תדע להמיר אותו למספר. הערה: בהקשרים אחרים, הגדרת פונקציית גיבוב והשימושים בה רחבים יותר ממה שנראה כאן.

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

לדוגמה: עבור מחרוזות, אפשר להחליט כי ערך המחרוזת יחושב באופן הבא: ערכה של כל אות יהיה שווה למיקומה בא"ב (למשל: א=1, ב=2, וכן הלאה) כפול גודל האלפבית בחזקת מיקומה במילה. למשל, נחשב את ערך המילה "שלום". מכיוון שמדובר באלפבית עברי, גודלו הוא 26 (כולל הסופיות).
* ש=21. האות הראשונה במילה, ערכה מוכפל ב-1.
* ל=12. האות השנייה במילה, ערכה מוכפל ב-26.
* ו=6. האות השלישית במילה, ערכה מוכפל ב-26*26 = 676.
* מ=13. האות הרביעית במילה, ערכה מוכפל ב-26*26*26 = 17576.
סך הכל: 21 * 1 + 12 * 26 + 6 * 676 + 13 * 17576 = 232877.

התחום של פונקציות הגיבוב הוא גדול ורחב. בג'אווה, המחלקה Object מכילה את השיטה hashCode, וכל אובייקט קיים כבר מממש אותה, כך שאין צורך לכתוב אותה עבור מחלקות כמו String.

===השימוש בטבלת הגיבוב===
כאשר יש לנו פונקציית הגיבוב, שאר העבודה הוא פשוט למדי: כשנרצה להכניס נתון מסוים, נחשב את מספרו הסידורי בעזרת פונקציית הגיבוב, ולתא שזה מספרו נכניס את הנתון. כאשר נרצה לשלוף נתון, נחשב את מספרו הסידורי, ולפי זה ניגש לתא הרצוי ונשלוף משם את הנתון. 
עם זאת, יש כאן בעייה נוספת: ייתכן שהמספר הסידורי שקיבלנו עובר את גודלה של הטבלה בה אנו משתמשים לאחסון. הפתרון הנפוץ: שימוש בפונקציית המודולו (שארית).
למשל: נניח שנרצה להכניס לטבלה בגודל 15 (לשם הפשטות, נניח שמספרי התאים הם 1 עד 15) את המספרים הסידוריים 13, 17, ו-33.
13 מודולו 15 שווה ל-13, ולכן נכניס אותו לתא מספר 13. 17 מודולו 15 שווה ל-2, לכן נכניס אותו לתא מספר 2. 33 מודולו 15 שווה ל-3, לכן נכניס אותו לתא מספר 3. 

===ניהול התנגשויות===
כאן מתעוררת בעייה נוספת: ומה אם שני נתונים שונים יקבלו מספר זהה? את הבעייה הזו אפשר לפתור באחת משתי דרכים:
* '''טבלה פתוחה''' - כאשר אנו מנסים להכניס נתון חדש לטבלה ומגלים שהמקום הרצוי (כלומר, המקום שאת מספרו מצאה פונקציית הגיבוב) כבר תפוס, נמשיך לתאים הבאים עד שנמצא תא פנוי ובו נמקם את הנתון. כאשר נרצה לחפש נתון, נתחיל במקום בטבלה אליו תפנה פונקציית הגיבוב ונבדוק אם האיבר שרצינו למצוא נמצא שם. אם התא תפוס אך האיבר שלנו לא שם - נמשיך הלאה עד שנמצא אותו (או עד שנגיע לתא ריק ונוכל לדעת שהוא לא נמצא).
* '''טבלה סגורה''' - בטבלה סגורה אנו משתמשים ברשימות מקושרות: בכל מקום בטבלה תהייה רשימה מקושרת. כאשר מכניסים איבר חדש, מכניסים אותו לסוף הרשימה (שנמצאת במקום אליו הפנתה אותנו פונקציית הגיבוב). כאשר שולפים איבר, פונים לרשימה שנמצאת במקום הרצוי ועוברים עליה עד שמוצאים את שחיפשנו (או עד שהרשימה נגמרה והאיבר לא נמצא).
כמו תמיד, יש יתרונות וחסרונות בכל אחת מהשיטות האלו.

====יעילות====
טבלת הגיבוב היא מבנה שיעיל במיוחד להכנסה ושליפה של נתונים בעלי מפתח ידוע. בהנחה שעלותה של פונקציית הגיבוב היא <math dir="ltr">\displaystyle O(1)</math>, נוכל להשיג עלות הכנסה, שליפה ומחיקה הקרובה ל-<math dir="ltr">\displaystyle O(1)</math>.

====יתרונות וחסרונות====
יתרונה הגדול של טבלת הגיבוב הוא במהירות הגדולה של ביצוע הפעולות הבסיסיות - הכנסה, הוצאה, ושליפה. תכונה זו הופכת את טבלת הגיבוב למבנה נתונים מצויין במקרים רבים. עם זאת, גם טבלת גיבוב סובלת מחסרונות. החסרון הראשון הוא שכמות גדולה של נתונים פוגעת בביצועי הטבלה. למשל: אם בטבלה פתוחה שגודלה 10 נכניס 1000 נתונים, אז אפילו אם החלוקה טובה מאוד ובכל מקום בטבלה יהיו בדיוק 100 נתונים, עדיין - שליפה של כל נתון תעלה במחיר של מעבר לאורך רשימה באורך 100. זוהי בעייה שניתנת לפיתרון באמצעות הגדלת הטבלה כאשר כמות הנתונים חוצה רף מסויים. 
בעייה אחרת של הטבלה היא המוגבלות של שליפת הנתונים. למשל: בספר טלפונים המבוסס על טבלת גיבוב, לא ניתן לחפש את כל האנשים ששמם מתחיל ב-"ד" (בלי לעבור על כל הרשומות בטבלה), או להדפיס את תוכן הספר על פי סדר האלפבית (מבלי להעתיק קודם את תוכן הספר למבנה נתונים אחר). 

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

{{תכנות מתקדם ב-Java|מוגבל}}

[[קטגוריה:תכנות מתקדם ב-Java|מבני נתונים מתקדמים]]