遍歷地圖演算法

1. java中map的常用遍歷方法有哪些

ava中map的常用遍歷的具體方法有：

一 、在for-each循環中使用entries來遍歷。這是最常見的並且在大多數情況下也是最可取的遍歷方式。在鍵值都需要時使用。

二、 在for-each循環中遍歷keys或values。如果只需要map中的鍵或者值，你可以通過keySet或values來實現遍歷，而不是用entrySet。

三、使用Iterator遍歷。

四、通過鍵找值遍歷（效率低）。

總結：如果僅需要鍵(keys)或值(values)使用方法二。如果你使用的語言版本低於java 5，或是打算在遍歷時刪除entries，必須使用方法三。否則使用方法一(鍵值都要)。

2. 如何遍歷map

遍歷Map的四種方法

public static void main(String[] args) {

Map<String, String> map = new HashMap<String, String>();
map.put("1", "value1");
map.put("2", "value2");
map.put("3", "value3");

//第一種：普遍使用，二次取值
System.out.println("通過Map.keySet遍歷key和value：");
for (String key : map.keySet()) {
System.out.println("key= "+ key + " and value= " + map.get(key));
}

//第二種
System.out.println("通過Map.entrySet使用iterator遍歷key和value：");
Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<String, String> entry = it.next();
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}

//第三種：推薦，尤其是容量大時
System.out.println("通過Map.entrySet遍歷key和value");
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}

//第四種
System.out.println("通過Map.values()遍歷所有的value，但不能遍歷key");
for (String v : map.values()) {
System.out.println("value= " + v);
}
}

當一個人找不到出路的時候，最好的辦法就是將當前能做好的事情做到極致，做到無人能及。

3. Java遍歷Map的幾種方式的效率對比

遍歷Map的方式有很多，通常場景下我們需要的是遍歷Map中的Key和Value，那麼推薦使用的、效率最高的方式是：

public static void main(String[] args)
{
HashMap<String, String> hm = new HashMap<String, String>();
hm.put("111", "222");

Set<Map.Entry<String, String>> entrySet = hm.entrySet();
Iterator<Map.Entry<String, String>> iter = entrySet.iterator();
while (iter.hasNext())
{
Map.Entry<String, String> entry = iter.next();
System.out.println(entry.getKey() + "\t" + entry.getValue());
}
}

4. java遍歷Map的幾種方法分析

1.先初始化一個map
public class TestMap {
public static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
}
2.keySet values
如果只需要map的key或者value，用map的keySet或values方法無疑是最方便的
// KeySet 獲取key
public void testKeySet() {
for (Integer key : map.keySet()) {
System.out.println(key);
}
}
// values 獲取value
public void testValues() {
for (Integer value : map.values()) {
System.out.println(value);
}
}
3.keySet get(key)
如果需要同時獲取key和value，可以先獲取key,然後再通過map的get(key)獲取value

需要說明的是，該方法不是最優選擇，一般不推薦使用

// keySet get(key) 獲取key and value
public void testKeySetAndGetKey() {
for (Integer key : map.keySet()) {
System.out.println(key + ":" + map.get(key));
}
}
4.entrySet
通過對map entrySet的遍歷，也可以同時拿到key和value，一般情況下，性能上要優於上一種,這一種也是最常用的遍歷方法

// entrySet 獲取key and value
public void testEntry() {
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}
}
5.Iterator
對於上面的幾種foreach都可以用Iterator代替，其實foreach在java5中才被支持，foreach的寫法看起來更簡潔

但Iterator也有其優勢：在用foreach遍歷map時，如果改變其大小，會報錯，但如果只是刪除元素，可以使用Iterator的remove方法刪除元素

// Iterator entrySet 獲取key and value
public void testIterator() {
Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, Integer> entry = it.next();
System.out.println(entry.getKey() + ":" + entry.getValue());
// it.remove(); 刪除元素
}
}

5. 哪種Map遍歷方法更優

我們都知道遍歷Map一般有3種方法，values()，keySet()和entrySet()，

常見的是keySet用的多，簡單容易理解，entrySet()是返回Map中的靜態內部類Entry類類型的Set實例，當然了你別說forEach，forEach只是一種代替for(inti=0;;)和while()遍歷的一種方式，底層也是用迭代器實現的,只不過把部分東西隱藏了,建議大家平常開發中能用forEach遍歷,盡可能的用這個,《Effectivejava》中也明確表示了，簡單而不容易出錯。

如果Map中有大量的元素，而且並發量又很高，這就涉及到採用哪種遍歷方法的問題，下面就來測試一下：

