Интерфейсът на Java Map е част от рамката на Java Collection, но не е подтип на интерфейса на Collection. Така че се държи по различен начин в сравнение, да речем, със списъци or други обекти на колекцията. Всеки елемент на Map<Key, Value> представлява двойка ключ-стойност. И ключът, и стойността са някои обекти. Всички ключове в дадена карта са уникални, докато стойностите не са, така че могат да бъдат дублирани. Може да мислите за Map в Java като за вид речник or каталог на онлайн магазин, където можете да намерите всеки елемент, използвайки неговия уникален индекс. Ключът е уникален идентификатор на стойността в карта. Например в Map<String, Item> String е ID на няHowъв артикул от онлайн магазина. Според documentацията Map има следните подинтерфейси:
Подвързии ;
ConcurrentMap<K,V> ;
ConcurrentNavigableMap<K,V> ;
Логически контекст на съобщението ;
Контекст на съобщението ;
NavigableMap<K,V> ;
SOAPMessageContext ;
Сортирана карта<K,V> .
И изпълнява класове:
Абстрактна карта
Атрибути
AuthProvider
ConcurrentHashMap
ConcurrentSkipListMap
EnumMap
HashMap
Хеш table
IdentityHashMap
LinkedHashMap
PrinterStateReasons
Имоти
Доставчик
RenderingHints
SimpleBindings
TabularDataSupport
TreeMap
UI по подразбиране
WeakHashMap
Java AbstractMap е абстрактен клас, който имплементира по-голямата част от интерфейса Map.
Java HashMap е структура от данни за съхраняване на двойки ключ-стойност с помощта на хеш-table.
Java TreeMap е структура от данни за използване на дърво, т.е. дисплей със сортирани ключове.
WeakHashMap за използване на хеш table със слаби ключове, дисплей със стойности, които могат да бъдат изтрити от събирача на отпадъци, ако вече не се използват.
LinkedHashMap е карта с реда на добавяне на елементи, позволява итерация в реда на вмъкване.
EnumMap разширява класа AbstractMap за използване с ключове enum.
IdentityHashMap използва проверка на референтна еквивалентност при сравняване на documentи, съпоставяне с ключове, сравнени с помощта на
== операция instead of метод
equals()
Тук се интересуваме от най-популярните реализации на Map Interface: HashMap, TreeMap и LinkedHashMap. Между другото, редът на елементите на картата зависи от конкретни реализации. Да кажем, TreeMap и LinkedHashMap имат предвидим ред на елементите, докато HashMap не.
Методи за карта
Основните операции на всяка карта са вмъкване, премахване и търсене на елементи.
public Object put(Object key, Object value) вмъква елемент в картата.
public void putAll(Map map) вмъква указаната карта вътре в картата.
public Object remove(Object key) изтрива запис според посочения ключ.
public Object get(Object key) връща стойността за посочения ключ.
public boolean containsKey(Object key) търси посочения ключ от тази карта
public Set keySet() връща изглед Set, който съдържа всички ключове
public Set entrySet() връща изглед Set с всички ключове и стойности.
Какво е HashMap
Какво е HashMap? Това е най-популярната реализация на интерфейс Map<Key,Value>. Тази структура на данните се основава на принципа на хеширане.
Основният принцип на работа на HashMap: хеширане
За да разберете Howво е хеш карта и How работи, нека първо поговорим за хеширането и хеш функциите. Хеш функцията е просто функция в математически смисъл. Така че има няHowва входна стойност (обект, част от данни) и функцията я преобразува с помощта на подходящо правило в изходна стойност - хеш. Доста често хешът е шестнадесетично число с подходяща дължина. Правилата за процесите на конвертиране могат да бъдат различни, но те са предмет на следните принципи:
Конкретен вход (обект) има определен хеш code.
Ако два обекта са равни, техните хеш codeове също са равни. Обратното не е вярно.
Ако хеш codeовете са различни, обектите определено не са еднакви.
Понякога различни обекти могат да имат един и същ хеш code. Това е много малко вероятно събитие, наречено „сблъсък“ и хеш функция с добро качество трябва да минимизира вероятността от сблъсъци.
В Java всеки обект има хеш code. Изчислява се чрез метода hashCode на класа Object, родителски клас на всички Java обекти. Обикновено разработчиците отменят този метод за собствените си класове, Howто и свързаните с него методи.
HashMap: How работи
Така че класът HashMap<K,V>, тъй като всяка реализация на Map се състои от ключове и стойности. Той съхранява ключове, като използва принципите на хеширане. Вътре в HashMap двойките ключ-стойност се съхраняват в "кофи", тези кофи заедно изграждат "table", вътрешен масив от свързани списъци и нейният първоначален размер е 16. HashMap в Java използва хеш-codeа на ключа, за да определи кофа, където трябва да картографира двойката ключ/стойност: Сложната характеристика на HashMap е, че всяка клетка (кофа) на tableта [] съхранява не само една двойка, но няколко. Те не се съхраняват като явен обект (като LinkedList), а като имплицитна верига. Веригата се създава поради факта, че всяка двойка съхранява връзка към следващата двойка. Тоест всички двойки HashMap са разпръснати в 16 вериги. Когато поставите нов чифт в tableта, хешът на ключа се взема предвид. Този хеш не е функция за хеш code, вградена в ключовия обект. Счита се, че е в диапазона 0-15. Двойката се добавя към веригата от двойки, съхранени в кофата с хеш индекса. Този подход ни дава ускорение на търсенето. Докато търсите чифт по ключ, няма нужда да преминавате през цялата маса. Отчита се хешът на ключа и се проверява само веригата, която се съхранява в клетката с хеш индекса. Ако има твърде много двойки в HashMap, веригите стават твърде дълги. След това размерът на масива се увеличава, хешът на всички съхранени обекти се преизчислява и те се разпръскват по нови вериги.
HashMap декларация
Ако отидете до codeа на класа HashMap, ще намерите следващата декларация:
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable
Където K е типът на ключовете, поддържани от тази карта, а V - типът на картираните стойности. Това е пример за декларация на HashMap с ключ Integer и стойност на низ във вашия code:
HashMap<Integer, String> myHashMap = new HashMap<Integer, String>();
HashMap методи
Ето списъка с HashMap методи.
Object get(Object key) връща стойността за посочения ключ;
Object put(Key k, Value v) вмъква съпоставяне на ключови стойности в картата;
Премахване на обект (обектен ключ) премахва съпоставянето за посочения ключ от тази карта, ако присъства;
void clear() премахва всички двойки ключ-стойност от HashMap;
Object clone() връща плитко копие на този екземпляр на HashMap без клониране на ключовете и стойностите;
boolean containsKey(Object key) връща true, ако посоченият ключ е намерен в картата, false, ако не е;
boolean containsValue(Object Value) връща true, ако посоченият ключ е намерен в картата, false, ако не е;
boolean isEmpty() връща true, ако картата е празна, false, ако не е;
Set keySet() връща набора от ключове, извлечени от картата;
int size() връща количеството съпоставяне на ключ-стойност;
Collection values() връща колекция от стойности на картата;
Object remove(Object key) премахва двойката ключ-стойност за посочения ключ;
void putAll(Map m) копира всички елементи на картата в другата карта.
Пример за Java HashMap
Нека създадем програма с Java HashMap Пример, за да демонстрираме How работи:
import java.util.HashMap;
import java.util.Map;
import java.util.Iterator;
import java.util.Set;
public class HashMap {
public static void main(String[] args) {
{
// HashMap declaration
HashMap<Integer, String> myHashMap = new HashMap<Integer, String>();
//Adding elements into HashMap
myHashMap.put(7, "Johnny");
myHashMap.put(8, "Ivy");
myHashMap.put(1, "Rick");
myHashMap.put(4, "Stan");
myHashMap.put(3, "Kyle");
//print out the map content using Iterator
Set set = myHashMap.entrySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Map.Entry mapEntry = (Map.Entry) iterator.next();
System.out.print("key: " + mapEntry.getKey() + " value: ");
System.out.println(mapEntry.getValue());
}
System.out.println("get an element from myHashMap via key and print the value out:");
System.out.println(myHashMap.get(8));
//print out hashMap on standard way:
System.out.println(myHashMap);
// Get values based on key
String var = myHashMap.get(2);
//here we'll get null, we don't have such a key
System.out.println("Value with key 2: " + var);
var = myHashMap.get(7);
System.out.println("Value with key 7: " + var);
// Remove values based on key
myHashMap.remove(4);
System.out.println("myHashMap after removing element:");
System.out.println(myHashMap);
myHashMap.clear();
System.out.println("myHashMap after total clearing:");
System.out.println(myHashMap);
}
}
}
Резултатът от стартирането на програмата:
key: 1 value: Rick
key: 3 value: Kyle
key: 4 value: Stan
key: 7 value: Johnny
key: 8 value: Ivy
get an element from myHashMap via key and print the value out:
Ivy
{1=Rick, 3=Kyle, 4=Stan, 7=Johnny, 8=Ivy}
Value with key 2: null
Value with key 7: Johnny
myHashMap after removing element:
{1=Rick, 3=Kyle, 7=Johnny, 8=Ivy}
myHashMap after total clearing:
{}
TreeMap
TreeMap в Java също имплементира интерфейс Map<Key,Value>, но се основава на Червено-черна дървовидна структура от данни. Дървото се състои от „възли“ и линии, които свързват възли – клони". „Коренният" възел е в горната част на дървото. От корена може да има клонове и възли. Това е йерархична структура, може да се сетите тези възли като "деца" на корена. Дъщерният възел може да има свои собствени деца - по-ниски възли. Възлите без деца се наричат "крайни възли" or "листа". Двоичното дърво е дърво, където всеки възел има нула, едно , or две деца Двоичното дърво за търсене е структура, където всеки вътрешен възел съхранява ключ, а понякога и свързана стойност, и има две разграничени поддървета („ляво“ и „дясно“). Самобалансиращото се дърво за двоично търсене е базирано на възли дърво за двоично търсене, което автоматично запазва височината си (максималния брой нива под корена) малка в лицето на произволни вмъквания и изтривания на елементи. Червено-черно дърво е балансирано двоично дърво със свойствата:
Всеки възел е or червен, or черен
Коренът винаги е черен
Всеки лист е NIL (вид празен, нулев) възел и е черен
Ако даден възел е червен, децата му определено са черни.
Всеки прост път от възел до низходящ лист съдържа същия брой черни възли.
Характеристики на TreeMap
TreeMap използва дървовидна структура от данни, за да съхранява ключовете като възли и сортира ключовете с помощта на алгоритъма Red-Black Tree. И така, TreeMap поддържа записите си сортирани според естествения ред на ключовете си. За числа естественият е възходящ ред, за низове — азбучен ред. Можете да използвате компаратор, ако трябва да промените логиката на подреждане. Сортирането на обекти по естествен начин е голямо предимство на TreeMap, Howто и намирането на някои обекти с помощта на различни филтри и условия.
Методи на TreeMap
Object get(Object key) връща стойността на съответния ключ;
Object put(Object key, Object value) вмъква картографиране в карта;
Object remove(Object key) премахва съпоставянето за този ключ от, ако TreeMap го съдържа;
boolean containsKey(Object key) връща true, ако тази карта съдържа съпоставяне за посочения ключ;
boolean containsValue(Object value) връща true, ако TreeMap съпоставя един or повече ключове към посочената стойност;
Object firstKey() връща първия ключ в момента в сортираната карта;
Object lastKey() връща последния ключ в момента в сортираната карта;
void putAll(Map map) копира всички съпоставяния от указаната карта към картата;
Set entrySet() връща зададен изглед на съпоставянията
int size() връща количеството съпоставяния ключ-стойност
Collection values() връща колекция изглед на стойностите
Object clone() връща плитко копие на TreeMap
void clear() премахва всички съпоставяния от TreeMap
SortedMap headMap(Object key_value) връща изглед на частта от картата, по-малка от параметъра key_value
Set keySet() връща Set изглед на ключовете, съдържащи се в дървовидната карта
SortedMap subMap(K fromKey, K toKey) връща изглед на частта от тази карта, чиито ключове варират от fromKey, включително, до toKey, изключително
Object firstKey() връща първия ключ от TreeMap.
Пример за TreeMap
import java.util.TreeMap;
import java.util.Set;
import java.util.Iterator;
import java.util.Map;
public class TreeMapExample {
public static void main(String args[]) {
//TreeMap declaration
TreeMap<Integer, String> myTreeMap = new TreeMap<Integer, String>();
//put elements to TreeMap
myTreeMap.put(1, "Stuart");
myTreeMap.put(23, "Michael");
myTreeMap.put(7, "Johnny");
myTreeMap.put(5, "Ivy");
myTreeMap.put(2, "Alex");
//Display and print out myTreeMap using Iterator
Set set = myTreeMap.entrySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Map.Entry myEntry = (Map.Entry) iterator.next();
System.out.print("key: " + myEntry.getKey() + " value: ");
System.out.println(myEntry.getValue());
}
//TreeMap printed in classical way
System.out.println(myTreeMap);
//removing an element with the key =2
myTreeMap.remove(2);
//myTreeMap after removing:
System.out.println(myTreeMap);
}
}
Резултатът от стартирането на програмата:
key: 1 value: Stuart
key: 2 value: Alex
key: 5 value: Ivy
key: 7 value: Johnny
key: 23 value: Michael
{1=Stuart, 2=Alex, 5=Ivy, 7=Johnny, 23=Michael}
{1=Stuart, 5=Ivy, 7=Johnny, 23=Michael}
LinkedHashMap
LinkedHashMap е структура от данни, която съчетава свързани списъци и хеш карти. Наистина LinkedHashMap разширява класа HashMap и имплементира интерфейса Map, но Howво е това за свързаните списъци? Декларацията на LinkedHashMap:
Map <Integer, String> linkedHashMap = new LinkedHashMap <Integer, String>();
Тази нова linkedHashMap наследява свойства от HashMap (като table, loadFactor, threshold, size, entrySet), също така получава две специални свойства:
header е главата на двойно свързан списък. По време на инициализацията той се показва
accessOrder показва How да получите достъп до елементи с помощта на итератор. Ако е вярно, по реда на последния достъп. Ако е невярно, достъпът ще бъде в реда на вмъкване на елементите.
Този свързан списък определя реда на итерациите. Обикновено това е редът на вмъкване на ключове в картата.
Методи на LinkedHashMap
Object get(Object key) връща стойността, към която е съпоставен посоченият ключ, or нула, ако тази карта не съдържа съпоставяне за ключа
void clear() премахва всички съпоставяния от картата.
boolean containsKey(Object key) връща true, ако посоченият елемент е картографиран от един or повече ключове
boolean removeEldestEntry(Map.Entry eldest) връща true, ако картата премахне най-стария си запис от картата
Set<Map.Entry<K,V>> entrySet() връща Set изглед на съпоставянията, съдържащи се в тази карта
void forEach(BiConsumer<? super K,? super V> action) изпълнява даденото действие за всеки запис в тази карта, докато всички записи бъдат обработени or действието хвърли изключение.
Object getOrDefault(Object key, V defaultValue) връща стойността, към която е съпоставен посоченият ключ. Ако картата не съдържа съпоставяне за ключа, връща defaultValue.
Set<K> keySet() връща изглед Set на ключовете, съдържащи се в картата
boolean removeEldestEntry(Map.Entry<K,V> eldest) връща true, ако тази карта трябва да премахне най-стария си запис
void replaceAll(BiFunction<? super K,? super V,? extends V> function) замества всяка стойност на запис с резултата от извикване на дадена функция на този запис, докато всички записи бъдат обработени or функцията хвърли изключение.
Collection<v>values() връща изглед на колекция от стойностите, съдържащи се в картата
Пример за LinkedHashMap
import java.util.LinkedHashMap;
import java.util.Set;
import java.util.Iterator;
import java.util.Map;
public class HashLinkedListExample {
public static void main(String args[]) {
// LinkedHashMap Declaration
LinkedHashMap<Integer, String> myLinkedHashMap =
new LinkedHashMap<Integer, String>();
//Adding elements into LinkedHashMap
myLinkedHashMap.put(7, "Johnny");
myLinkedHashMap.put(12, "Rick");
myLinkedHashMap.put(1, "Kyle");
myLinkedHashMap.put(5, "Percy");
myLinkedHashMap.put(85, "Sebastian");
// Generate a Set of entries
Set set = myLinkedHashMap.entrySet();
// Display and print out the nodes of LinkedHashMap
Iterator iterator = set.iterator();
while(iterator.hasNext()) {
Map.Entry me = (Map.Entry)iterator.next();
System.out.print("key: "+ me.getKey() +
" value: "+me.getValue()+"\n");
}
//print out HashLinkedMap on standard way:
System.out.println(myLinkedHashMap);
myLinkedHashMap.put(21, "Ivy");
System.out.println(myLinkedHashMap);
myLinkedHashMap.remove(12);
System.out.println(myLinkedHashMap);
myLinkedHashMap.put(12, "Ronny");
System.out.println(myLinkedHashMap);
myLinkedHashMap.put(1, "Stan");
System.out.println(myLinkedHashMap);
}
}
Тук създаваме нова LinkedHashMap, добавяйки пет елемента, след което я отпечатваме с помощта на итератор и по класически начин. Както можете да видите, LinkedHashMap поддържа реда за вмъкване. След това изтриваме елемент от нашата карта, след това добавяме новия и по-късно - още един елемент с ключа, който вече е на картата. Той замества старата стойност, нанесена на този ключ. Резултатът от изпълнение на програмата:
HashMap, TreeMap и LinkedHashMap са реализациите на Map интерфейси. HashMap и LinkedHashMap са структури от данни, които хешират ключове. TreeMap използва естествения ред на своите ключове за организиране на дърво за търсене. Поръчка:
HashMap не поддържа ниHowъв ред.
TreeMap сортира записите във възходящ ред на ключовете.
LinkedHashMap поддържа реда на вмъкване.
Нулеви ключове:
HashMap и LinkedHashMap позволяват един нулев ключ.
LinkedHashMap не позволява нулеви ключове в случай, че ключовете използват естествен ред or Comparator не поддържа сравнение на нулеви leys.
Нека имаме пример за карта на Java, който включва всичките три реализации, разгледани в тази статия:
Както виждаме, редът на елементите в HashMap не е очевиден, в treeMap зависи от ключовете, в LinkedHashMap става въпрос за реда на вмъкване. Ако се опитаме да поставим нулев ключ в linkedHashMap, ще получим NullPointerException, но в linkedHashMap1, където ключовете са String, можем да го направим. Хеш картата е най-добрата реализация на карта с общо преднаmeaning. Той осигурява максимална скорост на търсене, бързо съхранение и операции за извличане, но трябва да запомните хаотичното му подреждане. Свързаната хеш карта наследява предимствата на HashMap и получава ред за ключовете. Той обаче съдържа linkedList, който е сравнително скъп по отношение на паметта. той е по-бавен от HashMap при търсене и малко по-бавен за добавяне/премахване поради поддържането на свързан списък. Дървовидната карта съхранява ключове, сортирани във възходящ ред. Въпреки това, За да затвърдите наученото, ви предлагаме да гледате видео урок от нашия курс по Java
GO TO FULL VERSION