#algorithms #computer_science

Hash

בעיית המילון

בעיית תחזוק של קבוצה של איברים $S$ בגודל $n$ תחת הפעולות הבאות:
insert(x) - להוסיף $x$ אל $S$
delete(x) - עבור $x \in S$ , להסיר את $x$ מ $S$ .
member(x) החזר כן אם ורק אם $x \in S$

אם ישנו יחס סדר על האיברים נוכל לבנות עץ חיפוש בינארי מאוזן ולתמוך בפעולות הנ״ל בזמן $O (\log n)$ . לעתים לא נרצה יחס סדר כלשהו בין האברים כי הסדר לא בהכרח משנה לנו.

נניח שקבוצת האיברים שלנו נמצאת תחת עולם כלשהו נסמנו $U = [u] = {0, \dots, u - 1}$ . ומתקיים $S \subset U$ .
אם כן אחד הדברים האינטואיטיביים שאפשר לעשות אם אין יחס סדר זה להשתמש במערך בינארי מגודל $u$ .

Pasted image 20230207203051.png|250

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

חסרון

החסרון המשמעותי ביותר וגם הוא די אינטואיטיבי יהיה כאשר $| S | << u$ במצב זה מבזבזים המון זכרון. למשל אם הייתי משתמש בשיטה הזאת כדי לבדוק האם $I P$ קיים או לא הייתי צריך להחזיר אוסף מידע בגודל $256^{4}$ וזה רק עבור IP/4 שלא לדבר על גרסאות כמו IP/6 שיכולות להחזיק אפילו יותר ערכים

באופן כללי נרצה למפה מפתחות כלשהם לאיזשהו אינדקס בטבלת
Pasted image 20230227010453.png|300

פונקציית הגיבוב

רעיון לפתרון הבעיה- נמצא פונקצייה $h : [u] \to [m]$ כאשר $n \leq m << u$ ש מצב אידיאלי מקיימת את התכונות הבאות

א) חוסר בהתנגשויות

\forall_{x, y \in S} : h (x) \neq h (y)

ב) זמן חישוב של $h$ הוא קטן

ג) $m$ יחסית קטן בתקווה שהוא קרוב ל $O (n)$

אם תהיה לנו פונקצייה כזאת , נוכל ליישם את פתרון המערך שהראנו קודם. נגדיר מערך $A [m]$ ויתקיים

x \in S \leftrightarrow A [h (x)] = 1

$A$ נקראת טבלת גיבוב. והפונקצייה $h$ נקראת במצב זה perfect hash.

הרעיון זה שגם אם נביא $x$ מהעולם $U$ שהוא מספר מאוד גדול נוכל למפות אותו לעולם קטן יותר . זמן הריצה תלוי בזמן שלוקח לחשב את $h (x)$ אם הוא קבוע אז שיטת המערך שלנו היא קבועה בידיוק כמו בדוגמה הראשונה.

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

כלומר קיימים $x \neq y$ כך ש $h (x) = h (y)$
אם $y \notin S$ אבל $x \in S$ ניתן להבין את הבעיתיות בשיטה הזאת.

כלומר מטרת העל שלנו היא לבנות את הפונקצייה כך שיהיו כמה שפחות התנגשויות. כמה מטרות ביניים שנרצה להשיג יהיו:

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

נשים לב

המערך לא צריך להיות בינארי אפשר גם לרשום את הערכים עצמם אבל זה לא משפר או מתקן כלום שכן אם יש התנגשויות לא נדע כיצד להתמודד עם זה בידיוק באותו האופן שבוא לא ידענו עם המערך הבינארי

שימוש ברנדומיות

בהינתן קבוצה $S$ עם $n$ איברים מ $[u]$ .נגדיר את הפונקצייה $h : [u] \to [n]$ שעבורה אין התנגשויות כ perfect hash.
זאת פונקצייה שממש קשה למצוא אותה ויש בכלל אפשרות שאם נעדכן את הקבוצה שלנו כמו שאנחנו צריכים לתמוך אז הפונקצייה הזאת כבר לא תהיה רלוונטית.

