معرفی Map
هر Map یک مجموعه از کلید (Key) و مقدار (Value) است که با استفاده از کلید میتونیم مقدار رو برگردونیم؛ کلید در Map نمیتونه تکراری باشه اما مقدار میتونه تکراری باشه؛ به Map دیکشنری (Dictionary) هم گفته میشه.
بررسی کلاس Entry
هر Key و Value در Map داخل کلاسی به نام Entry نگهداری میشه و هر Map مجموعه ای از Entry هاست؛ در زیر متد های کلاس Entry به صورت UML شرح داده شده است.
| java.util.Map.Entry<K, V> | |
|---|---|
| getKey(): K | key رو بر میگردونه. |
| getValue(): V | value رو بر میگردونه. |
| setValue(v: V): void | value رو مقداردهی میکنه. |
در تصویر زیر سلسله مراتب ارثبری کلاس های Map شرح داده شده است.
بررسی اینترفیس Map
کلاس های Map در جاوا اینترفیس Map رو پیادهسازی میکنن و متد های مشترک بین تمام پیادهسازی های Map در اینترفیس Map قرار داره؛ در نمودار UML زیر متد های تعریف شده در Map شرح داده شده است.
| Interface | |
|---|---|
| <<java.util.Map<K, V>>> | |
| +put(key: K, value: V) | جفت Key و Value رو به صورت Entry به Map اضافه میکنه. |
| +putAll(map: Map<? extends K, ? extends V> | تمام Entry های map رو به Map فعلی اضافه می کنه. |
| +containsKey(key: Object): boolean | اگه Key در Map وجود داشته باشه مقدار true رو بر میگردونه. |
| +containsValue(value: Object): boolean | اگه یک یا چند کلید به مقدار value نگاشت شده باشه مقدار true رو بر میگردونه. |
| +entrySet(): Set<Entry<K, V>> | یک Set از Entry های موجود در Map رو بر میگردونه. |
| +get(key: Object): V | value مرتبط با Key رو بر میگردونه. |
| +isEmpty(): boolean | اگه Map خالی باشه مقدار true رو بر میگردونه. |
| +keySet(): Set<K> | یک Set از کلید های موجود در Map رو بر میگردونه. |
| +remove(key: Object): V | entry مربوط به Key مورد نظر رو حذف می کنه و value رو بر میگردونه. |
| +size() | تعداد entry های داخل Map رو بر میگردونه. |
| +values(): Collection<V> | تمام value های موجود در Map رو به صورت Collection بر میگردونه. |
| +forEach(action: Consumer<? super K, ? super V> | به پیمایش در entry های Map می پردازه. |
| +clear(): void | تمام Entry ها رو از Map حذف میکنه. |
سه کلاس HashMap, LinkedHashMap و TreeMap از پیادهسازی های Map هستن؛ کلاس HashMap و LinkedHashMap در با جاوا با هش کد پیاده سازی شدن و کلاس TreeMap با red-black tree.
بررسی هش کد (hash code)
به طور کلی کلاس های *Hash* با هش کد (hash code) پیاده سازی شدن، هر کلاسی در جاوا یک کد اختصاصی داره که با تابع hashCode ایجاد میشه؛ زمانی که دو عنصر با equals باهم برابر باشن و هش کد های یکسانی داشته باشن میگیم دو عنصر باهم یکسان هستن.
محل قرار گرفتن Key در HashMap ها با hashCode مشخص میشه و زمانی که جایگاه Key پیدا بشه باهاش میتونیم Value رو برگردونیم.
استفاده از HashMap
عناصر در HashMap به ترتیب و بر اساس هش کد هاشون قرار میگیرن، زمانی که بخوایم جفت Key, Value رو به یک HashMap اضافه کنیم، محل قرار گرفتن این جفت در HashMap بر اساس هش کد های Key مشخص میشه و به صورت Entry داخل Map قرار میگیرن؛ سپس با همین هش کد میتونیم محل قرار گرفتن Entry رو پیدا کنیم و Value رو صدا بزنیم.
در نمودار UML زیر کانستراکتور (سازنده) های کلاس HashMap شرح داده شده است.
| java.util.HashMap | |
|---|---|
| +HashMap() | یک نمونه از HashMap با loadFactor پیشفرض 0.75 ایجاد میکنه. |
| +HashMap(capacity: int, loadFactor: float) | یک نمونه از HashMap با ظرفیت (capacity) و loadFactor از پیش تعیین شده ایجاد میکنه. |
| +HashMap(map: Map<? extends K, ? extends V>) | یک نمونه از HashMap ایجاد میکنه و عناصر موجود در map رو بهش اضافه می کنه. |
به تعداد Entry هایی که Map میتونه داخل خودش نگهداری کنه ظرفیت (capacity) میگن، زمانی که ظرفیت Map پر بشه به صورت خودکار افزایش پیدا میکنه و امکان اضافه شدن Entry های جدید به Map فراهم میشه.
با loadFactor آستانه ی افزایش ظرفیت Map رو مشخص میکنیم مثلا اگه ظرفیت Map برابر با 16 باشه و loadFactor برابر با 0.5 باشه، زمانی که تعداد Entry های موجود در Map به 8 برسه ظرفیت به صورت خودکار افزایش پیدا میکنه.
در مثال زیر یک نمونه از استفاده از HashMap اورده شده است، میخوایم چندتا اسم رو به صورت key و سن رو به صورت value در HashMap ذخیره کنیم.
Map<String, Integer> map = new HashMap<>();
map.put("Rick", 52);
map.put("Carl", 32);
map.put("Rosita", 38);
map.put("Henry", 32);
map.put("Maggie", 33);
map.put("Negan", 45);
System.out.println("Display entries in map: ");
System.out.println(map + "\n");
System.out.println("Is Bijan in list?" + map.containsKey("Bijan"));
System.out.println("Do we have 32 yo person? " + map.containsValue(32));
System.out.println("List of names in map: ");
System.out.println(map.keySet());
System.out.println("List of Ages in map: ");
System.out.println(map.values() + "\n");
استفاده از LinkedHashMap
در پیادهسازی LinkedHashMap از LinkedList استفاده شده، Entry ها به ترتیبی که اضافه میشن در Map قرار میگیرن، زمانی که ترتیب قرار گرفتن Entry ها مهم باشه یا بخوایم یک Entry رو در اول یا آخر Map حذف یا اضافه کنیم از LinkedHashMap استفاده می کنیم.
در نمودار UML زیر کانستراکتور (سازنده) های کلاس LinkedHashMap شرح داده شده است.
| java.util.LinkedHashMap | |
|---|---|
| +LinkedHashMap() | یک نمونه از LinkedHashMap با loadFactor پیشفرض 0.75 ایجاد میکنه. |
| +LinkedHashMap(capacity: int, loadFactor: float, accessOrder: boolean) | یک نمونه از LinkedHashMap با ظرفیت (capacity) و loadFactor از پیش تعیین شده ایجاد میکنه و زمانی که accessOrder برابر با true باشه، هر Entry که با get صدا میزنیم میره انتهای Map. |
| +LinkedHashMap(map: Map<? extends K, ? extends V>) | یک نمونه از LinkedHashMap ایجاد میکنه و عناصر موجود در map رو بهش اضافه می کنه. |
| +putFirst(key: K, value: V): V | یک Entry از Key و Value به ابتدای Map اضافه می کنه؛ اگه Entry از پیش وجود داشته باشه میارش ابتدای صف و مقدار Value قبلی رو با Value جدید جایگزین میکنه و Value قبلی رو بر میگردونه. |
| +putLast(key: K, value: V): V | یک Entry از Key و Value به انتهای Map اضافه می کنه؛ اگه Entry از پیش وجود داشته باشه میارش انتهای Map و مقدار Value قبلی رو با Value جدید جایگزین میکنه و Value قبلی رو بر میگردونه. |
| +firstEntry(): Entry<K, V> | اولین Entry موجود در Map رو بر میگردونه. |
| +lastEntry(): Entry<K, V> | آخرین Entry موجود در Map رو بر میگردونه. |
| +pollFirstEntry(): Entry<K, V> | اولین Entry موجود در Map رو حذف میکنه و بر میگردونه، اگه Map خالی باشه مقدار null رو بر میگردونه. |
| +pollLastEntry(): Entry<K, V> | آخرین Entry موجود در Map رو حذف میکنه بر میگردونه و اگه Map خالی باشه مقدار null رو بر میگردونه. |
در مثال زیر میخوایم اسم و سن رو به صورت Key و Value در LinkedHashMap ذخیره کنیم.
LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("Rick", 52);
linkedHashMap.put("Carl", 32);
linkedHashMap.put("Rosita", 38);
linkedHashMap.put("Henry", 32);
linkedHashMap.put("Maggie", 33);
linkedHashMap.put("Negan", 45);
linkedHashMap.forEach((name, age) -> System.out.println("name: " + name + " age: " + age));
System.out.println();
System.out.println("Updating map by changing Maggie's age and re ordering it as first entry: ");
int oldAge = linkedHashMap.putFirst("Maggie", 27);
System.out.println("old age of Maggie: " + oldAge);
System.out.println();
linkedHashMap.forEach((name, age) -> System.out.println("name: " + name + " age: " + age));
در مثال زیر میخوایم اسم و سن رو به صورت Key و Value در LinkedHashMap با accessOrder ذخیره کنیم.
LinkedHashMap<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.5f, true);
System.out.println("Access order enabled...\n");
accessOrderMap.put("Rick", 52);
accessOrderMap.put("Carl", 32);
accessOrderMap.put("Rosita", 38);
accessOrderMap.put("Henry", 32);
accessOrderMap.put("Maggie", 33);
accessOrderMap.put("Negan", 45);
System.out.println("Rosita's age is " + accessOrderMap.get("Rosita"));
System.out.println("Maggie's age is " + accessOrderMap.get("Maggie"));
System.out.println();
accessOrderMap.forEach((name, age) -> System.out.println("name: " + name + " age: " + age));
System.out.println();
System.out.println("Updating map by changing Maggie's age and re ordering it as first entry: ");
System.out.println();
accessOrderMap.putFirst("Maggie", 27);
accessOrderMap.forEach((name, age) -> System.out.println("name: " + name + " age: " + age));
در مثال بالا زمانی که سن Rosita و Maggie با get صدا زده میشه، Entry هاشون میره به انتهای Map.
استفاده از TreeMap
کلاس TreeMap در جاوا با Red-Black Tree پیادهسازی شده و ترتیب قرار گرفتن Entry ها در TreeMap بر اساس مقایسه ای است که با Comparable یا Comparator بین Entry ها انجام میشه؛ در TreeMap زمانی دو Key باهم یکسان هستند که مقدار 0 توسط Comparable یا Comparator برگردونده بشه.
در نمودار UML زیر کانستراکتور (سازنده) های TreeMap با ویژگی هاشون شرح داده شده است.
| java.util.TreeMap | |
|---|---|
| +TreeMap() | یک نمونه از TreeMap ایجاد میکنه. |
| +TreeMap(comparator: Comparator<? super K> | یک نمونه از TreeMap ایجاد می کنه و Entry ها رو به ترتیب مقایسه Key هاشون که با Comparator میشن در TreeMap قرار میده. |
| +TreeMap(map: Map<? extends K, ? extends V>) | یک نمونه از TreeMap ایجاد می کنه و Entry های موجود در map رو بهش اضافه می کنه. |
اینترفیس SortedMap
یکی از پیادهسازی های TreeMap اینترفیس SortedMap است؛ در نمودار UML زیر متد های SortedMap با توضیحاتشون آورده شده است.
| Interface | |
|---|---|
| java.util.SortedMap | |
| +firstEntry(): Entry<K, V> | اولین Entry در TreeMap رو بر میگردونه. |
| +lastEntry(): Entry<K, V> | آخرین Entry در TreeMap رو بر میگردونه. |
| +firstKey(): K | اولین Key موجود در TreeMap رو بر میگردونه. |
| +lastKey(): K | آخرین Key موجود در TreeMap رو بر میگردونه. |
| +comparator<? extends K> | comparator استفاده شده در مرتب کردن key ها رو بر میگردونه و اگه از Comparator استفاده نشده باشه مقدار null رو بر میگردونه. |
| +headMap(untilKey: K): SortedMap<K, V> | یک SortedMap جدید از Key های قبل از untilKey بر میگردونه. |
| +tailMap(fromKey: K): SortedMap<K, V> | یک SortedMap جدید از Key های fromKey به بعد بر میگردونه. |
| توجه: متد های firstEntry و lastEntry از jdk21 به بعد اضافه شدن و در اینترفیس SequencedMap تعریف شدن که SortedMap یک ساب اینترفیس از SequencedMap است، SequencedMap یک پیادهسازی مشترک بین TreeMap و LinkedHashMap است که برای خلاصه تر شدن از بررسیش خودداری کردم. | |
در مثال زیر میخوایم یک TreeMap ایجاد کنیم و Key ها رو به ترتیب طولشون داخل TreeMap قرار بدیم.
System.out.println("Putting Name and Ages using TreeMap and comparing them by length...\n");
SortedMap<String , Integer> sortedMap = new TreeMap<>(Comparator.comparingInt(String::length));
sortedMap.put("Rick", 52);
sortedMap.put("Carl", 32);
sortedMap.put("Rosita", 38);
sortedMap.put("Henry", 32);
sortedMap.put("Maggie", 33);
sortedMap.put("Negan", 45);
System.out.println(sortedMap);
System.out.println("Names before Henry: " + sortedMap.headMap("Henry"));
System.out.println("Names after Henry: " + sortedMap.tailMap("Henry"));
بعد از اجرای مثال بالا بعضی از اسامی به TreeMap اضافه نمیشن و بخاطر اینه که اسامی به عنوان Key در نظر گرفته شدن و مقایسشون بر اساس طول String است و چون بعضی از Key ها طول یکسانی دارن بنابراین به TreeMap اضافه نمیشن و تنها Value اولین Key اضافه شده تغییر می کنه.
اینترفیس NavigableMap
یکی دیگه از پیادهسازی ها در TreeMap اینترفیس NavigableMap است؛ اینترفیس NavigableMap یک ساب اینترفیس از SortedMap است و علاوه بر متد های گفته شده در SortedMap متد های اختصاصی خودشو هم داره.
در نمودار UML زیر متد های تعریف شده در اینترفیس NavigableMap به همراه توضیحاتشون شرح داده شده است.
| Interface | |
|---|---|
| java.util.NavigableMap | |
| +lowerKey(k: K): K | بزرگترین کلید در TreeMap که کوچکتر از k باشه رو بر میگردونه. |
| +lowerEntry(k: K): Map.Entry<K, V> | Entry بزرگترین کلید در TreeMap که کوچکتر از K باشه رو بر میگردونه. |
| +higherKey(k: K): K | کوچکترین کلید در TreeMap که بزرگتر از k باشه رو بر میگردونه. |
| +higherEntry(k: K): Map.Entry<K, V> | Entry کوچکترین کلید در TreeMap که بزرگتر از k باشه رو بر میگردونه. |
| +floorKey(k: K): K | بزرگترین کلید در TreeMap که کوچکتر یا مساوی k باشه رو بر میگردونه. |
| +floorEntry(k: K): Map.Entry<K, V> | Entry مربوط به بزرگترین کلید در TreeMap که کوچکتر یا مساوی k باشه رو بر میگردونه. |
| +ceilingKey(k: K): K | کوچکترین کلید در TreeMap که بزرگتر یا مساوی k باشه رو بر میگردونه. |
| +ceilingEntry(k: K): Map.Entry<K, V> | Entry مربوط به کوچکترین کلید در TreeMap که بزرگتر یا مساوی k باشه رو بر میگردونه. |
| +descendingMap(): NavigableMap<K, V> | ترتیب قرار گرفتن Entry ها رو معکوس میکنه و یک نمونه از NavigableMap با ترتیب جدید بر میگردونه. |
| +descendingSet(): NavigableSet<K> | ترتیب قرار گرفتن کلید ها در NavigableMap رو معکوس میکنه و یک نمونه از NavigableSet از کلید ها رو با ترتیب جدید بر میگردونه. |
در مثال زیر میخوایم اسم و سن ها رو بدون استفاده از Comparator به TreeMap اضافه کنیم و سپس از متد های گفته شده در NavigableMap استفاده کنیم.
System.out.println("Using TreeMap in natural order...");
NavigableMap<String, Integer> navigableMap = new TreeMap<>(map);
System.out.println(navigableMap);
System.out.println("lowerEntry(\"R\"): " + navigableMap.lowerEntry("R"));
System.out.println("higherEntry(\"R\"): " + navigableMap.higherEntry("R"));
System.out.println("floorEntry(\"R\"): " + navigableMap.floorEntry("R"));
System.out.println("ceilingEntry(\"R\"): " + navigableMap.ceilingEntry("R"));
System.out.println(navigableMap.descendingMap());
System.out.println(navigableMap.descendingKeySet());
پیچیدگی زمان (Time Complexity)
در جدول زیر پیچیدگی زمان افزودن و صدا زدن Entry ها در حالت amortized در HashMap, LinkedHashMap, TreeMap شرح داده شده است.
| put | get | |
|---|---|---|
| HashMap | O(1) | O(1) |
| LinkedHashMap | O(1) | O(1) |
| TreeMap | O(logn) | O(logn) |
توجه
پیچیدگی زمان برای TreeMap در بدترین حالت (worst case) نیز O(logn) است در صورتی که برای HashMap LinkedHashMap برابر با O(n) است.
مورد مطالعه (مثال) ها
در مثال زیر میخوایم دفعات تکرار کلمات در یک String رو با Map بررسی کنیم.
public class CountOccurrencesOfWords {
public static void main(String[] args) {
String text = "Good morning. Have a good class. " +
"Have a good visit. Have fun!";
Map<String, Integer> map = new HashMap<>();
String[] words = text.split("[\\s+\\p{P}]");
for (String word : words) {
String key = word.toLowerCase();
if (!key.isBlank()) {
if (map.get(key) == null)
map.put(key, 1);
else map.put(key, (map.get(key) + 1));
}
}
System.out.printf("%-10s %10s\n", "Word", "Number of Occurrences");
for (int i = 0; i < 40; i++)
System.out.print("-");
System.out.println();
map.forEach((word, occurrences) -> System.out.printf("%-10s %10d\n", word, occurrences));
}
}
در مثال زیر برنامه دفعات تکرار کلیدواژه های جاوا در یک فایل جاوا رو بررسی میکنه و نمایش میده، اگه کلیدواژه در فایل وجود نداشته باشه نمایش نمیده.
public class CountOccurrencesOfKeywords {
public static void main(String[] args) throws IOException {
Map<String, Integer> map = prepareKeywordsMap();
Scanner input = new Scanner(System.in);
System.out.println("Enter java file path: ");
String path = input.nextLine();
File file = new File(path);
if (!file.getName().matches(".+\\.java")){
System.out.println("You should choose a java file");
System.exit(0);
}
Scanner readFile = new Scanner(file);
while (readFile.hasNext()){
String line = readFile.nextLine();
String[] words = line.split("\\s");
for (String word : words) {
if (map.containsKey(word)) {
int count = map.get(word);
map.put(word, ++count);
}
}
}
readFile.close();
System.out.printf("%-10s %22s\n", "Keyword", "Number of Occurrences");
for (int i = 0; i < 35; i++)
System.out.print("-");
System.out.println();
map.forEach((keyword, occurrences) ->{
if (occurrences != 0){
System.out.printf("%-10s %10d\n", keyword, occurrences);
}
});
}
private static Map<String, Integer> prepareKeywordsMap(){
String[] keywordString = {"abstract", "assert", "boolean",
"break", "byte", "case", "catch", "char", "class", "const",
"continue", "default", "do", "double", "else", "enum",
"extends", "for", "final", "finally", "float", "goto",
"if", "implements", "import", "instanceof", "int",
"interface", "long", "native", "new", "package", "private",
"protected", "public", "return", "short", "static",
"strictfp", "super", "switch", "synchronized", "this",
"throw", "throws", "transient", "try", "void", "volatile",
"while", "true", "false", "null"};
Map<String, Integer> map = new HashMap<>();
for (String keyword : keywordString){
map.put(keyword, 0);
}
return map;
}
}
خلاصه
- هر Map در جاوا دارای کلید و مقدار است و برای دسترسی به مقدار از کلید استفاده میکنیم.
- جفت کلید و مقدار به صورت Entry در Map نگهداری میشن.
- تمام پیادهسازی های Map در جاوا اینترفیس Map رو پیادهسازی میکنن.
- Entry ها در HashMap به ترتیب هش کد هاشون نگهداری میشن.
- Entry ها در LinkedHashMap به ترتیبی که اضافه میشن نگهداری میشن و اگه فلگ accessOrder برابر با true باشه بر اساس دسترسی که با get به مقدار داریم نگهداری میشن.
- Entry ها در TreeMap به ترتیب مقایسه ای که با Comparable یا Comparator میشن، نگهداری میشن.
- پیچیدگی زمان افزودن و صدا زدن Entry در HashMap و LinkedHashMap در حالت amortized برابر با O(1) است و در TreeMap برابر با O(logn) است.
بازخورد و دیدگاه ها
اولین نفری باشید که در این صفحه نظر میدهید