java紅黑樹演算法

❶ java中的TreeMap為什麼要用紅黑樹實現，而不用AVL樹實現

這篇文章講的很明白了。

http://blog.csdn.net/hustyangju/article/details/27214251?utm_source=tuicool
很疑惑，為什麼大家碰到問題不先自己去網路呢？

❷ 演算法中紅黑樹的刪除方法問題.

了無適俗韻真可與晤語

❸ 請問java中HashMap是怎麼實現的，還有treeMap的實現原理是紅黑樹，請解釋一下紅黑樹

參考資料的網頁上有比較的代碼,你可以仔細看下~~~

java中HashMap,LinkedHashMap,TreeMap，HashTable的區別
java為數據結構中的映射定義了一個介面java.util.Map;它有四個實現類,分別是HashMap Hashtable LinkedHashMap 和TreeMap
Map主要用於存儲健值對，根據鍵得到值，因此不允許鍵重復(重復了覆蓋了),但允許值重復。
Hashmap 是一個最常用的Map,它根據鍵的HashCode 值存儲數據,根據鍵可以直接獲取它的值，具有很快的訪問速度，遍歷時，取得數據的順序是完全隨機的。HashMap最多隻允許一條記錄的鍵為Null;允許多條記錄的值為 Null;HashMap不支持線程的同步，即任一時刻可以有多個線程同時寫HashMap;可能會導致數據的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
Hashtable與 HashMap類似,它繼承自Dictionary類，不同的是:它不允許記錄的鍵或者值為空;它支持線程的同步，即任一時刻只有一個線程能寫Hashtable,因此也導致了 Hashtable在寫入時會比較慢。
LinkedHashMap保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的.也可以在構造時用帶參數，按照應用次數排序。在遍歷的時候會比HashMap慢，不過有種情況例外，當HashMap容量很大，實際數據較少時，遍歷起來可能會比LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數據有關，和容量無關，而HashMap的遍歷速度和他的容量有關。
TreeMap實現SortMap介面，能夠把它保存的記錄根據鍵排序,默認是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator 遍歷TreeMap時，得到的記錄是排過序的。

一般情況下，我們用的最多的是HashMap,HashMap裡面存入的鍵值對在取出的時候是隨機的,它根據鍵的HashCode值存儲數據,根據鍵可以直接獲取它的值，具有很快的訪問速度。在Map 中插入、刪除和定位元素，HashMap 是最好的選擇。
TreeMap取出來的是排序後的鍵值對。但如果您要按自然順序或自定義順序遍歷鍵，那麼TreeMap會更好。
LinkedHashMap 是HashMap的一個子類，如果需要輸出的順序和輸入的相同,那麼用LinkedHashMap可以實現,它還可以按讀取順序來排列，像連接池中可以應用。

❹ Java中HashMap和TreeMap的區別深入理解

首先介紹一下什麼是Map。在數組中我們是通過數組下標來對其內容索引的，而在Map中我們通過對象來對對象進行索引，用來索引的對象叫做key，其對應的對象叫做value

首先介紹一下什麼是Map。在數組中我們是通過數組下標來對其內容索引的，而在Map中我們通過對象來對對象進行索引，用來索引的對象叫做key，其對應的對象叫做value。這就是我們平時說的鍵值對。

HashMap通過hashcode對其內容進行快速查找，而
TreeMap中所有的元素都保持著某種固定的順序，如果你需要得到一個有序的結果你就應該使用TreeMap（HashMap中元素的排列順序是不固定的）。

HashMap 非線程安全 TreeMap 非線程安全

線程安全

在Java里，線程安全一般體現在兩個方面：

1、多個thread對同一個java實例的訪問（read和modify）不會相互干擾，它主要體現在關鍵字synchronized。如ArrayList和Vector，HashMap和Hashtable

（後者每個方法前都有synchronized關鍵字）。如果你在interator一個List對象時，其它線程remove一個element，問題就出現了。

2、每個線程都有自己的欄位，而不會在多個線程之間共享。它主要體現在java.lang.ThreadLocal類，而沒有Java關鍵字支持，如像static、transient那樣。