והחסרון הכי משמעותי הוא שצריך לרוב לבנות את הפונקצייה לפני שבכלל אנחנו יודעים מיהי $S$ . כמו כן מ שובך היונים אנחנו יודעים שאם נקבל פונקציית $h : [u] \to [m]$ הרי שבהכרח עבור $h$ ישנה קבוצה כלשהי של $\frac{u}{m}$ איברים שכולה ממופה לאותו ערך $[m]$ .

Pasted image 20230207212421.png|350
המשמעות היא שאם $S$ במקרה תהיה הקבוצה הזאת אז פונקציית הגיבוב שלנו לא תעבוד בכלל.

הבעיה בשימוש באקראיות לקביעת

h

מספר הפונקציות $h$ שמתאימות לנו הוא $m^{u}$ וברובן יש הרבה התנגשויות. אנחנו רוצים לבחור את אחת מהפונקציות האלה למשל על ידי בחירה של מספר בטווח $[0, m^{u} - 1]$ , הפונקצייה ש״שמורה״ במקום הזה תהיה $h$ . כלומר נתאר את $h$ על ידי המספר של הכניסה ברשימה. היכולת הזאת לשייך מספר לפונקצייה מצריכה זכרון, למעשה עבור קבוצה בגודל $k$ צריך $\log k$ ביטים לייצוג כל הקבוצות ובאופן דומה עבור $m^{u}$ צריך $Ω (u \log m)$ ביטים כדי לשדך מספר לפונקצייה. זה הופך להיות יקר מאוד מהר מאוד. כלומר שימוש בהתפלגות אחידה לבחירה של $h$ היא יקרה מדי.

המסקנה היא שלא נרצה לבחור את הפונקציות ממרחב כל הפונקציות אלא ננסה לרכז אוסף מסויים של תכונות כדי לצמצם את המרחב שממנו בוחרים את הפונקציות.

התכונות החשובות של מרחב הבחירה של h

Uniformity

נרצה שלכל $x \in [u]$ יהיה סיכוי שווה להיות ממופה לכל אחד מהערכים ב $[m]$ כלומר

\forall_{(i, x) \in [m] \times [u]} : P_{h \in H} (h (x) = i) = \frac{1}{m}

collisions

\forall_{x \neq y} : P_{h \in H} (h (x) = h (y)) \leq \frac{1}{m}

כלומר הסיכוי שהפונקצייה שבחרנו מתוך $H$ תקיים את הדרוש צריכה להיות לכל היותר $\frac{1}{m}$ .

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

\forall_{x \neq y} : P_{h \in H} (h (x) = h (y)) \leq \frac{2}{m}

דוגמאות לפונקציות גיבוב

שיטת החלוקה

h (x) = x \cdot m o d m

ברור שנקבל מספר בין $0$ ל $m - 1$ .
שיטה זו לא טובה במיוחד למשל אם $S$ מוכלת בקבוצת המספרים הזוגיים ו $m$ הוא חזקה של $2$ . אז יש טווח גדול של ערכים שאנחנו לא משתמשים בו באמצעות הפונקצייה הזאת.

שיטת הכפל

h (x) = (a \cdot x m o d 2^{w}) \div 2^{w - r}

כאשר $\div$ היא פעולת החילוק ללא שארית (אפשר לדמיין את זה כמו casting ל int).
$a$ נבחר בבחירה רנדומית ובשאיפה שיהיה אי זוגי.
$w$ מייצג את מספר הביטים במילת מחשב. הביטוי $a x m o d 2^{w}$ זה בעצם כל המילים שניתן לייצג עם הגודל $w$ . הכפל $a x$ נותן לי בעצם תוצאה שהיא בגודל של לכל היותר 2 מילות מחשב. פעולת המודולו לוקחת את החצי הימני של המילה. כיוון שכדי לתאר את קבוצת המספרים בין $[0, 2^{w} - 1]$ דרוש עד $w$ ביטים.
$r$ מקיים שהוא $r = \log m$ כלומר $m = 2^{r}$ . כאשר החלוקה מתרחשת אנחנו נפטרים מ $w - r$ הביטים החל מהLSB.

