treemap是常用的排序樹，本文主要介紹treemap中，類的注釋中對treemap的介紹。代碼如下。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
/** * a red-black tree based {@link navigablemap} implementation. * the map is sorted according to the {@linkplain comparable natural * ordering} of its keys, or by a {@link comparator} provided at map * creation time, depending on which constructor is used. * <p>this implementation provides guaranteed log(n) time cost for the * {@code containskey}, {@code get}, {@code put} and {@code remove} * operations. algorithms are adaptations of those in cormen, leiserson, and * rivest's <em>introduction to algorithms</em>. * <p>note that the ordering maintained by a tree map, like any sorted map, and * whether or not an explicit comparator is provided, must be <em>consistent * with {@code equals}</em> if this sorted map is to correctly implement the * {@code map} interface. (see {@code comparable} or {@code comparator} for a * precise definition of <em>consistent with equals</em>.) this is so because * the {@code map} interface is defined in terms of the {@code equals} * operation, but a sorted map performs all key comparisons using its {@code * compareto} (or {@code compare}) method, so two keys that are deemed equal by * this method are, from the standpoint of the sorted map, equal. the behavior * of a sorted map <em>is</em> well-defined even if its ordering is * inconsistent with {@code equals}; it just fails to obey the general contract * of the {@code map} interface. * <p><strong>note that this implementation is not synchronized.</strong> * if multiple threads access a map concurrently, and at least one of the * threads modifies the map structurally, it <em>must</em> be synchronized * externally. (a structural modification is any operation that adds or * deletes one or more mappings; merely changing the value associated * with an existing key is not a structural modification.) this is * typically accomplished by synchronizing on some object that naturally * encapsulates the map. * if no such object exists, the map should be "wrapped" using the * {@link collections#synchronizedsortedmap collections.synchronizedsortedmap} * method. this is best done at creation time, to prevent accidental * unsynchronized access to the map: <pre> * sortedmap m = collections.synchronizedsortedmap(new treemap(...));</pre> * <p>the iterators returned by the {@code iterator} method of the collections * returned by all of this class's "collection view methods" are * <em>fail-fast</em>: if the map is structurally modified at any time after * the iterator is created, in any way except through the iterator's own * {@code remove} method, the iterator will throw a {@link * concurrentmodificationexception}. thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than risking * arbitrary, non-deterministic behavior at an undetermined time in the future. * <p>note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. fail-fast iterators * throw {@code concurrentmodificationexception} on a best-effort basis. * therefore, it would be wrong to write a program that depended on this * exception for its correctness: <em>the fail-fast behavior of iterators * should be used only to detect bugs.</em> * <p>all {@code map.entry} pairs returned by methods in this class * and its views represent snapshots of mappings at the time they were * produced. they do <strong>not</strong> support the {@code entry.setvalue} * method. (note however that it is possible to change mappings in the * associated map using {@code put}.) * <p>this class is a member of the * <a href="{@docroot}/../technotes/guides/collections/index.html" rel="external nofollow" > * java collections framework</a>. * @param <k> the type of keys maintained by this map * @param <v> the type of mapped values * @author josh bloch and doug lea * @see map * @see hashmap * @see hashtable * @see comparable * @see comparator * @see collection * @since 1.2 **/ |
這是一個基于紅黑樹的可導航的實現。這個map基于key的可比較的自然順序，或者基于在map創建時提供的comparator的順序來存儲元素。
這個實現提供可保證的log(n)的時間復雜度來完成containskey，get，put和remove操作。
需要注意到這一點，不管是否顯式提供了排序器，如果這個排序map想要正確實現map接口，tree map維護的順序必須和equals保持一致，就像任何排序map那樣。之所以會這樣，是因為map接口是根據equals操作來定義的，但是排序map進行所有key的比較時使用的是他們的compareto方法，所以，從排序map的觀點來看，被這個方法認為相等的兩個key，才是相等的。盡管如果它的順序和equals不一致，排序map的行為也是正常的，它只是沒有遵守map接口的通常約定。
請注意這個實現是非同步的。如果多個線程并發訪問一個treemap，并且至少有一個線程修改結構，必須進行外部同步。這個通常是通過在包含這個map的對象上進行同步來實現的。如果沒有這樣的對象，那么這個map需要用collections.synchronizedsortedmap方法包裝一下。最好是在創建map時就這樣做，以防止意外非同步訪問這個map。代碼如下sortedmap m = collections.synchronizedsortedmap(new treemap(...));
所有這個類的集合視角方法返回的集合的iterator方法返回的迭代器都是fast-fail的：如果迭代器創建后的任何時間map發生了結構性改變，除了通過迭代器的刪除方法外，迭代器都會拋出同步修改異常。于是，面對同步修改時，迭代器會迅速干凈的失敗，而不是冒著在未來的不確定的時間發生不一致或無法確定的行為的風險。
這個類和它的視圖的方法返回的map.entry對代表了他們被創建時的快照。他們不支持entry.setvalue方法。
這個類是java集合框架的一個成員。
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對服務器之家的支持。如果你想了解更多相關內容請查看下面相關鏈接
原文鏈接：https://blog.csdn.net/li_canhui/article/details/85253951