1.AbstractMap抽象類和SortedMap介面

AbstractMap抽象類：(HashMap繼承AbstractMap)覆蓋了equals()和hashCode()方法以確保兩個相等映射返回相同的哈希碼。如果兩個映射大小相等、包含同樣的鍵且每個鍵在這兩個映射中對應的值都相同，則這兩個映射相等。映射的哈希碼是映射元素哈希碼的總和，其中每個元素是Map.Entry介面的一個實現。因此，不論映射內部順序如何，兩個相等映射會報告相同的哈希碼。

SortedMap介面：（TreeMap繼承自SortedMap）它用來保持鍵的有序順序。SortedMap介面為映像的視圖(子集)，包括兩個端點提供了訪問方法。除了排序是作用於映射的鍵以外，處理SortedMap和處理SortedSet一樣。添加到SortedMap實現類的元素必須實現Comparable介面，否則您必須給它的構造函數提供一個Comparator介面的實現。TreeMap類是它的唯一一份實現。

2.兩種常規Map實現

HashMap：基於哈希表實現。使用HashMap要求添加的鍵類明確定義了hashCode()和equals()[可以重寫hashCode()和equals()]，為了優化HashMap空間的使用，您可以調優初始容量和負載因子。

(1)HashMap(): 構建一個空的哈希映像
(2)HashMap(Map m): 構建一個哈希映像，並且添加映像m的所有映射

(3)HashMap(int initialCapacity): 構建一個擁有特定容量的空的哈希映像
(4)HashMap(int
initialCapacity, float loadFactor): 構建一個擁有特定容量和載入因子的空的哈希映像

TreeMap：基於紅黑樹實現。TreeMap沒有調優選項，因為該樹總處於平衡狀態。
(1)TreeMap():構建一個空的映像樹

(2)TreeMap(Map m): 構建一個映像樹，並且添加映像m中所有元素
(3)TreeMap(Comparator c):
構建一個映像樹，並且使用特定的比較器對關鍵字進行排序
(4)TreeMap(SortedMap s):
構建一個映像樹，添加映像樹s中所有映射，並且使用與有序映像s相同的比較器排序

3.兩種常規Map性能

HashMap：適用於在Map中插入、刪除和定位元素。
Treemap：適用於按自然順序或自定義順序遍歷鍵(key)。

4.總結

HashMap通常比TreeMap快一點(樹和哈希表的數據結構使然)，建議多使用HashMap，在需要排序的Map時候才用TreeMap。

復制代碼
代碼如下:

import java.util.HashMap;
import
java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;

import java.util.TreeMap;
public class HashMaps {
public static void
main(String[] args) {
Map<String, String> map = new HashMap<String,
String>();
map.put("a", "aaa");
map.put("b", "bbb");
map.put("c",
"ccc");
map.put("d", "ddd");
Iterator<String> iterator =
map.keySet().iterator();
while (iterator.hasNext()) {
Object key =
iterator.next();
System.out.println("map.get(key) is :" + map.get(key));

}
// 定義HashTable,用來測試
Hashtable<String, String> tab = new
Hashtable<String, String>();
tab.put("a", "aaa");
tab.put("b",
"bbb");
tab.put("c", "ccc");
tab.put("d", "ddd");

Iterator<String> iterator_1 = tab.keySet().iterator();
while
(iterator_1.hasNext()) {
Object key = iterator_1.next();

System.out.println("tab.get(key) is :" + tab.get(key));
}

TreeMap<String, String> tmp = new TreeMap<String, String>();

tmp.put("a", "aaa");
tmp.put("b", "bbb");
tmp.put("c", "ccc");

tmp.put("d", "cdc");
Iterator<String> iterator_2 =
tmp.keySet().iterator();
while (iterator_2.hasNext()) {
Object key =
iterator_2.next();
System.out.println("tmp.get(key) is :" + tmp.get(key));

}
}
}

運行結果如下：
map.get(key) is :ddd

map.get(key) is :bbb
map.get(key) is :ccc
map.get(key) is :aaa

tab.get(key) is :bbb
tab.get(key) is :aaa
tab.get(key) is :ddd