לא אכנס לעומק של נכונות הפונקצייה הזאת ברמה הפרקטית

דוגמה למשפחה אוניברסלית

H = {(a x + b m o d p) \mod m}

כאשר איבר בקבוצה הוא מהצורה $h_{i j} (x) = (i x + j \mod p) \mod m$ .
$a, b$ ייבחרו באקראי מהתחום $[p]$
ו $p > u$ ראשוני (תמיד יש כזה).
פעולת ה $m o d$ תבטיח שכל הערכים ייכנסו לטבלת הגיבוב שלנו.

זאת משפחה שקיימת את תכונת ההתנגשות אך לא אוכיח זאת

לפונקצייה זו יש תכונה חשובה מהסתברות שנקראת אי תלות בזוגות כלומר עבור פונקצייה $h \in H$ יתקיים

\forall_{t_{1, 2}, x_{1} \neq x_{2} \in [u]} : P_{h \in H} (h (x_{1}) = t_{1} \land h (x_{2}) = t_{2}) = P (h (x_{1}) = t_{1}) \cdot P (h (x_{2}) = t_{2})

ואם תכונת ה וuniformity מתקיימת אז

= \frac{1}{m} \cdot \frac{1}{m} = \frac{1}{m^{2}}

הבחנה

במקרה הזה בחירה של הפונקצייה תלויה בפרמטרים $a, b$ כלומר ההסתברות ש $h (x) = h (y)$ לפי $a, b$ שנבחרו היא $\frac{1}{m}$

שיטות להתמודדות עם התנגשויות

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

Chaining

במקום ה $k$ בטבלה מגודל $m$ תהיה רשימה מקושרת של כל האיברים שמופו לערך $k$ על ידי הפונקצייה $h$ .

Pasted image 20230207234550.png|350

במקרה הגרוע חיפוש האם $x \in S$ יהיה $Θ (n)$ שכן אם כל האיברים מופו לאותו ערך ואז במקום זה בטבלה יש רשימה מקושרת של כל האיברים ייתכן שצריך לסרוק את כולם.
נסמן $l (x)$ את מספר האיברים מ $S$ שמופו אל $h (x)$ כלומר מספר ההתנגשויות. $l (x) = Θ (n)$ במקרה גרוע.

נחסום את $l (x)$ במקרה הממוצע כפי שעשינו באלגוריתמים רנדומיים אחרים . המשמעות היא חישוב התוחלת $E [l (x)]$ . אם כן נגדיר משתנה ברנולי $I_{x, y}$ המקיים

I_{x, y} = {\begin{cases} 1 & h (x) = h (y) \\ 0 & e l s e \end{cases}

ולכן

l (x) = \sum_{y \in S} I_{x, y}

כאשר $h$ ממשפחה אוניברסלית מתקיים

E [I_{x y}] = P (h (x) = h (y)) = \frac{1}{m}

ולכן

E [l (x)] = E [\sum_{y \in S} I_{x y}] = \sum E [I_{x y}] = \sum \frac{1}{m} = \frac{n}{m}

המעבר האחרון נובע כי $| S | = n$ .
המשמעות היא קצת כמו במיון דלי . מספר האיברים המצופה שיהיה בכל תא בטבלה הוא $\frac{n}{m}$ . נסמן את זה כ load factor

α = \frac{n}{m}

נשים לב ש $n \leq m$ מאיך שהם מוגדרים ולכן $α \leq 1$ .
סך הכל תוחלת זמן החיפוש תהיה חיפוש התא המתאים $k = h (x)$ וחיפוש ברשימה שזה אומר

O (1 + α)

זמן המחיקה זהה לזמן החיפוש.

עלות להכנסה היא $O (1)$ שכן מכניסים לתחילת הרשימה.
בסיכוי גבוה אורך השרשרת הארוכה ביותר הוא $O (\frac{\log n}{\log \log n})$ . נזכר שסיכוי גבוה הוא $\frac{1}{n^{c}}$ .

הבחנה

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

number of variables \cdot \log (u)

כאשר הסיבה ששמנו $\log u$ היא בגלל שהחסם עליון של המספרים $a, b$ היא $u$ באותה מידה אם הייתי צריך לייצג גם את $p$ ואת $m$ הייתי מקדיש $\log m$ ביטים לייצוג. זה תלוי במספר שמחשבים או מגרילים.
למרות שאנחנו בוחרים מבין פחות אפשרויות אנחנו עדיין מקבלים תוחלת שנותנת התנהגות טובה יחסית שקרובה להתנהגות במצב שבו היינו מגרילים מכל הפונקציות האפשריות.

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

ב) שימוש בשתי פונקציות
במקום פונקציית $h$ אחת נשתמש בשתי פונקציות $h_{1}, h_{2}$ . נכניס את $x$ לרשימה הקטנה יותר ואם אורך של שתי הרשימות זהה בוחרים אחת מהן. שם האלגוריתם נקרא power of two choices. זמן הריצה בסיכוי גבוה הוא $O (\log \log (n))$

