stanford-oval/wikipedia huggingface dataset:
פרס גראמי לביצוע ה-R&B העממי הטוב ביותר
זוכים ומועמדים

הערה: הזוכה מסומן בצהוב
קיסרות אקסום

| --- | --- |

 
 ממשל
 משטר:  קיסרות
 שפה נפוצה:  געז ויוונית
 עיר בירה:  אקסום
 גאוגרפיה
 יבשת:  אפריקה, אסיה
 היסטוריה
 הקמה:  פרוטו-אקסום
 תאריך:  המאה ה-1 לפנה"ס
 פירוק:  כיבושי האסלאם (אנ') מרד יהודית
 תאריך:  850
 ישות קודמת:  ממלכת דעמת
 ישות יורשת:  ממלכת ביתא ישראל
 שטח בעבר:  1.25 מיליון קמ"ר (נכון ל־מאה ה-4 וה-5)
 אוכלוסייה בעבר:  כ-500,000   להוציא שטחים כבושים (נכון ל־מאה ה-4 וה-5)
 כלכלה
 מטבע:  מטבע אקסומי
 
קיסרות אקסוּם (בגעז: መንግሥተ አክሱም) הייתה ישות מדינית וכלכלית חשובה באזור חבש בצפון-מזרחה של אפריקה, בשטחי אתיופיה ואריתריאה של ימינו. הממלכה, שמרכזה בעיר אקסום (המצויה בצפון שטח אתיופיה המודרנית), הוקמה במאה ה-1 לפני הספירה, והפכה לקיסרות (אימפריה) באופן רשמי כאשר המלך סאמבראוטאס הכריז על עצמו כ"קיסר" (ንጉሠ ነገሥት; מילולית: מלך המלכים).
שם הקיסרות

אקסום: בספר אקסום, אוסף כתבים שנכתב במאה ה-15 על ההיסטוריה האקסומית, נטען שהשם אקסום נגזר משמו של אקסומווי שייסד את העיר אקסום והיה בנו של אתיופיס.
אתיופיה: בשם זה כינו היוונים והביזנטים את כל האזור שמדרום למצרים. במאה ה־4 לאחר שהקיסר אזנה אימץ את הנצרות כדת המדינה ולאחר כיבוש ממלכת כוש, הוא החליף את שמה הרשמי של אקסום לאתיופיה.
חבש: (בגעז: ሐበሻ) הוא חבל ארץ גאוגרפי-היסטורי בצפון-מזרח קרן אפריקה. מקור השם משפת הגעז, מהמילה ሐበሣ (חבּשׂה), ונכתב לראשונה כחבּס בשפה השבאית. אדוארד גלייזר (אנ'), מומחה אוסטרי לדרום-ערבית, טען כי במילה חבש השתמשה לראשונה המלכה חתשפסות בשנת 1460 לפני הספירה ביחס לארץ פונטו.[דרוש מקור] נוסע אחר מהמפרץ הערבי הוא אל חרני. ב-1295 הוא מתאר את אימפריית חבש שבה אחת הערים הגדולות והידועות ביותר נקראת כברה, שהיא העיירה המלכותית על חוף הים האדום. הוא כותב ש"כברה היא מרכז מסחרי המהווה את נמל הים שממנו חבשה חצה את הים...".
היסטוריה

אקסום הממוקמת בצפונה של אתיופיה ובאריתריאה, חלשה על סחר עשיר בין האוקיינוס ההודי לים התיכון. אקסום מוזכרת בספר "השיוט בים האריתריאי", מהמאה הראשונה לספירה, כמקום חשוב לסחר של שנהב:
על פי שיוט בים האריתריאי (פריפלוס - קובץ הוראות שיוט), שליטה של אקסום היה זוסקלאס, ששלט מאקסום על שתי ערי נמל חשובות: אדוליס (ליד מאסאווה של היום) וארסינוי (אסאב של היום). בספר מוזכר שבממלכה הייתה ספרות יוונית ענפה:
במאה ה-3, אקסום החלה להתערב בעניינים הפנימים של ממלכות בדרום חצי האי ערב, ושלטה לסירוגין באזור תיהמה במערב ערב הסעודית של היום ובאזורים אחרים.
בסוף המאה ה-3 אקסום החלה להטביע מטבעות משלה ונזכרה, על ידי הנביא הפרסי מאני(אנ'), כאחת מארבע המעצמות של התקופה, לצד פרס, רומא וסין. הממלכה קיבלה את הנצרות בין השנים 325–328 תחת שלטונו של הקיסר אזנה והייתה המדינה הראשונה שהשתמשה בצלב על מטבעותיה. בשיאה שלטה אתיופיה על אזור נרחב הכולל את צפון אתיופיה, אריתריאה, צפון סודאן, דרום מצרים, ג'יבוטי, תימן ודרום ערב הסעודית. שטחה הסתכם בכ-1.25 מיליון קמ"ר
אתיופיה הייתה בעלת בריתה של האימפריה הביזנטית כנגד האימפריה הפרסית ושקעה מסיבות בלתי ברורות, שאת חלקן ניתן לייחס להתפשטות האסלאם, התמעטות הסחר באזורה ומיתון בשוקי אלכסנדריה, ביזנטיון ודרום אירופה.
אחרי תקופת זוהר שנייה בתחילת המאה ה-6, החלה הממלכה לשקוע שוב, והתמוטטה סופית לאחר פלישת כוחות יהודית המלכה במאה ה-10.
מקור

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

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

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

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

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

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

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

Stuart Munro-Hay, Aksum: An African Civilization of Late Antiquity, Edinburgh University Press, Edinburgh, 1991. ISBN 0-7486-0106-6
הערות שוליים

↑  אנציקלופדיה אתיופיקה: ד-ח, עמוד 948
↑  "ציוויליזציה אפריקאית של שלהי העת העתיקה": סטיוארט מונרו-היי, 1991. p. 90
↑  פריפלוס הים האריתראי, עמוד 4.
↑  פריפלוס הים האריתראי, עמוד 5.
↑  East-West Orientation of Historical Empires, פיטר טארצ'ין, ג'ונתן מ. אדמס, וטומס ד. מסדרון. נובמבר 2004.
1 2  Stuart Munro-Hay, Aksum: An African Civilization of Late Antiquity. Edinburgh: University Press, 1991, p. 57.
↑  אנציקלופדיה אתיופיקה בערך געז, עמוד 732.
↑  "הפוליתאיזם בקיסרות הרומית ומחוץ לגבולותיה בשלהי העת העתיקה," בתוך: אלי קדם: הפוליתיאיזם בארץ ישראל ושכנותיה מן האלף השני לפסה"נ ועד התקופה המוסלמית, עורכים מנחם קיסטר, יוסף גייגר, נדב נאמן, שאול שקד (ירושלים: יד יצחק בן-צבי, 2008), עמ' 185-241
↑  ג'יימס ברוס, מסעות לגילוי מקור הנילוס כרך ראשון, עמ' 485
↑  דברי לאפסו דלבו באתר חבשה
↑  שלוה וייל, כינויים קולקטיביים וזהות קולקטיבית של יהודי אתיופיה, בתוך 'יהודי אתיופיה באור הזרקורים' בעריכת שלוה וייל, האוניברסיטה העברית בירושלים, יולי 1997 ISSN 0792-2329
1 2  יעקב מלקמו, סולומון מברטו, זיוה מקונן, שושנה סמואל, אורלי אוסדון, רחמים מלקו, מורשת יהדות אתיופיה - קהילת "ביתא ישראל" באתיופיה ובישראל, המינהל לחינוך התיישבותי ועליית הנוער במשרד החינוך, 2002
| היסטוריה של אתיופיה |
| --- | --- | --- |
| התקופה הקדומה | פרהיסטוריה • שבא • סבא • ממלכת דעמת • קיסרות אקסום | כנסיית ביתה גיורגיס, לליבלה |
| ימי הביניים | תקופת החושך • תקופת תור הזהב • תקופת השפל • תקופת התחייה • תקופת השופטים | כנסיית ביתה גיורגיס, לליבלה |
| אתיופיה המודרנית | תקופת הגיבוש • תקופת הכיבוש • תקופת השחרור | כנסיית ביתה גיורגיס, לליבלה |
| סוציאליזם | מלחמת האזרחים • החונטה הצבאית • הרפובליקה העממית | כנסיית ביתה גיורגיס, לליבלה |
| כיום | ממשלת המעבר • הפדרציה האתיופית | כנסיית ביתה גיורגיס, לליבלה |
| 0 | 1 | 2 |
| --- | --- | --- |
| הקודם: פרוטו-אקסום | היסטוריה של אתיופיה  המאה ה-1 לפנה"ס - המאה ה-10 | הבא: תקופת החושך |
| --- | --- |
בקרת זהויות :  NLI: 987007494124405171  GND: 4357441-5  LCCN: n99038042  LNB: 000297450  VIAF: 132712036   WorldCat (עם VIAF): 132712036 
אקסום הייתה ממלכה חשובה בסחר הבינלאומי מהמאה ה-1 (המפה על פי הספר השיוט בים האריתראי) עד אשר ירדה מגדולתה בגלל עליית הסחר הערבי והתפשטות האסלאם.
מטבעות עם דיוקנו של המלך אינדוביס במטבע שמשמאל רשום ביוונית "ΑΞΩΜΙΤΩ BICIΔΑΧΥ" (לא ברור. משמעות המילה הראשונה היא "של אקסום"). במטבע שמימין רשום ביוונית "ΕΝΔΥΒΙC ΒΑCΙΛΕΥC", "המלך אינדוביס".
אקסום ודרום ערב לקראת סוף מלכותו של גאדרט במאה השלישית.
אדריכלות אקסומית טיפוסית, מנזר בדברה דמו
טבלת גיבוב

במדעי המחשב, טבלת גִּבּוּב או טבלת ערבול (באנגלית: Hash table), היא מבנה נתונים מילוני, אשר נותן גישה לרשומה באמצעות המפתח המתאים לה. המבנה הזה עובד באמצעות הפיכת המפתח על ידי פונקציית הגיבוב, למספר המייצג מיקום במערך שמפנה אל הרשומה המבוקשת. הפעולה העיקרית שבה היא תומכת ביעילות היא אחזור המידע מתוך מבנה הנתונים: בהינתן מפתח נתון (למשל שם של אדם), מצא את הרשומה המתאימה (למשל מספר הטלפון של אותו אדם).
הרעיון לטבלת הגיבוב הופיע כבר ב-1953 במזכר פנימי בחברת IBM שפורסם על ידי ה.פ. לון (H. P. Luhn) ובמקביל פותחה על ידי ג'ין אמדל (Gene Amdahl), ה.מ בוהם (E. M. Boehme), נתניאל רוצ'סטר (Nathaniel Rochester) וארתור סמואל (Arthur Samuel) תוכנית שמשתמשת בגיבוב. כאשר למדען המחשב הרוסי אנדריי ארשוב (Andrey Ershov), היה את אותו רעיון כמו לאמדל.
מבנה טבלת הגיבוב

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

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

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

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

כדי לחפש ערך בטבלה משתמשים בפונקציית הגיבוב שמקבלת כמשתנה את המפתח של הרשומה המבוקשת כאשר המטרה היא שהערך שהפונקציה מחזירה יוביל אותנו אל הרשומה.
כאשר מדובר על טבלה פתוחה, פעולת החיפוש צריכה לטפל בבעיית ההתנגשות. כלומר, המפתח הוביל אותנו אל רשומה שלא מתאימה אליו. בעיה זו נפתרת לרוב על ידי משתנה נוסף שהפונקציה מקבלת והוא מקבל ערך חדש עבור כל התנגשות נוספת בחיפוש הנוכחי. פונקציית הגיבוב מתייחסת אל המשתנה הזה כאשר היא מחזירה את הערך ותחזיר ערך חדש אחרי כל התנגשות. החיפוש נגמר כאשר מצאנו את הרשומה המתאימה או כשמגיעים לתא שלא הפנה לשום ערך. בשימוש בשיטה הזאת יכולה להתקיים בעיה כאשר מוחקים מהטבלה את אחת הרשומות שהיא גם אחת מההתנגשויות בחיפוש אחר רשומה נוספת. בפעולת החיפוש נקבל את הרושם שהגענו לתא שלא הפנה לשום רשומה ולכן נפסיק את החיפוש. הפתרון לבעיה הוא באמצעות משתנה שישמור עבור כל תא בטבלה אם הוא הפנה אל רשומה ובזמן החיפוש נבדוק באמצעות המשתנה אם התא "אוכלס" בעבר.
עבור פונקציית גיבוב טובה, סיבוכיות הזמן תהיה תלויה במספר ההתנגשויות בזמן חיפוש ערך ותהיה גבוהה יותר ככל שמספר הרשומות בטבלה, מתקרב לגודל המערך (מסומן "B<<n" כאשר B - גודל המערך, n - מספר הרשומות בפועל במערך). הסיבוכיות תהיה תלויה גם בכמות הרשומות שהוכנסו לטבלה אפילו אם הן כבר לא נמצאות בה כיוון שהרבה תאים יסומנו כתאים ש"אוכלסו". כאשר כמות הרשומות אינה גבוהה, מספר ההתנגשויות צפוי להיות בודד ולכן סיבוכיות החיפוש תהיה במקרה הממוצע  \ O(1). במקרה הגרוע של הרבה התנגשויות הסיבוכיות תהיה  \ O(n).
בטבלה סגורה בעיית ההתנגשות נפתרת על ידי מבנה נתונים נוסף שאליו התא בטבלה מפנה. החיפוש נעשה על ידי שימוש בפונקציית הגיבוב שמחזירה אינדקס במערך ולאחר מכן בפונקציית החיפוש של מבנה הנתונים שאליו מפנה האינדקס.
עבור פונקציית גיבוב טובה, כאשר כמות הרשומות באותו סדר גודל של מספר התאים במערך (מסומן "B~n"), סיבוכיות החיפוש תהיה במקרה הממוצע  \ O(1) כיוון שבכל מבנה נתונים יהיה בממוצע מספר בודד של רשומות. במקרה הגרוע, הסיבוכיות תהיה כמו הסיבוכיות במקרה הגרוע של מבנה הנתונים בו משתמשים.
פעולת הכנסה

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

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

עבור טבלה סגורה, ניתן להשתמש במבנה הנתונים רשימה מקושרת ואף על פי שבמקרה הגרוע, היעילות תהיה  \ O(n) עבור כל אחת משלוש הפעולות, קלות התפיסה של פעולת הרשימות המקושרות והתכנות שלהם, יכולים לפצות על כך. ניתן להשתמש גם בעץ חיפוש מאוזן כמו עץ AVL ועץ B+ שיקטינו את החיפוש במקרה הגרוע ל  \ O(\log n). במערכות זמן אמת בהם זמן ביצוע פעולה הוא קריטי גם במקרה הגרוע, בחירה במבני נתונים אלו יכולה לשפר את ביצועי המערכת.
בטבלה הפתוחה קיימות מספר שיטות לפתירת בעיית ההתנגשות:
בדיקה ליניארית (אנ') - עבור כל התנגשות נבדוק סדרתית האם האינדקס הבא במערך פנוי. שיטה זו קלה לחישוב ולהבנה ושומרת על מקומיות בזיכרון דבר שחוסך גישה לדיסק הקשיח אך יכולה ליצור בעיה של הצטברות רשומות בסדרת אינדקסים ובעקבות כך יהיה מספר גדול של התנגשויות עבור הרשומות באותם באינדקסים. ההצטברות תתהווה משום שעבור כל ניסיון הכנסה של רשומה לצביר רשומות, ההצטברות תגדל בעוד אחד וכך גם מספר האינדקסים שיגדילו את הצביר יגדל באחד.
בדיקה ריבועית (אנ') - עבור כל התנגשות נבדק מקום מתאים אחר תוך שימוש בהעלאה בריבוע של מספר ההתנגשויות שהיו עד כה עבור אותו מפתח. הפונקציה עבור הבדיקה הריבועית היא:  h(k,i)=(h(k)+c_{1}i+c_{2}i^{2})\mod m כאשר:  h - פונקציית הגיבוב,  k - המפתח המבוקש,  i - מספר ההתנגשויות,  m - מספר התאים בטבלה ו- c_{1},c_{2} - מספרים קבועים. בשיטה זו אמנם תיתכן הצטברות שתבוא לידי ביטוי בסדרות של תאים מאוכלסים שמתחילות מ- h(k) וממשיכות בתאים שבאופן רצוף האינדקס עבורם הוא  h(k,i) והם מאוכלסים. ההצטברות מתהווה משום שכל המפתחות שמחזירים  h(k) תמיד ינותבו אל אותה סדרת תאים. ההצטברות עבור הבדיקה הריבועית פחות משמעותית מההצטברות המתרחשת עבור הבדיקה הליניארית, אך הבדיקה הריבועית שומרת על מקומיות בזיכרון ברמה פחותה.
גיבוב כפול (אנ') - בגיבוב כפול משתמשים בפונקציית גיבוב נוספת כדי לטפל במקרה של התנגשות. הנוסחה עבור גיבוב כפול היא:  h(k,i)=(h_{1}(k)+i\cdot h_{2}(k))\mod m כאשר  k - המפתח המבוקש,  h_{1},h_{2} - פונקציות גיבוב,  i - מספר ההתנגשויות ו- m - מספר התאים בטבלה. ההצטברות בגיבוב כפול מתרחשת רק עבור מפתחות שבאופן נדיר שתי הפונקציות מחזירות עבורם את אותו הערך, ובכך עדיפה על הבדיקה הריבועית אבל לא נשמרת המקומיות בכלל.
שימושים לטבלאות גיבוב

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

פונקציית גיבוב
גיבוב קוקייה
הערות שוליים

↑  Hans Peter Luhn and the Birth of the Hashing Algorithm - IEEE Spectrum, spectrum.ieee.org (באנגלית)
| מבני נתונים |
| --- | --- | --- |
| מבנים מופשטים | רשימה • מחסנית • קבוצה • מולטי קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות |  |
| מימושים ליניאריים | מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ |  |
| גרפים ועצים | ערימה  (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש  (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R‏ • Trie • X-fast trie • טריי y מהיר• עץ WAVL |  |
| הסתברותיים | מסנן בלום |  |
| --- | --- |
בקרת זהויות :  GND: 1046573225
ציר זמן של המהפכה התעשייתית השנייה

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

ב-1826 הפטנט הראשון למנוע בעירה פנימית ניתן בארצות הברית לסמואל מורי.
ב-1859 המציא הצרפתי אטיין לנואר את מנוע הבעירה פנימית הראשון בעל ערך שימושי שמתבסס על גז פחמי.
ב-1879 המציא ניקולאוס אוטו את המנוע הארבע-פעימות הראשון.
ב-1881 רשם המהנדס דוגלד קלארק (Dugald Clerk) פטנט על מנוע שתי פעימות.
ב-1885 מנוע הבנזין הראשון, שפעל עם קרבורטור, נבנה על ידי גוטליב דיימלר.
ב-1886 יצא הדגם "Benz Patent-Motorwagen " לשוק, כלי הרכב הראשון שפועל בעזרת מנוע בעירה פנימי.
ב-1892 רודולף דיזל המציא מנוע פעימה פנימית שפועל על בנזין ונקרא על שמו "מנוע דיזל".
ב-1898 בנתה חברת דויץ הגרמנית את המנוע הראשון בעל הזרקת בנזין, אך הוא הותאם להנעת כלי רכב רק כחמישים שנה מאוחר יותר.
ב-1897 מנוע הדיזל הופעל לראשונה.
ב-1904 רשם פטנט אלפרד סקוט (Yorkshireman Alfred Angas Scott) על מנוע הרכב בעל מנוע 2 הפעימות שפיתח, שב-1908 יוצא לשוק.
ב-1908 יצא הדגם הפופולרי פורד מודל T שהצליח בזכות מחירו שנועד להיות כ"מחיר שמתאים לכל פועל".
ב-1910 יצא הדגם "Cyclecar"(המכונית המשולשת) הפופולרי בבריטניה,שנקראה כך כיוון שנסעה על 3 גלגלים (2 אחוריים ואחד קדמי) והצליחה בזכות המחיר הזול שלה לאותה תקופה.
טלגרף

ב-1833 תכננו קרל פרידריך גאוס ווילהלם אדוארד ובר את הטלגרף האלקטרומגנטי הראשון שמקשר בין מצפה הכוכבים אל מכון הפיזיקה בתוך אוניברסיטת גטינגן.
ב-1838 בנה סמואל מורס את הטלגרף האלקטרומגנטי היישומי הראשון, שאפשר לשדר מסרים למרחקים ארוכים באמצעות כבל באיכות פשוטה ואיתו את קוד מורס.
ב-1844 ב-24 במאי המברק הטלגרפי הראשון נשלח על ידי סמואל מורס מוושינגטון לבולטימור, ובו נכתב: "What hath God wrought!"(מתוך הפסוק "כִּי לֹא נַחַשׁ בְּיַעֲקֹב וְלֹא קֶסֶם בְּיִשְׂרָאֵל. כָּעֵת יֵאָמֵר לְיַעֲקֹב וּלְיִשְׂרָאֵל: מַה פָּעַל אֵל", ספר במדבר, פרק כ"ג, פסוק כ"ג).
פלדה

ב-1856 רשם הנרי בסמר פטנט על תהליך ייצור הפלדה ההמוני שהוא יצר הנקרא גם על שמו: "תהליך בסמר".
ב-1859 קמה החברה הבריטית "Barrow Hematite Steel " שמייצרת באמצעות תהליך בסמר פסי רכבת עשוים מפלדה.
ב-1874 נבנה גשר הפלדה הראשון בעולם "Eads Bridge" בידי חברת "Keystone Bridge Company" שבשליטת אנדרו קרנגי.
ב-1902 נבנה גורד השחקים הראשון בעולם בעזרת מסגרת פלדה ששימשה כשלד, לאחר שתוכנן על יד ויליאם לה ברון ג'ני בשם "בניין הום אינשורנס" בעיר שיקגו.