Класът Java Hashtable е един от най-старите членове на Java Collection Framework. Това е реализация на структура от данни на математическа хеш table. В Java hashtable вътрешно съдържа кофи, където се съхраняват двойките ключ/стойност. Hashtable е доста подобен на HashMap . Най-съществената разлика между тях: Hashtable се синхронизира, докато HashMap не.
Hashtable като структура от данни
Hashtable е структура от данни, където данните се съхраняват във формат на масив. Всяка стойност на данните има уникална ключова стойност. Ако ключът е известен, достъпът до необходимите данни е много бърз. Така че операциите по вмъкване и търсене са бързи независимо от размера на данните. Хеш tableта се състои от масив за съхраняване на данни и хеширане за генериране на индекс, където трябва да се намира даден елемент. Какво е хеширане? Това е правило, което преобразува обекта в набор от знаци (code). Обикновено този вид функция преобразува голяма част от данни в малка целочислена стойност. Хеш функциите могат да бъдат различни, но всички те предават определени свойства:
Конкретен обект има конкретен хеш code.
Два еднакви обекта имат еднакви хеш codeове. Обратното не е вярно.
Ако два хеш codeа са различни, обектите определено не са еднакви.
Различни обекти могат да имат един и същ хеш code. Това много рядко събитие се нарича сблъсък. Добрата хеш функция минимизира вероятността от сблъсъци.
Резултатът от прилагането на хеш функция към обект извиква hashCode .
Хеш table в Java
Класът Hashtable е реализация на структура от данни на хеш table. Тази колекция е създадена по-рано от Java Collection Framework, но по-късно е включена в нея. Както всички „ранни“ колекции (от Java 1.0), хеш-tableта е синхронизирана (почти всички методи са маркирани като синхронизирани). Поради този фактор hashtable има значителни проблеми с производителността. Следователно, като се започне от Java 1.2, в повечето случаи се препоръчва използването на други реализации на интерфейса Map поради липсата им на синхронизация. Обикновено HashMap е най-подходящият заместител. Така че клас Hashtable<K,V>се състои от ключове и стойности. Той съхранява ключовете на принципа на хеширането. Двойките ключ-стойност се съхраняват в "кофи". Кофите заедно изграждат „маса“, вид вътрешен масив. Hashtable използва хеш codeа на ключа, за да определи кофа, където двойката ключ/стойност трябва да се картографира. Хеш функцията позволява да се получи местоположението на кофата от хеш codeа на Key. Тази функция връща цяло число за обект. Както казахме по-горе, два равни обекта имат един и същ хешcode, докато два неравни обекта може да не винаги имат различни хешcodeове. Различни обекти, поставени в хеш-table, може да имат един и същ хеш-code. За разрешаване на този проблем (сблъсък) се използва масив от списъци в хеш-tableта. Двойките, съпоставени към една кофа, се съхраняват в списък и тази препратка към списък се съхранява в индекс на масив.
Хеширани Java конструктори
Hashtable() , конструкторът по подразбиране. Създава празна хеш-table. (Първоначален капацитет по подразбиране = 11, коефициент на натоварване = 0,75).
Hashtable(int size) създава хеш-table с определен размер.
Hashtable(int size, float fillRatio) създава хеш table с определен размер и съотношение на запълване.
Hashtable(Map m) създава хеш-table със същите съпоставяния като дадената карта.
Декларация на хеш-table
Класът 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<>();
Как да импортирате хеш table в Java
Java Hashtable е в пакета java.util . Затова използвайте import java.util.Hashtable; във вашия code. Обикновено ще получите съвет от вашата IDE за това.
Основни операции за хеширане
Основните операции на Hashtable са получаване, вмъкване в колекцията и премахване от там. Ето тези три операции са:
Object get(Object key) връща стойността на обекта, който е посочил ключ. Връща null, ако не бъде намерен такъв ключ.
Object put(Object key, Object value) съпоставя указания ключ към посочената стойност. Нито ключът, нито стойността могат да бъдат нула.
Object remove(Object key) премахва записа (ключ и съответната стойност) от хеш-tableта.
Други важни операции:
int size() връща количеството записи в хеш-tableта.
boolean съдържа (стойност на обект) проверява дали определената стойност е в хеш-tableта. Ако е така, методът връща true, else връща false.
boolean containsValue(Object value) проверява дали указаната стойност е в хеш-tableта. Ако е така, методът връща true, else връща false.
void clear() премахва всички записи от хеш-tableта.
boolean containsKey(Object key) връща true, ако посоченият ключ съществува в хеш-tableта, в противен случай връща false.
boolean isEmpty() връща true, ако хеш-tableта е празна or false, ако съдържа поне един ключ.
void rehash() увеличава размера на хеш-tableта и повторно хешира всички нейни ключове.
Реализация на хеш table, Java code:
Нека създадем ученически клас:
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 в хеш-table, след което премахнем някои и проверим някои параметри.
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 да се използва като стойност or ключ. HashMap позволява един нулев ключ и множество нулеви стойности.
Hashtable наследява класа Dictionary, докато HashMap наследява класа AbstractMap.
HashMap се преминава от Iterator. Hashtable може да се обхожда не само от Iterator, но и от Enumerator.
Пример за хеш-table на Java (Hashtable срещу HashMap нулев ключ)
Ето code на фрагмент за демонстрация на нула, използвана като ключ и стойност в 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 в реални проекти, но е лесно да срещнете тази структура от данни в стари проекти. Както и да е, важно е да разберете Howви структури от данни има Java и How работят, поне за вашите интервюта. Обикновено обектите HashMap се използват instead of Hashtable поради тяхната прorка. HashMap е по-ефективен (не е синхронизиран) и може да има null като ключ.
GO TO FULL VERSION