Open addressing

הרעיון - במקום פונקציית hash אחת נשתמש ב $m$ פונקציות גיבוב $h_{0}, h_{1}, \dots, h_{m - 1}$ . ונניח שלכל $x \in [u]$ מתקיים ש $(h_{0} (x) \dots h_{m - 1} (x))$ היא פרמוטציה של המספרים $[m]$ . כלומר כל אחת מהפונקציות ישלח אותי למספר אחר.

אלגוריתם החיפוש
כדי לבדוק האם $x \in S$ נפעיל $h_{0} (x)$ ונבדוק האם $x$ נמצא במקום הזה בטבלה. אם יש ערך אחר נפעיל את $h_{1} (x)$ וככה נמשיך עד שנגיע למקום ריק או עד שנמצא את $x$ .

הכנסה
על מנת להכניס איבר $x$ נחפש את המקום הראשון שריק על ידי הפעלת הפונקציות הנ״ל ונכניס לשם את $x$ . בגלל ההנחה שמדובר בפרמוטצייה אנחנו יכולים להסיק שהאלגוריתם יעבוד, כלומר מובטח שיימצא איבר פנוי כל עוד הטבלה לא מלאה . אחרת אם לא נמצא מקום ל $x$ אנחנו בעצם מתמודדים עם טבלה מלאה ויש לבצע פעולה שהיא מחוץ ל סקופ שאדבר עליו כאן. בגדול מבצעים פעולת rehash להגדלת הטבלה.

תחת הנחת הגיבוב האחיד זמן החיפוש וההכנסה הוא $O (\frac{1}{1 - α})$ .

מחיקה
מחיקה במיעון פתוח היא פעולה בעייתית. החיפוש אחר איבר $x$ מתבצע באמצעות מעבר על האיברים $h_{0} (x), h_{1} (x) \dots, h_{m - 1} (x)$ עד שמוצאים את $x$ או שהתא ריק. אם נמחק איבר, ייתכן שהחיפוש ימצא תא ריק לפני שימצא את $x$ למרות ש $x$ במבנה. כדי להתמודד עם זה הפתרון הפשוט ביותר הוא להכניס איבד temp שמסמן מקומות שבהם מחקנו איבר . אם נתקל באיבר מהסוג הזה אנחנו יודעים שמחקנו משם איבר ולכן בהכנסה נבצע השמה אבל בחיפוש נדלג.

בחירה נכונה של סדרת הפונקציות

Linear probing

בבדיקה ליניארית כאשר נמצא התנגשות נתחיל לסרוק את המערך תא אחרי תא (באופן ציקלי, כי זה בידיוק מה שקורה עבור הפעלה של הפונקצייה הבאה בסדרה) עד שנמצא תא ריק ובתא הזה נשים איבר חדש. בוחרים $h \in H$ ומתקיים