Map<String,String>mapTest=newHashMap<String,String>();
for(inti=0;i<10000;i++){
mapTest.put(String.valueOf(i),String.valueOf(i));
}

//一種遍歷，keySet()方法

longstart=System.nanoTime();
Set<String>setEach=mapTest.keySet();
for(Stringkey:setEach){
Stringvalue=mapTest.get(key);
}
longend=System.nanoTime();
System.out.println("keySet遍歷map耗時"+(end-start)/1000+"微秒");

//二種遍歷，可用values()返回Collection<T>,不容易得到對應的key

start=System.nanoTime();
Collection<String>co=mapTest.values();
for(Stringvalue:co){
//遍歷中也在創建value
}
end=System.nanoTime();
System.out.println("values遍歷map(只得到值)耗時"+(end-start)/1000+"微秒");

//三種遍歷，用entrySet()方法返回Set<Map.Entry<T,T>>類型，再獲取里邊的Map.Entry

start=System.nanoTime();
Set<Map.Entry<String,String>>entrySet=mapTest.entrySet();
for(Map.Entry<String,String>entry:entrySet){
Stringkey=entry.getKey();
Stringvalue=entry.getValue();
}
end=System.nanoTime();
System.out.println("entrySet遍歷map耗時"+(end-start)/1000+"微秒");

經過多次運行，結果大概都是這樣的：

• keySet遍歷map耗時9867微秒

• values遍歷map(只得到值)耗時2539微秒

• entrySet遍歷map耗時2783微秒

values()是返回Map的所有value的集合collection,只能遍歷到值，很難遍歷到key所以一般不用，除非在某種特殊場合，所以一般採用的第一種和第三種方式。而測試表明entrySet()方式遍歷效率更高。

entrySet()方式遍歷之所以快於keySet()，一個原因是keySet相當與遍歷了2次，

一次是對key的Set集合的遍歷，二次是每次遍歷過程都要通過key和map.get(key)來獲取value值。

第二個原因是map.get(key)獲取的時候，底層其實根據key的hashcode值經過哈希演算法得到一個hash值然後作為索引映射到對應table數組的索引位置，這是一次密集型計算，很耗費CPU，如果有大量的元素，則會使CPU使用率飆升，影響響應速度，而entrySet()返回的set里邊元素都是Map.Entry類型，key和value就是這個類的一個屬性，entry.getKey()和entry.getValue()效率肯定很高。

所以平常開發過程中，如果對Map講究效率的遍歷的話，還是採用entrySet()方法。

6. 百度地圖的路徑搜索演算法

這個還是要問程序猿，現在比較流行A*演算法，至於網路是否開發出了新的演算法不得而知，畢竟沒有完全相同的程序。
給你看一篇文獻：
地圖中最短路徑的搜索演算法研究
學生:李小坤 導師：董巒
摘要：目前為止, 國內外大量專家學者對「最短路徑問題」進行了深入的研究。本文通過理論分析, 結合實際應用，從各個方面較系統的比較廣度優先搜索演算法(BFS)、深度優先搜索演算法(DFS)、A* 演算法的優缺點。
關鍵詞:最短路徑演算法；廣度優先演算法；深度優先演算法；A*演算法；
The shortest path of map's search algorithm
Abstract:So far, a large number of domestic and foreign experts and scholars on the" shortest path problem" in-depth study. In this paper, through theoretical analysis and practical application, comprise with the breadth-first search algorithm ( BFS ), depth-first search algorithm ( DFS ) and the A * algorithms from any aspects of systematic.
Key words: shortest path algorithm; breadth-first algorithm; algorithm; A * algorithm;
前言：
最短路徑問題是地理信息系統（GIS）網路分析的重要內容之一，而且在圖論中也有著重要的意義。實際生活中許多問題都與「最短路徑問題」有關, 比如: 網路路由選擇, 集成電路設計、布線問題、電子導航、交通旅遊等。本文應用深度優先演算法，廣度優先演算法和A*演算法，對一具體問題進行討論和分析，比較三種算的的優缺點。

