日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

[[388024]]

本文轉(zhuǎn)載自微信公眾號(hào)「貝塔學(xué)JAVA」，作者Silently9527。轉(zhuǎn)載本文請(qǐng)聯(lián)系貝塔學(xué)JAVA公眾號(hào)。

“專業(yè)、務(wù)實(shí)、高效、創(chuàng)新、把客戶的事當(dāng)成自己的事”是我們每一個(gè)人一直以來(lái)堅(jiān)持追求的企業(yè)文化。 創(chuàng)新互聯(lián)公司是您可以信賴的網(wǎng)站建設(shè)服務(wù)商、專業(yè)的互聯(lián)網(wǎng)服務(wù)提供商! 專注于成都做網(wǎng)站、網(wǎng)站建設(shè)、軟件開(kāi)發(fā)、設(shè)計(jì)服務(wù)業(yè)務(wù)。我們始終堅(jiān)持以客戶需求為導(dǎo)向，結(jié)合用戶體驗(yàn)與視覺(jué)傳達(dá)，提供有針對(duì)性的項(xiàng)目解決方案，提供專業(yè)性的建議，創(chuàng)新互聯(lián)建站將不斷地超越自我，追逐市場(chǎng)，引領(lǐng)市場(chǎng)！

前言

JAVA中的Map主要就是將一個(gè)鍵和一個(gè)值聯(lián)系起來(lái)。雖然JAVA中已經(jīng)提供了很多Map的實(shí)現(xiàn)，為了學(xué)習(xí)并掌握常用的數(shù)據(jù)結(jié)構(gòu)，從本篇開(kāi)始我將自己實(shí)現(xiàn)Map的功能，本篇主要是通過(guò)數(shù)組和鏈表兩種方式實(shí)現(xiàn)，之后提供二叉樹，紅黑樹，散列表的版本實(shí)現(xiàn)。通過(guò)自己手寫各個(gè)版本的Map實(shí)現(xiàn)，掌握每種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)，可以在實(shí)際的工作中根據(jù)需要選擇適合的Map。

Map API的定義

在開(kāi)始之前，我們需要先定義出Map的接口定義，后續(xù)的版本都會(huì)基于此接口實(shí)現(xiàn)

 
 
 

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

這個(gè)接口是最簡(jiǎn)單的一個(gè)Map定義，相信這些方法對(duì)于java程序員來(lái)說(shuō)不會(huì)陌生;

基于鏈表實(shí)現(xiàn)Map

基于鏈表實(shí)現(xiàn)首先我們需要定義一個(gè)Node節(jié)點(diǎn)，表示我們需要存儲(chǔ)的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方法的實(shí)現(xiàn)思路是遍歷鏈表，然后比較每個(gè)Node中的key是否相等，如果相等就返回value，否則返回null

 
 
 

  
  
  
@Override 
  
  
  
public V get(K key) { 
  
  
  
    return searchNode(key).map(node -> node.value).orElse(null); 
  
  
  
} 
  
  
  
 
  
  
  
public Optional 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方法的實(shí)現(xiàn)思路也是遍歷鏈表，然后比較每個(gè)Node的key值是否相等，如果相等那么覆蓋掉value，如果未查找到有key相等的node，那么就新建一個(gè)Node放到鏈表的開(kāi)頭

 
 
 

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

delete方法實(shí)現(xiàn)同樣也需要遍歷鏈表，因?yàn)槲覀兊氖菃蜗蜴湵恚瑒h除某個(gè)節(jié)點(diǎn)有兩種思路，第一種，在遍歷鏈表的時(shí)候記錄下當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，把上一個(gè)節(jié)點(diǎn)的next指向當(dāng)前節(jié)點(diǎn)next;第二種，當(dāng)遍歷到需要?jiǎng)h除的節(jié)點(diǎn)時(shí)，把需要?jiǎng)h除節(jié)點(diǎn)的next的key、value完全復(fù)制到需要?jiǎng)h除的節(jié)點(diǎn)，把next指針指向next.next，比如：first - > A -> B -> C -> D -> E -> F -> G -> NULL,要?jiǎng)h除 C 節(jié)點(diǎn)，就把D節(jié)點(diǎn)完全復(fù)制到c中，然后C -> E，變相刪除了C

 
 
 

  
  
  
@Override 
  
  
  
public void delete(K key) { 
  
  
  
// 第一種實(shí)現(xiàn)： 
  
  
  
//        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; 
  
  
  
//                } 
  
  
  
//            } 
  
  
  
//        } 
  
  
  
 
  
  
  
// 第二中實(shí)現(xiàn): 
  
  
  
    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; 
  
  
  
        } 
  
  
  
    } 
  
  
  
} 
 
 
 

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

”

基于數(shù)組實(shí)現(xiàn)Map

基于鏈表的實(shí)現(xiàn)非常低效，因?yàn)槊看尾僮鞫夹枰闅v鏈表，假如我們的數(shù)據(jù)是有序的，那么查找的時(shí)候我們可以使用二分查找法，那么get方法會(huì)加快很多

為了體現(xiàn)出我們的Map是有序的，我們需要重新定義一個(gè)有序的Map

 
 
 

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

該定義要求key必須實(shí)現(xiàn)接口Comparable，rank方法如果key值存在就返回對(duì)應(yīng)在數(shù)組中的下標(biāo)，如果不存在就返回小于key鍵的數(shù)量

• 在基于數(shù)組的實(shí)現(xiàn)中，我們會(huì)定義兩個(gè)數(shù)組變量分部存放keys、values;
• rank方法的實(shí)現(xiàn)：由于我們整個(gè)數(shù)組都是有序的，我們可以二分查找法(可以查看《老哥是時(shí)候來(lái)復(fù)習(xí)下數(shù)據(jù)結(jié)構(gòu)與算法了》)，如果存在就返回所在數(shù)組的下表，如果不存在就返回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方法實(shí)現(xiàn)：基于rank方法，判斷返回的keys[index]與key進(jìn)行比較，如果相等返回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方法實(shí)現(xiàn)：基于rank方法，判斷返回的keys[index]與key進(jìn)行比較，如果相等直接修改values[index]的值，如果不相等表示不存在該key，需要插入并且移動(dòng)數(shù)組

 
 
 

  
  
  
@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方法實(shí)現(xiàn)：通過(guò)rank方法判斷該key是否存在，如果不存在就直接返回，如果存在需要移動(dòng)數(shù)組

 
 
 

  
  
  
@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--; 
  
  
  
} 
 
 
 

基于數(shù)組實(shí)現(xiàn)的Map，雖然get方法采用的二分查找法，很快O(logN)，但是在處理大量數(shù)據(jù)的情況下效率依然很低，因?yàn)閜ut方法還是太慢;下篇我們將基于二叉樹來(lái)實(shí)現(xiàn)Map，繼續(xù)改進(jìn)提升效率

”

文中所有源碼已放入到了github倉(cāng)庫(kù)https://github.com/silently9527/JavaCore

當(dāng)前題目：基于數(shù)組或鏈表實(shí)現(xiàn)Map
本文鏈接：http://m.5511xx.com/article/cophjhc.html