h_{i} (x) = (h (x) + i) \mod m

החסרון בשיטה הזאת היא שעלול להיווצר עומס, כלומר הצטברות של איברים רצופים. אם יש בלוק $t$ של תאים רצופים ככל שהוא גדול יותר ככה בסבירות גבוהה יותר שאני אתנגש בו ואצטרך להתחיל לסרוק אותו כלומר ההסתברות שהאיבר הבא ייצטרף לסוף הרצף הזה ויאריך אותו היא $\frac{t + 1}{m}$ . היתרון בשיטה הזאת היא בעיקר ברמה הפרקטית, סמיכות האיברים גורמת להם להיות גם באותה רמה של cache כלומר יהיו פחות cache misses .

quadratic hashing

הרחבה של הבדיקה הליניארית. נבחר $c_{1, 2}$ כאשר $c_{2} \neq 0$ ונקבע לפי $h (x) \in H$

h_{i} (x) = (h (x) + c_{1} \cdot i + c_{2} \cdot i^{2}) \mod m

נשים לב שהבדיקה הליניארית היא מקרה פרטי של $c_{1} = 1, c_{2} = 0$ . היתרון בשיטה זו היא שלא נוצר עומס כמו במקרה הליניארי אבל עדיין יכול להווצר עומס מסדר שני. המשמעות היא שכל $x$ שיקיים $h (x) = a$ ילך לאותו מסלול עבור הפעלת הפונקצייה $h_{i + 1}$ וכן הלאה. במצב זה יש $m$ מסלולים שונים סך הכל. במקרה זה גם צריך לשים לב שהבחירה שלנו היא עדיין פרמוטצייה אחרי השמה של $c_{1, 2}$ .

double hashing

נשתמש בשתי פונקציות hash נפרדות $h_{1, 2} \in H$ ונגדיר

h_{i} (x) = (h_{1} (x) + (h_{2} (x) + 1) \cdot i) mod m

כלומר בכל בדיקה של איבר נעבור מספר צעדים קבוע שהוא $h_{2} (x)$ . אם נבחר את $m$ להיות מספר ראשוני, אז המסלול של כל איבר אכן יהיה פרמוטציה ולכן אם יש מקום פנוי במערך הוא יימצא. בשיטה זו כבר יש $m^{2}$ מסלולים שונים ולכן היא יותר קרובה להנחת הגיבוב האחיד. נשים לב שמקרה של הפרמוטציות הנחת הגיבוב האחיד אומרת שיש $m!$ פרמוטציות שונות אבל בבחירות שלנו עד כה הצלחנו לבנות רק $m$ פרמוטציות שונות ועכשיו יש $m^{2}$ כלומר אנחנו משלמים באקראיות המלא ומאבדים חלק מהפרמוטציות אבל מקבלים בתמורה שיטה סדורה שמבטיחה סדר מסויים של מיקום האיברים בטבלה וטיפול יותר טוב בהתנגשויות , הכנסות ומחיקות.

שילוב – שיטת FKS

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

m = 2 \cdot n^{2}

ונבחר את $h$ מתוך משפחה כמעט אוניברסלית. במצב זה נקבל

P_{h \in H} (h (x) = h (y)) \leq \frac{2}{m} = \frac{1}{n^{2}}

נסמן את הנ״ל כמאורע $A_{x y}$ ויתקיים

P (A_{x y}) \leq \frac{1}{n^{2}}

אנחנו רוצים למצוא מהו הסיכוי שאין התנגשויות

P (no collision) = 1 - P (at least one collision)

P (at least one collision) = P (⋃_{x \leq y} A_{x y}) \leq \sum_{x < y} P (A_{x y}) = (\binom{n}{2}) \cdot \frac{1}{n^{2}} < \frac{1}{2}

המעבר השני נובע מ חסם איחוד ההסתברויות . לכן

P (no collision) = 1 - P (at least one collision) > 1 - \frac{1}{2} = \frac{1}{2}

