Java Hashtable

מחלקה Java Hashtable היא אחד החברים הוותיקים ביותר של Java Collection Framework. זהו יישום של מבנה נתוני טבלת Hash מתמטי. ב-Java hashable מכיל באופן פנימי דליים שבהם מאוחסנים צמדי המפתח/ערך. Hashtable די דומה ל- HashMap . ההבדל המשמעותי ביותר ביניהם: Hashtable מסונכרן ואילו HashMap לא.

Hashtable כמבנה נתונים

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

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

התוצאה של החלת פונקציית Hash על אובייקט קוראת ל-hashCode .

Hashtable ב-Java

מחלקה Hashable היא יישום של מבנה נתונים של טבלת Hash. אוסף זה נוצר מוקדם יותר מ-Java Collection Framework, אך נכלל בו מאוחר יותר. כמו כל האוספים ה"מוקדמים" (מ-Java 1.0), טבל hashable מסונכרן (כמעט כל השיטות מסומנות כמסונכרנות). בגלל גורם זה, ל-hashtable יש בעיות ביצועים משמעותיות. לפיכך, החל מ-Java 1.2, ברוב המקרים מומלץ להשתמש במימושים אחרים של ממשק Map עקב חוסר הסנכרון שלהם. בדרך כלל HashMap הוא התחליף המתאים ביותר. אז Class Hashtable<K,V> מורכב ממפתחות וערכים. הוא מאחסן מפתחות על עיקרון הגיבוב. צמדי מפתח-ערך מאוחסנים ב"דליים". הדליים יחד בונים "שולחן", מעין מערך פנימי. Hashtable משתמש בקוד ה-hash של המפתח כדי לקבוע דלי שבו זוג המפתח/ערך צריך למפות. פונקציית Hash מאפשרת לקבל את מיקום הדלי מה-hashcode של Key. פונקציה זו מחזירה מספר שלם עבור אובייקט. כפי שאמרנו לעיל לשני אובייקטים שווים יש קוד hashcode זהה, בעוד שלשני אובייקטים לא שווים ייתכן שלא תמיד יהיו קודים שונים. אובייקטים שונים, המוכנסים ל-Hashtable עשויים להיות בעלי אותו קוד Hash. כדי לפתור בעיה זו (התנגשות) נעשה שימוש במערך רשימות ב-hashtable. הזוגות הממופים לדלי בודד מאוחסנים ברשימה והפניה לרשימה זו מאוחסנת באינדקס מערך.

Hashtable Java Constructors

• Hashtable() , בנאי ברירת המחדל. זה יוצר hashtable ריק. (קיבולת התחלתית ברירת מחדל = 11, מקדם עומס = 0.75).
• Hashtable (גודל int) בונה טבל hashable בגודל שצוין.
• Hashtable (גודל int, float fillRatio) יוצר טבלת גיבוב בגודל ויחס מילוי שצוינו.
• Hashtable(Map m) יוצר טבל hashable עם אותם מיפויים כמו המפה הנתונה.

הצהרת Hashtable

מחלקת ה- Hashtable Java מיישמת ממשקים של Map , Cloneable ו- Serializable . זה מרחיב את שיעור המילון .

Hashtable.java
public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

K הוא סוג המפתחות המתוחזק על ידי המפה. V הוא סוג הערכים הממופים. דוגמא:

Hashtable<Student, Integer> myHTable = new Hashtable<>();

כיצד לייבא ג'אווה hashable

Java Hashtable נמצא בתוך חבילת java.util . אז השתמש ב-import java.util.Hashtable; בקוד שלך. בדרך כלל תקבל רמז מה-IDE שלך לגבי זה.

פעולות עיקריות Hashable

הפעולות העיקריות של ה-Hashtable הן קבלת, הכנסה לאוסף והסרה משם. הנה שלושת הפעולות האלה:

• Object get(Object key) מחזירה את הערך של האובייקט שצוין מפתח. מחזירה null אם לא נמצא מפתח כזה.
• Object put(Object key, Object value) ממפה את המפתח שצוין לערך שצוין. לא המפתח ולא הערך יכולים להיות null.
Object remove(Object key) מסיר את הערך (המפתח והערך המתאים) מ-hashtable.

שאר הפעולות החשובות:

