[[388024]]

本文轉載自微信公眾號「貝塔學JAVA」，作者Silently9527。轉載本文請聯系貝塔學JAVA公眾號。

前言

JAVA中的Map主要就是將一個鍵和一個值聯系起來。雖然JAVA中已經提供了很多Map的實現，為了學習并掌握常用的數據結構，從本篇開始我將自己實現Map的功能，本篇主要是通過數組和鏈表兩種方式實現，之后提供二叉樹，紅黑樹，散列表的版本實現。通過自己手寫各個版本的Map實現，掌握每種數據結構的優缺點，可以在實際的工作中根據需要選擇適合的Map。

Map API的定義

在開始之前，我們需要先定義出Map的接口定義，后續的版本都會基于此接口實現

public interface Map<K, V> { 
    void put(K key, V value); 
 
    V get(K key); 
 
    void delete(K key); 
     
    int size(); 
 
    Iterable<K> keys(); 
 
    default boolean contains(K key) { 
        return get(key) != null; 
    } 
 
    default boolean isEmpty() { 
        return size() == 0; 
    } 
} 

這個接口是最簡單的一個Map定義，相信這些方法對于java程序員來說不會陌生;

基于鏈表實現Map

基于鏈表實現首先我們需要定義一個Node節點，表示我們需要存儲的key、vlaue

class Node { 
    K key; 
    V value; 
    Node next; 
 
    public Node(K key, V value, Node next) { 
        this.key = key; 
        this.value = value; 
        this.next = next; 
    } 
 
} 

get方法的實現思路是遍歷鏈表，然后比較每個Node中的key是否相等，如果相等就返回value，否則返回null

@Override 
public V get(K key) { 
    return searchNode(key).map(node -> node.value).orElse(null); 
} 
 
public Optional<Node> searchNode(K key) { 
    for (Node node = root; node != null; node = node.next) { 
        if (node.key.equals(key)) { 
            return Optional.of(node); 
        } 
    } 
    return Optional.empty(); 
} 

put方法的實現思路也是遍歷鏈表，然后比較每個Node的key值是否相等，如果相等那么覆蓋掉value，如果未查找到有key相等的node，那么就新建一個Node放到鏈表的開頭

@Override 
public void put(K key, V value) { 
    Optional<Node> optionalNode = searchNode(key); 
 
    if (optionalNode.isPresent()) { 
        optionalNode.get().value = value; 
        return; 
    } 
    this.root = new Node(key, value, root); 
} 

delete方法實現同樣也需要遍歷鏈表，因為我們的是單向鏈表，刪除某個節點有兩種思路，第一種，在遍歷鏈表的時候記錄下當前節點的上一個節點，把上一個節點的next指向當前節點next;第二種，當遍歷到需要刪除的節點時，把需要刪除節點的next的key、value完全復制到需要刪除的節點，把next指針指向next.next，比如：first - > A -> B -> C -> D -> E -> F -> G -> NULL,要刪除 C 節點，就把D節點完全復制到c中，然后C -> E，變相刪除了C

@Override 
public void delete(K key) { 
// 第一種實現： 
//        for (Node node = first, preNode = null; node != null; preNode = node, node = node.next) { 
//            if (node.key.equals(key)) { 
//                if (Objects.isNull(preNode)) { 
//                    first = first.next; 
//                } else { 
//                    preNode.next = node.next; 
//                } 
//            } 
//        } 
 
// 第二中實現: 
    for (Node node = first; node != null; node = node.next) { 
        if (node.key.equals(key)) { 
            Node next = node.next; 
            node.key = next.key; 
            node.value =next.value; 
            node.next = next.next; 
        } 
    } 
} 

分析上面基于鏈表實現的map，每次的put、get、delete都需要遍歷整個鏈表，非常的低效，無法處理大量的數據，時間復雜度為O(N)

”

基于數組實現Map

基于鏈表的實現非常低效，因為每次操作都需要遍歷鏈表，假如我們的數據是有序的，那么查找的時候我們可以使用二分查找法，那么get方法會加快很多

為了體現出我們的Map是有序的，我們需要重新定義一個有序的Map

public interface SortedMap<K extends Comparable<K>, V> extends Map<K, V> { 
    int rank(K key); 
} 

該定義要求key必須實現接口Comparable，rank方法如果key值存在就返回對應在數組中的下標，如果不存在就返回小于key鍵的數量

• 在基于數組的實現中，我們會定義兩個數組變量分部存放keys、values;
• rank方法的實現：由于我們整個數組都是有序的，我們可以二分查找法(可以查看《老哥是時候來復習下數據結構與算法了》)，如果存在就返回所在數組的下表，如果不存在就返回0

@Override 
public int rank(K key) { 
    int lo = 0, hi = size - 1; 
    while (lo <= hi) { 
        int mid = (hi - lo) / 2 + lo; 
        int compare = key.compareTo(keys[mid]); 
        if (compare > 0) { 
            lo = mid + 1; 
        } else if (compare < 0) { 
            hi = mid - 1; 
        } else { 
            return mid; 
        } 
    } 
    return lo; 
} 

get方法實現：基于rank方法，判斷返回的keys[index]與key進行比較，如果相等返回values[index]，不相等就返回null

@Override 
public V get(K key) { 
    int index = this.rank(key); 
    if (index < size && key.compareTo(keys[index]) == 0) { 
        return values[index]; 
    } 
    return null; 
} 

put方法實現：基于rank方法，判斷返回的keys[index]與key進行比較，如果相等直接修改values[index]的值，如果不相等表示不存在該key，需要插入并且移動數組

@Override 
public void put(K key, V value) { 
    int index = this.rank(key); 
    if (index < size && key.compareTo(keys[index]) == 0) { 
        values[index] = value; 
        return; 
    } 
 
    for (int j = size; j > index; j--) { 
        this.keys[j] = this.keys[j--]; 
        this.values[j] = this.values[j--]; 
    } 
    keys[index] = key; 
    values[index] = value; 
    size++; 
} 

delete方法實現：通過rank方法判斷該key是否存在，如果不存在就直接返回，如果存在需要移動數組

@Override 
public void delete(K key) { 
    int index = this.rank(key); 
    if (Objects.isNull(keys[index]) || key.compareTo(keys[index]) != 0) { 
        return; 
    } 
    for (int j = index; j < size - 1; j++) { 
        keys[j] = keys[j + 1]; 
        values[j] = values[j + 1]; 
    } 
    keys[size - 1] = null; 
    values[size - 1] = null; 
    size--; 
} 

基于數組實現的Map，雖然get方法采用的二分查找法，很快O(logN)，但是在處理大量數據的情況下效率依然很低，因為put方法還是太慢;下篇我們將基于二叉樹來實現Map，繼續改進提升效率

”

文中所有源碼已放入到了github倉庫https://github.com/silently9527/JavaCore