tab.get(key) is :ccc
tmp.get(key) is :aaa
tmp.get(key) is :bbb

tmp.get(key) is :ccc
tmp.get(key) is :cdc

HashMap的結果是沒有排序的，而TreeMap輸出的結果是排好序的。
下面就要進入本文的主題了。先舉個例子說明一下怎樣使用HashMap:

復制代碼
代碼如下:

import java.util.*;
public class Exp1 {

public static void main(String[] args){
HashMap h1=new HashMap();

Random r1=new Random();
for (int i=0;i<1000;i++){
Integer t=new
Integer(r1.nextInt(20));
if (h1.containsKey(t))

((Ctime)h1.get(t)).count++;
else
h1.put(t, new Ctime());
}

System.out.println(h1);
}
}
class Ctime{
int count=1;

public String toString(){
return Integer.toString(count);
}
}

在HashMap中通過get()來獲取value，通過put()來插入value，ContainsKey()則用來檢驗對象是否已經存在。可以看出，和ArrayList的操作相比，HashMap除了通過key索引其內容之外，別的方面差異並不大。

前面介紹了，HashMap是基於HashCode的，在所有對象的超類Object中有一個HashCode()方法，但是它和equals方法一樣，並不能適用於所有的情況，這樣我們就需要重寫自己的HashCode()方法。下面就舉這樣一個例子：

復制代碼
代碼如下:

