Map是Java中的一種鍵值對（Key-Value）數(shù)據(jù)結構，它提供了高效的鍵值對的存儲和訪問。在Java中，常見的Map實現(xiàn)類有HashMap、LinkedHashMap和TreeMap等。這些實現(xiàn)類在底層使用不同的數(shù)據(jù)結構來存儲鍵值對，以提供不同的性能和特性。
讓我們看看官方介紹Map吧（采用機翻）
Map是將鍵映射到值的對象。map不能包含重復的鍵; 每個鍵最多只能映射到一個值。這個接口取代了Dictionary類，Dictionary類是一個完全抽象的類，而不是接口。
Map接口提供了三個集合視圖，它們允許將映射的內容視為一組鍵、一組值或一組鍵-值映射。映射的順序定義為映射集合視圖上的迭代器返回其元素的順序。一些類似實現(xiàn)，比如TreeMap類，對它們的順序做出了特定的保證;其他類，如HashMap類，則不需要。
注意:如果使用可變對象作為映射鍵，必須非常小心。如果對象的值以影響相等比較的方式更改，而該對象是映射中的鍵，則不指定映射的行為。這種禁止的一個特殊情況是，不允許map將自身包含為鍵。雖然允許映射將自身包含為一個值，但建議非常小心。
equals和hashCode方法不再在這樣的映射上得到很好的定義。
所有通用的map實現(xiàn)類都應該提供兩個“標準”構造函數(shù):
- 創(chuàng)建空映射的void(無參數(shù))構造函數(shù)，
- 具有單個map類型參數(shù)的構造函數(shù)，它創(chuàng)建具有與其參數(shù)相同的鍵值映射的新映射。
實際上，后一種構造函數(shù)允許用戶復制任何映射，生成所需類的等效映射。沒有辦法強制執(zhí)行這個建議(因為接口不能包含構造函數(shù))，但是JDK中的所有通用映射實現(xiàn)都遵循這個建議。該接口中包含的“破壞性”方法，即修改其操作的映射的方法，被指定為在該映射不支持該操作時拋出UnsupportedOperationException。如果是這種情況，如果調用對映射沒有影響，這些方法可能(但不是必需)拋出UnsupportedOperationException。
例如，在不可修改的映射上調用putAll(Map)方法，如果要“疊加”其映射的映射為空，則可能(但不是必需的)拋出異常。一些映射實現(xiàn)對它們可能包含的鍵和值有限制。例如，有些實現(xiàn)禁止空鍵和空值，有些實現(xiàn)對其鍵的類型有限制。嘗試插入不符合條件的鍵或值將引發(fā)未檢查異常，通常為NullPointerException或ClassCastException。試圖查詢是否存在不符合條件的鍵或值可能會拋出異常，或者簡單地返回false;有些實現(xiàn)將展示前一種行為，有些將展示后一種行為。更一般地說，嘗試對不符合條件的鍵或值進行操作，其完成后不會導致在映射中插入不符合條件的元素，可能會拋出異常，也可能成功，這取決于實現(xiàn)的選擇。這種異常在該接口的規(guī)范中被標記為“可選的”。
Collections Framework接口中的許多方法都是根據(jù)equals方法定義的。例如，containsKey(Object key)方法的規(guī)范說:“當且僅當此映射包含鍵k的映射使得(key==null ?)K ==null: key.equals(K))。”此規(guī)范不應被解釋為暗示調用Map。帶有非空參數(shù)key的containsKey將導致對任何鍵k調用key.equals(k)。實現(xiàn)可以自由地實現(xiàn)優(yōu)化，從而避免equals調用，例如，首先比較兩個鍵的哈希碼。(Object.hashCode()規(guī)范保證兩個哈希碼不相等的對象不能相等。)更一般地說，只要實現(xiàn)者認為合適，各種集合框架接口的實現(xiàn)可以自由地利用底層對象方法的指定行為。一些執(zhí)行遞歸遍歷map的map操作可能會失敗，對于map直接或間接包含自身的自引用實例可能會出現(xiàn)異常。這包括clone()、equals()、hashCode()和toString()方法。實現(xiàn)可以選擇性地處理自引用場景，但是大多數(shù)當前實現(xiàn)都不這樣做。
Map的特點
- 鍵唯一性：Map中的鍵是唯一的，每個鍵只能對應一個值。
- 無序性：Map中的鍵值對是無序的，插入順序不會影響鍵值對的存儲和訪問順序。
- 鍵和值的映射關系：每個鍵都與一個值相關聯(lián)，通過鍵可以獲取對應的值。
- 允許空鍵和空值：Map允許使用null作為鍵和值。
- 可變性：Map是可變的數(shù)據(jù)結構，可以動態(tài)地添加、修改和刪除鍵值對。
Map的實現(xiàn)方式
- HashMap使用哈希表（Hash Table）實現(xiàn)，通過哈希函數(shù)將鍵映射到數(shù)組索引，以實現(xiàn)快速的插入、查找和刪除操作。它提供了O(1)的平均時間復雜度。
- LinkedHashMap在HashMap的基礎上，使用雙向鏈表維護插入順序，以保持鍵值對的迭代順序。
- TreeMap使用紅黑樹（Red-Black Tree）實現(xiàn)，以保持鍵的有序性。它提供了O(log n)的時間復雜度。
Map的缺點
- 性能開銷：相比于數(shù)組或列表，Map的性能開銷較大。由于需要維護鍵的唯一性和映射關系，以及可能的哈希沖突等，Map的操作通常比較耗時。
- 內存占用：Map需要維護額外的數(shù)據(jù)結構來存儲鍵值對的映射關系，這會占用一定的內存空間。
- 無序性：雖然Map提供了鍵值對的存儲和訪問，但是它們是無序的。如果需要有序性，可能需要使用其他數(shù)據(jù)結構。
示例：
將Map對象轉換為List對象
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
public class MapToListExample {
public static void main(String[] args) {
// 創(chuàng)建一個Map對象
Map<String, Integer> map = Map.of("A", 1, "B", 2, "C", 3);
// 將Map對象轉換為List對象
List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
// 打印轉換后的List對象
for (Map.Entry<String, Integer> entry : list) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
}
}
將HashMap的鍵值對結構轉換為數(shù)組對象結構
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class HashMapToArrayExample {
public static void main(String[] args) {
// 創(chuàng)建一個HashMap對象
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("A", 1);
hashMap.put("B", 2);
hashMap.put("C", 3);
// 將HashMap的鍵值對結構轉換為數(shù)組對象結構
List<MyObject> array = new ArrayList<>();
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
MyObject obj = new MyObject(entry.getKey(), entry.getValue());
array.add(obj);
}
// 打印轉換后的數(shù)組對象
for (MyObject obj : array) {
System.out.println(obj.getKey() + " : " + obj.getValue());
}
}
}
class MyObject {
private String key;
private Integer value;
public MyObject(String key, Integer value) {
this.key = key;
this.value = value;
}
public String getKey() {
return key;
}
public Integer getValue() {
return value;
}
}
實現(xiàn)一個簡易版本的紅黑樹
package com.xh.Map;
/**
* @author HWZ
* @date 2024年03月07日 11:01
* @description
*/
public class RedBlackTree<K extends Comparable<K>, V> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root;
private class Node {
private K key;
private V value;
private Node left, right;
private boolean color;
public Node(K key, V value) {
this.key = key;
this.value = value;
this.color = RED;
}
}
/**
* 向紅黑樹中插入鍵值對
* @param key 鍵
* @param value 值
*/
public void put(K key, V value) {
root = put(root, key, value);
root.color = BLACK;
}
private Node put(Node node, K key, V value) {
if (node == null) {
return new Node(key, value);
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node.left = put(node.left, key, value);
} else if (cmp > 0) {
node.right = put(node.right, key, value);
} else {
node.value = value;
}
if (isRed(node.right) && !isRed(node.left)) {
node = rotateLeft(node);
}
if (isRed(node.left) && isRed(node.left.left)) {
node = rotateRight(node);
}
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}
return node;
}
/**
* 刪除紅黑樹中指定鍵的節(jié)點
* @param key 鍵
*/
public void delete(K key) {
if (!contains(key)) {
return;
}
if (!isRed(root.left) && !isRed(root.right)) {
root.color = RED;
}
root = delete(root, key);
if (root != null) {
root.color = BLACK;
}
}
private Node delete(Node node, K key) {
if (key.compareTo(node.key) < 0) {
if (!isRed(node.left) && !isRed(node.left.left)) {
node = moveRedLeft(node);
}
node.left = delete(node.left, key);
} else {
if (isRed(node.left)) {
node = rotateRight(node);
}
if (key.compareTo(node.key) == 0 && (node.right == null)) {
return null;
}
if (!isRed(node.right) && !isRed(node.right.left)) {
node = moveRedRight(node);
}
if (key.compareTo(node.key) == 0) {
Node min = findMin(node.right);
node.key = min.key;
node.value = min.value;
node.right = deleteMin(node.right);
} else {
node.right = delete(node.right, key);
}
}
return balance(node);
}
private Node deleteMin(Node node) {
if (node.left == null) {
return null;
}
if (!isRed(node.left) && !isRed(node.left.left)) {
node = moveRedLeft(node);
}
node.left = deleteMin(node.left);
return balance(node);
}
/**
* 判斷紅黑樹中是否包含指定鍵
* @param key 鍵
* @return 是否包含指定鍵
*/
public boolean contains(K key) {
return get(key) != null;
}
/**
* 根據(jù)鍵查找紅黑樹中的值
* @param key 鍵
* @return 值
*/
public V get(K key) {
Node node = root;
while (node != null) {
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node = node.left;
} else if (cmp > 0) {
node = node.right;
} else {
return node.value;
}
}
return null;
}
/**
* 更新紅黑樹中指定鍵的值
* @param key 鍵
* @param value 值
*/
public void update(K key, V value) {
if (contains(key)) {
put(key, value);
}
}
private boolean isRed(Node node) {
if (node == null) {
return false;
}
return node.color == RED;
}
private Node rotateLeft(Node node) {
if (node == null || node.right == null) {
return node;
}
Node x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
private Node rotateRight(Node node) {
Node x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
private void flipColors(Node node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
private Node moveRedLeft(Node node) {
flipColors(node);
if (isRed(node.right.left)) {
node.right = rotateRight(node.right);
node = rotateLeft(node);
flipColors(node);
}
return node;
}
private Node moveRedRight(Node node) {
flipColors(node);
if (isRed(node.left.left)) {
node = rotateRight(node);
flipColors(node);
}
return node;
}
private Node balance(Node node) {
if (isRed(node)) {
node = rotateLeft(node);
}
if (isRed(node.left) && isRed(node.left.left)) {
node = rotateRight(node);
}
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}
return node;
}
private Node findMin(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
}
這個簡易版本的紅黑樹實現(xiàn)包括了插入、刪除、查找和修改操作。紅黑樹的節(jié)點使用內部類Node表示，包含了鍵、值、左子節(jié)點、右子節(jié)點和顏色屬性。
插入操作使用遞歸實現(xiàn)，并根據(jù)紅黑樹的性質進行旋轉和顏色翻轉來保持樹的平衡性。刪除操作也使用遞歸實現(xiàn)，并根據(jù)不同情況進行旋轉和顏色翻轉來保持樹的平衡性。
查找操作根據(jù)鍵的比較逐級向下搜索，直到找到匹配的鍵或搜索到葉子節(jié)點為止。修改操作先判斷是否包含指定的鍵，如果包含則調用插入操作來更新鍵對應的值。文章來源：http://www.zghlxwxcb.cn/news/detail-839277.html
注意，這只是一個簡易版本的紅黑樹實現(xiàn)，并沒有考慮到所有的邊界情況和優(yōu)化。在實際應用中，我們更加建議使用Java標準庫中的TreeMap來實現(xiàn)紅黑樹，它提供了更完善和高效的實現(xiàn)。文章來源地址http://www.zghlxwxcb.cn/news/detail-839277.html
上述紅黑樹代碼的測試：
public class RedBlackTreeTest {
public static void main(String[] args) {
RedBlackTree<Integer, String> tree = new RedBlackTree<>();
// 插入操作
tree.put(5, "Value 5");
tree.put(2, "Value 2");
tree.put(8, "Value 8");
tree.put(1, "Value 1");
tree.put(4, "Value 4");
tree.put(7, "Value 7");
tree.put(9, "Value 9");
// 查找操作
System.out.println(tree.get(4)); // 輸出: Value 4
System.out.println(tree.get(10)); // 輸出: null
// 修改操作
tree.update(4, "New Value 4");
System.out.println(tree.get(4)); // 輸出: New Value 4
// 刪除操作
tree.delete(2);
System.out.println(tree.contains(2)); // 輸出: false
}
}
到了這里，關于Java的 Map以及實現(xiàn)一個簡單的紅黑樹的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