כלומר עבור $m = 2 \cdot n^{2}$ בסיכוי גבוה אין התנגשות.

רעיון לבחור פונקציה כמעט אוניברסלית $h : [u] \to [m]$ . אם אין התנגשויות כאשר מפעילים את $h$ על כל האיברים ב $S$ אז סיימנו. תוחלת מספר האיטרציות היא לכל היותר 2 כי ההסתברות להצלחה גדולה מ $\frac{1}{2}$ . אם יש התנגשויות נחזור על כל התהליך.

במצב זה הגיבוב הוא מושלם אבל נקבל טבלה גדולה מאוד רצינו ש $m = O (n)$ . כמו כן חסרון משמעותי הוא העובדה שאני צריך להריץ את פונקציית הגיבוב שבחרתי $O (n)$ פעמים על כל איברי $S$ כדי לוודא שאין התנגשויות.

אם כן כעת נוכל לדבר על שיטת FKS. שמשלבת בין השיטה הנ״ל לשיטת chaining. הסיבה לשילוב היא שאומנם בשרשור פונקציית הhash לא מושלמת אבל הטיפול בהתנגשויות במצב של הכנסה מושלם ובמקרה הסטטי שעכשיו תיארנו פונקציית הhash היא מושלמת אבל גודל הטבלה הוא גדול מדי.

הרעיון הוא להשתמש בפונקצייה כמעט אוניברסלית $h$ כמו מקודם. אבל נקבע $m = n$ . כמובן שבהתסברות גבוהה יותר שנקבל בחלק מהתאים התנגשות.

לכל מספר $i \in [m]$ נסמן ב $n_{i}$ את מספר האיברים שמופו לתא ה $i$

n_{i} = | {x \in S | h (x) = i} |

אם $n_{i} \geq 2$ יש התנגשות.

כעת עבור $i \in [m]$ נחפש פונקציית גיבוב מושלמת $h_{i} : [u] \to [2 n_{i}^{2}]$ בידיוק כמו במצב הסטטי רק עבור הקבוצה ${x \in S | h (x) = i}$ . נמפה כל איבר בקבוצה ${x \in S | h (x) = i}$ למקום בטבלה ה $i$ שנקבע על פי $h_{i}$

Pasted image 20230208021130.png|450

למעשה הרעיון הוא הפעלה של פונקציית hash פעמיים. פעם אחת כדי להיות ממופה לתא ה $i$ ובפעם השנייה כדי לקבל את המיקום הספציפי בטבלה לפי $h_{i}$ שהיא מושלמת.

חיפוש
דורש הפעלת שתי hash כלומר $O (1)$ .
נשים לב שאין תמיכה בהכנסה ומחיקה

בנייה
עבור $i \in [n]$ נשקיע $O (n_{i}^{2})$ זמן בתוחלת וגם $O (n_{i}^{2})$ זכרון. סך הכל

O (\sum_{i = 0}^{m - 1} n_{i}^{2})

לא אכנס להוכחה אבל מתקיים $E [\sum_{i = 0}^{m - 1} n_{i}^{2}] < 3 n$ ולכן בתוחלת הזמן לבנייה הוא $O (n)$ שזה יתרון על בני הבנייה במקרה הסטטי.

גיבוב קוקיה

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

בשיטת גיבוב הקוקיה נשתמש בשתי פונקציות גיבוב $h_{0}, h_{1} : U \to [m]$ בלתי תלויות. ונגדיר כבר עכשיו ש $m = 4 n$ לטבלה שתשמור $n$ איברים. לכל איבר בעולם שלנו $x \in U$ אם כך יש שני מקומות מתאימים בטבלה $h_{1, 0} (x)$ . שיטה זו יחסית פשוטה ביחס לשיטות אחרות אבל ישנם מקרי קצה שצריך לדון בהם.

search(x)
	if x is in h0(x) or h1(x)
		return x
	return "x is not in the table" or NULL

delete(x)
	if x = search(x) is not NULL
		delete(x)