import java.util.*;
public class Exp2 {

public static void main(String[] args){
HashMap h2=new HashMap();

for (int i=0;i<10;i++)
h2.put(new Element(i), new Figureout());

System.out.println("h2:");
System.out.println("Get the result for
Element:");
Element test=new Element(5);
if (h2.containsKey(test))

System.out.println((Figureout)h2.get(test));
else

System.out.println("Not found");
}
}
class Element{
int
number;
public Element(int n){
number=n;
}
}
class
Figureout{
Random r=new Random();
boolean
possible=r.nextDouble()>0.5;
public String toString(){
if (possible)

return "OK!";
else
return "Impossible!";
}
}

在這個例子中，Element用來索引對象Figureout,也即Element為key，Figureout為value。在Figureout中隨機生成一個浮點數，如果它比0.5大，列印"OK!"，否則列印"Impossible!"。之後查看Element(3)對應的Figureout結果如何。

結果卻發現，無論你運行多少次，得到的結果都是"Not found"。也就是說索引Element(3)並不在HashMap中。這怎麼可能呢？

原因得慢慢來說：Element的HashCode方法繼承自Object，而Object中的HashCode方法返回的HashCode對應於當前的地址，也就是說對於不同的對象，即使它們的內容完全相同，用HashCode（）返回的值也會不同。這樣實際上違背了我們的意圖。因為我們在使用
HashMap時，希望利用相同內容的對象索引得到相同的目標對象，這就需要HashCode()在此時能夠返回相同的值。在上面的例子中，我們期望 new
Element(i) (i=5)與
Elementtest=newElement(5)是相同的，而實際上這是兩個不同的對象，盡管它們的內容相同，但它們在內存中的地址不同。因此很自然的，上面的程序得不到我們設想的結果。下面對Element類更改如下：

復制代碼
代碼如下:

class Element{
int number;
public
Element(int n){
number=n;
}
public int hashCode(){
return
number;
}
public boolean equals(Object o){
return (o instanceof
Element) && (number==((Element)o).number);
}
}

在這里Element覆蓋了Object中的hashCode()和equals()方法。覆蓋hashCode()使其以number的值作為
hashcode返回，這樣對於相同內容的對象來說它們的hashcode也就相同了。而覆蓋equals()是為了在HashMap判斷兩個key是否相等時使結果有意義（有關重寫equals()的內容可以參考我的另一篇文章《重新編寫Object類中的方法》）。修改後的程序運行結果如下：

h2:
Get the result for Element:
Impossible!

請記住：如果你想有效的使用HashMap，你就必須重寫在其的HashCode()。
還有兩條重寫HashCode()的原則：

[list=1]

不必對每個不同的對象都產生一個唯一的hashcode，只要你的HashCode方法使get()能夠得到put()放進去的內容就可以了。即"不為一原則"。

生成hashcode的演算法盡量使hashcode的值分散一些，不要很多hashcode都集中在一個范圍內，這樣有利於提高HashMap的性能。即"分散原則"。至於第二條原則的具體原因，有興趣者可以參考Bruce
Eckel的《Thinking in Java》，在那裡有對HashMap內部實現原理的介紹，這里就不贅述了。

掌握了這兩條原則，你就能夠用好HashMap編寫自己的程序了。不知道大家注意沒有，java.lang.Object中提供的三個方法：clone()，equals()和hashCode()雖然很典型，但在很多情況下都不能夠適用，它們只是簡單的由對象的地址得出結果。這就需要我們在自己的程序中重寫它們，其實java類庫中也重寫了千千萬萬個這樣的方法。利用面向對象的多態性——覆蓋，Java的設計者很優雅的構建了Java的結構，也更加體現了Java是一門純OOP語言的特性。

❺ 紅黑樹和平衡二叉樹 區別

紅黑樹和平衡二叉樹的主要區別如下：
平衡二叉樹（AVL）樹是嚴格的平衡二叉樹，平衡條件必須滿足（所有節點的左右子樹高度差不超過1）。不管我們是執行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉來保持平衡，而的英文旋轉非常耗時的。所以平衡二叉樹（AVL）適合用於插入與刪除次數比較少，但查找多的情況。
紅黑樹在二叉查找樹的基礎上增加了著色和相關的性質使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復雜度最壞為O(log
n)。所以紅黑樹適用於搜索，插入，刪除操作較多的情況。
(5)java紅黑樹演算法擴展閱讀：
平衡二叉樹在Windows
NT內核中廣泛存在。
紅黑樹的應用：
1、在C
++的STL中，地圖和集都是用紅黑樹實現的；
2、著名的Linux的的進程調度完全公平調度程序，用紅黑樹管理進程式控制制塊，進程的虛擬內存區域都存儲在一顆紅黑樹上，每個虛擬地址區域都對應紅黑樹的一個節點，左指針指向相鄰的地址虛擬存儲區域，右指針指向相鄰的高地址虛擬地址空間；
3、IO多路復用的epoll的的的實現採用紅黑樹組織管理的sockfd，以支持快速的增刪改查；
4、Nginx的的的中用紅黑樹管理定時器，因為紅黑樹是有序的，可以很快的得到距離當前最小的定時器；
5、Java中的TreeMap中的實現。
參考資料：
網路-平衡二叉樹
網路-紅黑樹

❻ Java數據結構與演算法有哪些

《Java數據結構和演算法》（第2版）介紹了計算機編程中使用的數據結構和演算法，對於在計算機應用中如何操作和管理數據以取得最優性能提供了深入淺出的講解。全書共分為15章，分別講述了基本概念、數組、簡單排序、堆和隊列、鏈表、遞歸、進階排序、二叉樹、紅黑樹、哈希表及圖形等知識。附錄中則提供了運行專題Applet和常式、相關書籍和問題解答。《Java數據結構和演算法》（第2版）提供了學完一門編程語言後進一步需要知道的知識。本書所涵蓋的內容通常作為大學或學院中計算機系二年級的課程，在學生掌握了編程的基礎後才開始本書的學習。

❼ java的monitor機制中,為什麼阻塞隊列用list等待隊列用set

java阻塞隊列應用於生產者消費者模式、消息傳遞、並行任務執行和相關並發設計的大多數常見使用上下文。

BlockingQueue在Queue介面基礎上提供了額外的兩種類型的操作，分別是獲取元素時等待隊列變為非空和添加元素時等待空間變為可用。

BlockingQueue新增操作的四種形式：

3.2.1.3 HashMap類

對Map類的另外一個實現是HashMap。HashMap使用Hash表數據結構。HashMap假定哈希函數能夠將元素適當的分布在各桶之間，提供一種接近O(1)的查詢和更新操作。但是如果需要對集合進行迭代，則與HashMap的容量和桶的大小有關，因此HashMap的迭代效率不會很高（尤其是你為HashMap設置了較大的容量時）。

與HashMap性能有影響的兩個參數是，初始容量和載入因子。容量是哈希表中桶的數量，初始容量是哈希表在創建時的容量。載入因子是哈希表在容器容量被自動擴充之前，HashMap能夠達到多滿的一種程度。當hash表中的條目數超出了載入因子與當前容量的乘積時，Hash表需要進行rehash操作，此時Hash表將會擴充為以前兩倍的桶數，這個擴充過程需要進行完全的拷貝工作，效率並不高，因此應當盡量避免。合理的設置Hash表的初始容量和載入因子會提高Hash表的性能。HashMap自身不是線程安全的，可以通過Collections的synchronizedMap方法對HashMap進行包裝。

3.2.1.4 ConcurrentHashMap類

ConcurrentHashMap類實現了ConcurrentMap介面，並提供了與HashMap相同的規范和功能。實際上Hash表具有很好的局部可操作性，因為對Hash表的更新操作僅會影響到具體的某個桶（假設更新操作沒有引發rehash），對全局並沒有顯著影響。因此ConcurrentHashMap可以提供很好的並發處理能力。可以通過concurrencyLevel的設置，來控制並發工作線程的數目（默認為16），合理的設置這個值，有時很重要，如果這個值設置的過高，那麼很有可能浪費空間和時間，使用的值過低，又會導致線程的爭用，對數量估計的過高或過低往往會帶來明顯的性能影響。最好在創建ConcurrentHashMap時提供一個合理的初始容量，畢竟rehash操作具有較高的代價。

3.2.2 ConcurrentSkipListSet類

實際上Set和Map從結構來說是很像的，從底層的演算法原理分析，Set和Map應當屬於同源的結構。所以Java也提供了TreeSet和ConcurrentSkipListSet兩種SortedSet，分別適合於非多線程（或低並發多線程）和多線程程序使用。具體的演算法請參考前述的Map相關介紹，這里不在累述。

3.2.3 CopyOnWriteArrayList類

CopyOnWriteArrayList是ArrayList的一個線程安全的變體，其中對於所有的可變操作都是通過對底層數組進行一次新的復制來實現的。

由於可變操作需要對底層的數據進行一次完全拷貝，因此開銷一般較大，但是當遍歷操作遠遠多於可變操作時，此方法將會更有效，這是一種被稱為「快照」的模式，數組在迭代器生存期內不會發生更改，因此不會產生沖突。創建迭代器後，迭代器不會反映列表的添加、移除或者更改。不支持在迭代器上進行remove、set和add操作。CopyOnWriteArraySet與CopyOnWriteArrayList相似，只不過是Set類的一個變體。

3.2.3 Collections提供的線程安全的封裝

Collections中提供了synchronizedCollection、synchronizedList、synchronizedMap、synchronizedSet、synchronizedSortedMap、synchronizedSortedMap等方法可以完成多種集合的線程安全的包裝，如果在並發度不高的情況下，可以考慮使用這些包裝方法，不過由於Concurrent相關的類的出現，已經不這么提倡使用這些封裝了，這些方法有些人稱他們為過時的線程安全機制。

3.2.4簡單總結

提供線程安全的集合簡單概括分為三類，首先，對於並發性要求很高的需求可以選擇以Concurrent開頭的相應的集合類，這些類主要包括：ConcurrentHashMap、ConcurrentLinkedQueue、ConcurrentSkipListMap、ConcurrentSkipSet。其次對於可變操作次數遠遠小於遍歷的情況，可以使用CopyOnWriteArrayList和CopyOnWriteArraySet類。最後，對於並發規模比較小的並行需求可以選擇Collections類中的相應方法對已有集合進行封裝。

此外，本章還對一些集合類的底層實現進行簡單探討，對底層實現的了解有利於對何時使用何種方式作出正確判斷。希望大家能夠將涉及到原理（主要有循環隊列、堆、HashMap、紅黑樹、SkipList）進行仔細研究，這樣才能更深入了解Java為什麼這樣設計類庫，在什麼情況使用，應當如何使用。