• int size() מחזירה את כמות הערכים בטבלת ה-hash.
• boolean contains(Object value) בודק אם הערך שצוין נמצא בטבלת ה-hash. אם כן, השיטה מחזירה true, אחרת מחזירה false.
• boolean containsValue(Object value) בודק אם הערך שצוין נמצא בטבלת ה-hash. אם כן, השיטה מחזירה true, אחרת מחזירה false.
• void clear() מסיר את כל הערכים מה-hashtable.
• boolean containsKey(Object key) מחזירה true אם המפתח שצוין קיים בטבלת ה-hash, אחרת תחזיר false.
• boolean isEmpty() מחזירה true אם הטבלת hashable ריקה או false אם היא מכילה מפתח אחד לפחות.
• void rehash() מגדיל את גודל ה-hashtable ומחזיר את כל המפתחות שלו.

הטמעת טבלת Hash, קוד Java:

בואו ניצור כיתת סטודנטים :

import java.util.Date;
public class Student {
   String surname;
   String name;
   String secondName;
   Long birthday; // Long instead of long is used by Gson/Jackson json parsers and various orm databases

   public Student(String surname, String name, String secondName, Date birthday ){
       this.surname = surname;
       this.name = name;
       this.secondName = secondName;
       this.birthday = birthday == null ? 0 : birthday.getTime();
   }

   @Override
   public int hashCode(){
       //TODO: check for nulls
       return (surname + name + secondName + birthday).hashCode();
   }
   @Override
   public boolean equals(Object other_) {
       Student other = (Student)other_;
       return (surname == null || surname.equals(other.surname) )
               && (name == null || name.equals(other.name))
               && (secondName == null || secondName.equals(other.secondName))
               && (birthday == null || birthday.equals(other.birthday));
   }
}

הנה דוגמה של Java Hashtable . בוא נכניס שני אובייקטים של הכיתה Student לתוך hashable, ואז נסיר חלק ונבדוק כמה פרמטרים.

public class HashTableExample {
   public static void main(String[] args) {

       Hashtable<Student, Integer> myHTable = new Hashtable<>();
       Student sarah1 = new Student("Sarah","Connor", "Jane", null);
       Student john = new Student("John","Connor", "Kyle", new Date(1985, 02-1, 28)); // date not exists
       myHTable.put(john,1);
       myHTable.put(sarah1,0);
       System.out.println(myHTable.get(john));
       System.out.println(myHTable.isEmpty());
       System.out.println(myHTable.size());
       System.out.println(myHTable.contains(1));
       myHTable.remove(john);
       System.out.println(myHTable.contains(0));
       System.out.println(myHTable.contains(1));
       System.out.println(myHTable.containsKey(sarah1));
   }
}

התוצאה של הפעלת התוכנית היא:

1
false
2
true
true
false
true

HashMap לעומת Hashtable

• Hashtable דומה ל-HashMap ב-Java. ההבדל המשמעותי ביותר הוא שה-Hashtable מסונכרן ואילו HashMap לא. לכן, Hashtable איטי יותר מ- HashMap בגלל סנכרון.
• למעט בעיית סנכרון, Hashtable אינו מאפשר שימוש ב-null כערך או מפתח. HashMap מאפשר מפתח null אחד וערכי null מרובים.
• Hashtable יורש את המחלקה Dictionary בעוד HashMap יורש את המחלקה AbstractMap.
• HashMap עוברת על ידי Iterator. ניתן לעבור את Hashtable לא רק על ידי Iterator אלא גם על ידי Enumerator.

דוגמה של Java hashtable (Hashtable לעומת HashMap key null)

הנה קוד פרגמנט להדגמת null המשמש כמפתח וערך ב- HashMap וב- Hashtable

// Null key Java hashtable example and hashmap example

try{
      System.out.println("Hashtable");
      Hashtable hashTable = new Hashtable();
      hashTable.put(null, new Object());
    }catch(Exception ex){
      ex.printStackTrace();
    }
    System.out.println("HashMap");
    HashMap hashMap = new HashMap();
    hashMap.put(null, new Object());
    System.out.println("as you see no exceptions with null key in HashMap");
  }

התוצאה של הפעלת התוכנית המכילה את הפרגמנט הזה:

java.lang.NullPointerException
	at java.base/java.util.Hashtable.put(Hashtable.java:480)
	at Character.main(Character.java:58)
HashMap
as you see no exceptions with null key in HashMap

סיכום

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