היתרון הברור של גיבוב הקוקיה על פני שיטות אחרות היא שחיפוש ומחיקה הם בזמן קבוע במקרה הגרוע ולא רק בתוחלת או בהסתברות גבוהה.

הכנסה

אלגוריתם ההכנסה דומה לאיך שעובדת ציפור הקוקיה בטבע. איבר חדש שנכנס למבנה עם הערך $x$ יישמר בתא $h_{0} (x)$ . הבעיה היחידה היא מה קורה כאשר התא הזה תפוס על ידי $y$ . במצב זה נעביר את $y$ לתא אחר כלומר אם $y$ נמצא ב $h_{0} (x) = h_{0} (y)$ אז נעביר אותו ל $h_{1} (y)$ . אם $y$ נמצא ב $h_{0} (x) = h_{1} (y)$ אז נעביר אותו ל $h_{0} (y)$
כמובן שכתוצאה מההכנסה הזאת אנחנו יכולים להתקל בבעיה חדשה כלומר, אותה הבעיה פשוט על התאים שעכשיו אנחנו רוצים להכניס את $y$ . כלומר נוכל לפתור את הבעיה באותו אופן. נחלק למקרים :

אם המשכנו את התהליך עד מציאת תא ריק - נכניס לתא הריק
אם ביצענו את התהליך $c \log n$ פעמים אז נעצור את הריקורסייה ונבנה את כל המבנה מהתחלה במקום לנסות להמשיך לתקן. המשמעות היא שמגרילים שתי פונקציות גיבוב חדשות ומכניסים את כל האיברים לטבלה חדשה על פי הפונקציות האלו.

סוגי הכנסות

ברמה העקרונית ישנם שלושה סוגים של מסלולי הזזה- כלומר סדרות של מעברים של איברים כתוצאה מהכנסת איבר חדש. כדי להבין יותר טוב איך זה נראה נוכל להסתכל על הגרף התואם לטבלה. בגרף יהיו $m$ קודקודים- קודקוד אחד לכל תא, ו $n$ קשתות- כך שלכל $x \in S$ נוסיף לגרף את הקשרת $h_{0} (x), h_{1} (x)$ באופן לא מכוון. אם כן מסלולי ההזזה הם

Pasted image 20230208024514.png|250

א) מסלול פשוט סדרה של $k$ איברים שונים $x_{1} \dots x_{k + 1}$ כך ש $x = x_{1}$ ומסלול זה מתחיל ב $h_{0} (x_{1})$ ובכל צעד מתקדם על הקשת $(h_{0} (x_{i}), h_{1} (x_{i}))$ (בכיוון המתאים ביחס לקודקוד שממנו באנו.) ומעבירים את האיבר ה $x_{i}$ מהתא בו הוא היה נמצא לתא השני שלו.

ב) מעגל אחד סדרה של $k$ איברים כך שבנקודה מסוימת איבר מופיע פעמיים. במקרה הזה אנחנו נחזור על עקבותנו עד להתחלה כלומר $h_{0} (x)$ אבל עם איבר חדש ואז נעביר את האיבר החדש לאפשרות השנייה שלו על ידי הפעלת $h_{1}$ ונמשיך במסלול פשוט עד שנגיע לתא ריק. נשים לב שזה לא מעגל מהצורה שתגרום ללולאה אינסופית שכן הגענו לאותו אינדקס בטבלה הראשונה עם ערך חדש

ג) מעגל כפול - מצב שבוא מגיעים בטבלה הראשונה במקום לתא ריק נגיע לאיבר $x$ שכבר ביקרנו בו וכתוצאה מכך סדרת ההזזות תהיה אינסופית.

ניתוח
לא אכנס לניתוח המדוייק של זה כאן , אבל לסיכום זה יוצא

חיפוש ומחיקה ב $O (1)$ במקרה הגרוע
תוחלת ההכנסה בניתוח לשיעורין $O (1)$
בסבירות גבוהה בניתוח לשיעורין הכנסה גם כן ב $O (1)$