本篇內(nèi)容介紹了“基于數(shù)組或鏈表實現(xiàn)Map的方法教程”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

創(chuàng)新互聯(lián)主營開福網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,成都APP應(yīng)用開發(fā),開福h5微信小程序開發(fā)搭建,開福網(wǎng)站營銷推廣歡迎開福等地區(qū)企業(yè)咨詢

前言

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

Map API的定義

在開始之前，我們需要先定義出Map的接口定義，后續(xù)的版本都會基于此接口實現(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;     } }

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

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

基于鏈表實現(xiàn)首先我們需要定義一個Node節(jié)點，表示我們需要存儲的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方法的實現(xiàn)思路是遍歷鏈表，然后比較每個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方法的實現(xiàn)思路也是遍歷鏈表，然后比較每個Node的key值是否相等，如果相等那么覆蓋掉value，如果未查找到有key相等的node，那么就新建一個Node放到鏈表的開頭

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

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

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

”

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

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

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

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

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

• 在基于數(shù)組的實現(xiàn)中，我們會定義兩個數(shù)組變量分部存放keys、values;

• rank方法的實現(xiàn)：由于我們整個數(shù)組都是有序的，我們可以二分查找法(可以查看《老哥是時候來復(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方法實現(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方法實現(xiàn)：基于rank方法，判斷返回的keys[index]與key進(jìn)行比較，如果相等直接修改values[index]的值，如果不相等表示不存在該key，需要插入并且移動數(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方法實現(xiàn)：通過rank方法判斷該key是否存在，如果不存在就直接返回，如果存在需要移動數(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ù)組實現(xiàn)的Map，雖然get方法采用的二分查找法，很快O(logN)，但是在處理大量數(shù)據(jù)的情況下效率依然很低，因為put方法還是太慢

“基于數(shù)組或鏈表實現(xiàn)Map的方法教程”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！