在地圖中最短路徑的搜索演算法研究中，每種演算法的優劣的比較原則主要遵循以下三點:[1]
(1)演算法的完全性：提出一個問題，該問題存在答案，該演算法能夠保證找到相應的答案。演算法的完全性強是演算法性能優秀的指標之一。
(2)演算法的時間復雜性: 提出一個問題，該演算法需要多長時間可以找到相應的答案。演算法速度的快慢是演算法優劣的重要體現。
(3)演算法的空間復雜性:演算法在執行搜索問題答案的同時，需要多少存儲空間。演算法佔用資源越少，演算法的性能越好。
地圖中最短路徑的搜索演算法:
1、廣度優先演算法
廣度優先演算法(Breadth-First-Search)，又稱作寬度優先搜索，或橫向優先搜索，是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型,Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。廣度優先演算法其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位址，徹底地搜索整張圖，直到找到結果為止。BFS並不使用經驗法則演算法。
廣度優先搜索演算法偽代碼如下：[2-3]
BFS(v)//廣度優先搜索G，從頂點v開始執行
//所有已搜索的頂點i都標記為Visited(i)=1.
//Visited的初始分量值全為0
Visited(v)=1;
Q=[];//將Q初始化為只含有一個元素v的隊列
while Q not null do
u=DelHead(Q);
for 鄰接於u的所有頂點w do
if Visited(w)=0 then
AddQ(w,Q); //將w放於隊列Q之尾
Visited(w)=1;
endif
endfor
endwhile
end BFS
這里調用了兩個函數：AddQ(w,Q)是將w放於隊列Q之尾；DelHead(Q)是從隊列Q取第一個頂點，並將其從Q中刪除。重復DelHead(Q)過程，直到隊列Q空為止。
完全性：廣度優先搜索演算法具有完全性。這意指無論圖形的種類如何，只要目標存在，則BFS一定會找到。然而，若目標不存在，且圖為無限大，則BFS將不收斂（不會結束）。
時間復雜度：最差情形下，BFS必須尋找所有到可能節點的所有路徑，因此其時間復雜度為,其中|V|是節點的數目，而 |E| 是圖中邊的數目。
空間復雜度：因為所有節點都必須被儲存，因此BFS的空間復雜度為，其中|V|是節點的數目，而|E|是圖中邊的數目。另一種說法稱BFS的空間復雜度為O(B),其中B是最大分支系數，而M是樹的最長路徑長度。由於對空間的大量需求，因此BFS並不適合解非常大的問題。[4-5]
2、深度優先演算法
深度優先搜索演算法（Depth First Search）英文縮寫為DFS，屬於一種回溯演算法，正如演算法名稱那樣，深度優先搜索所遵循的搜索策略是盡可能「深」地搜索圖。[6]其過程簡要來說是沿著頂點的鄰點一直搜索下去，直到當前被搜索的頂點不再有未被訪問的鄰點為止，此時，從當前輩搜索的頂點原路返回到在它之前被搜索的訪問的頂點，並以此頂點作為當前被搜索頂點。繼續這樣的過程，直至不能執行為止。
深度優先搜索演算法的偽代碼如下：[7]
DFS(v) //訪問由v到達的所有頂點
Visited(v)=1;
for鄰接於v的每個頂點w do
if Visited(w)=0 then
DFS(w);
endif
endfor
end DFS
作為搜索演算法的一種，DFS對於尋找一個解的NP（包括NPC）問題作用很大。但是，搜索演算法畢竟是時間復雜度是O(n!)的階乘級演算法，它的效率比較低，在數據規模變大時，這種演算法就顯得力不從心了。[8]關於深度優先搜索的效率問題，有多種解決方法。最具有通用性的是剪枝，也就是去除沒有用的搜索分支。有可行性剪枝和最優性剪枝兩種。
BFS:對於解決最短或最少問題特別有效，而且尋找深度小，但缺點是內存耗費量大（需要開大量的數組單元用來存儲狀態）。
DFS：對於解決遍歷和求所有問題有效，對於問題搜索深度小的時候處理速度迅速，然而在深度很大的情況下效率不高。
3、A*演算法
1968年的一篇論文，「P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968」。[9]從此，一種精巧、高效的演算法——A*演算法問世了，並在相關領域得到了廣泛的應用。A* 演算法其實是在寬度優先搜索的基礎上引入了一個估價函數,每次並不是把所有可擴展的結點展開,而是利用估價函數對所有未展開的結點進行估價, 從而找出最應該被展開的結點,將其展開,直到找到目標節點為止。
A*演算法主要搜索過程偽代碼如下：[10]
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
算起點的估價值;
將起點放入OPEN表;
while(OPEN!=NULL) //從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
endif
for(當前節點n 的每個子節點X)
算X的估價值;
if(X in OPEN)
if(X的估價值小於OPEN表的估價值)
把n設置為X的父親;
更新OPEN表中的估價值; //取最小路徑的估價值;
endif
endif
if(X inCLOSE)
if( X的估價值小於CLOSE表的估價值)
把n設置為X的父親;
更新CLOSE表中的估價值;
把X節點放入OPEN //取最小路徑的估價值
endif
endif
if(X not inboth)
把n設置為X的父親;
求X的估價值;
並將X插入OPEN表中; //還沒有排序
endif
end for
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
end while(OPEN!=NULL)
保存路徑，即 從終點開始，每個節點沿著父節點移動直至起點，這就是你的路徑；
A *演算法分析：
DFS和BFS在展開子結點時均屬於盲目型搜索，也就是說，它不會選擇哪個結點在下一次搜索中更優而去跳轉到該結點進行下一步的搜索。在運氣不好的情形中，均需要試探完整個解集空間, 顯然，只能適用於問題規模不大的搜索問題中。而A*演算法與DFS和BFS這類盲目型搜索最大的不同，就在於當前搜索結點往下選擇下一步結點時，可以通過一個啟發函數來進行選擇，選擇代價最少的結點作為下一步搜索結點而跳轉其上。[11]A *演算法就是利用對問題的了解和對問題求解過程的了解, 尋求某種有利於問題求解的啟發信息, 從而利用這些啟發信息去搜索最優路徑.它不用遍歷整個地圖, 而是每一步搜索都根據啟發函數朝著某個方向搜索.當地圖很大很復雜時, 它的計算復雜度大大優於D ijks tr a演算法, 是一種搜索速度非常快、效率非常高的演算法.但是, 相應的A*演算法也有它的缺點.啟發性信息是人為加入的, 有很大的主觀性, 直接取決於操作者的經驗, 對於不同的情形要用不同的啟發信息和啟發函數, 且他們的選取難度比較大,很大程度上找不到最優路徑。
總結：
本文描述了最短路徑演算法的一些步驟，總結了每個演算法的一些優缺點，以及演算法之間的一些關系。對於BFS還是DFS，它們雖然好用，但由於時間和空間的局限性，以至於它們只能解決規模不大的問題，而最短或最少問題應該選用BFS,遍歷和求所有問題時候則應該選用DFS。至於A*演算法，它是一種啟發式搜索演算法，也是一種最好優先的演算法，它適合於小規模、大規模以及超大規模的問題，但啟發式搜索演算法具有很大的主觀性，它的優劣取決於編程者的經驗，以及選用的啟發式函數，所以用A*演算法編寫一個優秀的程序，難度相應是比較大的。每種演算法都有自己的優缺點，對於不同的問題選擇合理的演算法，才是最好的方法。
參考文獻：
[1]陳聖群,滕忠堅,洪親,陳清華.四種最短路徑演算法實例分析[J].電腦知識與技術(學術交流),2007(16):1030-1032
[2]劉樹林,尹玉妹.圖的最短路徑演算法及其在網路中的應用[J].軟體導刊,2011(07):51-53
[3]劉文海,徐榮聰.幾種最短路徑的演算法及比較[J].福建電腦，2008(02）:9-12
[4]鄧春燕.兩種最短路徑演算法的比較[J].電腦知識與技術，2008（12）：511-513
[5]王蘇男,宋偉,姜文生.最短路徑演算法的比較[J].系統工程與電子技術,1994(05)：43-49
[6]徐鳳生,李天志.所有最短路徑的求解演算法[J].計算機工程與科學,2006(12)：83-84
[7]李臣波,劉潤濤.一種基於Dijkstra的最短路徑演算法[J].哈爾濱理工大學學報,2008(03)：35-37
[8]徐鳳生.求最短路徑的新演算法[J].計算機工程與科學,2006(02).
[9] YanchunShen . An improved Graph-based Depth-First algorithm and Dijkstra algorithm program of police patrol [J] . 2010 International Conference on Electrical Engineering and Automatic Control , 2010(3) : 73-77
[10]部亞松.VC++實現基於Dijkstra演算法的最短路徑[J].科技信息(科學教研),2008(18)：36-37
[11] 楊長保,王開義,馬生忠.一種最短路徑分析優化演算法的實現[J]. 吉林大學學報(信息科學版),2002(02)：70-74

7. 地圖區域遍歷演算法求助

首先從前序的第一個確定二叉樹的根A，回到中序切割，將二叉樹分為三部分： 左子樹的中序DBGE，根A，右子樹的中序CHF 再由左子樹的前序可知左子樹的根為B，於是左子樹的中序被再次切分為三部分： 左子樹的左子樹中序D，左子樹的根B

8. java Map 怎麼遍歷

關於java中遍歷map具體有四種方式，請看下文詳解。

1、這是最常見的並且在大多數情況下也是最可取的遍歷方式，在鍵值都需要時使用。

Map<Integer, Integer> map = newHashMap<Integer, Integer>();

for(Map.Entry<Integer, Integer> entry : map.entrySet()) {

System.out.println("Key = "+ entry.getKey() + ", Value = "+ entry.getValue());

}

2、在for-each循環中遍歷keys或values。

如果只需要map中的鍵或者值，你可以通過keySet或values來實現遍歷，而不是用entrySet。

Map<Integer, Integer> map = newHashMap<Integer, Integer>();

for(Integer key : map.keySet()) {

System.out.println("Key = "+ key);

}

for(Integer value : map.values()) {

System.out.println("Value = "+ value);

}

該方法比entrySet遍歷在性能上稍好（快了10%），而且代碼更加干凈。

3、使用Iterator遍歷

使用泛型：

Map<Integer, Integer> map = newHashMap<Integer, Integer>();

Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();

while(entries.hasNext()) {

Map.Entry<Integer, Integer> entry = entries.next();

System.out.println("Key = "+ entry.getKey() + ", Value = "+ entry.getValue());

}

不使用泛型：

Map map = newHashMap();

Iterator entries = map.entrySet().iterator();

while(entries.hasNext()) {

Map.Entry entry = (Map.Entry) entries.next();

Integer key = (Integer)entry.getKey();

Integer value = (Integer)entry.getValue();

System.out.println("Key = "+ key + ", Value = "+ value);

}

4、通過鍵找值遍歷（效率低）

Map<Integer, Integer> map = newHashMap<Integer, Integer>();

for(Integer key : map.keySet()) {

Integer value = map.get(key);

System.out.println("Key = "+ key + ", Value = "+ value);

}

假設Map中的鍵值對為1=>11,2=>22,3=>33,現用方法1來遍歷Map代碼和調試結果如下：

(8)遍歷地圖演算法擴展閱讀：

1、HashMap的重要參數

HashMap 的實例有兩個參數影響其性能：初始容量 和載入因子。容量是哈希表中桶的數量，初始容量只是哈希表在創建時的容量。

載入因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了載入因子與當前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建內部數據結構），從而哈希表將具有大約兩倍的桶數。

在Java編程語言中，載入因子默認值為0.75，默認哈希表元為101。

2、HashMap的同步機制

注意，此實現不是同步的。 如果多個線程同時訪問一個哈希映射，而其中至少一個線程從結構上修改了該映射，則它必須保持外部同步。

（結構上的修改是指添加或刪除一個或多個映射關系的任何操作；以防止對映射進行意外的非同步訪問，如下：

Map m = Collections.synchronizedMap(new HashMap(...));

9. JAVA循環遍歷Map的幾種方法

第一種用for循環

Java代碼
for(Map.Entry<String, String> entry:map.entrySet()){
System.out.println(entry.getKey()+"--->"+entry.getValue());
}

第二種用迭代

Java代碼
Set set = map.entrySet();
Iterator i = set.iterator();
while(i.hasNext()){
Map.Entry<String, String> entry1=(Map.Entry<String, String>)i.next();
System.out.println(entry1.getKey()+"=="+entry1.getValue());
}

用keySet()迭代

Java代碼
Iterator it=map.keySet().iterator();
while(it.hasNext()){
String key;
String value;
key=it.next().toString();
value=map.get(key);
System.out.println(key+"--"+value);
}

用entrySet()迭代

Java代碼
Iterator it=map.entrySet().iterator();
System.out.println( map.entrySet().size());
String key;
String value;
while(it.hasNext()){
Map.Entry entry = (Map.Entry)it.next();
key=entry.getKey().toString();
value=entry.getValue().toString();
System.out.println(key+"===="+value);
}

10. 怎麼樣實現map這樣一個遍歷

#include<map>
#include<string>
#include<iostream>int main(){map<string,int> words;
map<string,int>::iterator it=words.begin();
for(;it!=words.end();++it)
cout<<"key:"<<it->first
<<"value:"<<it->second<<end1;return 0;} std::map<key, value> mymap;
map<key,value>::iterator begiter = mymap.begin();
map<key,value>::iterator enditer = mymap.end();
for(;begiter!=enditer;++begiter){// ....}
盡管map的底層一般由紅黑樹實現，但map的迭代器還是使它具有了一個類似線性結構的訪問介面。因此，所有適用於list等順序容器的訪問方法都可以用來對map進行訪問。諸如for_each(),accumulate()等遍歷區間的演算法都可以用來遍歷map。