Java Tutorial/Collections/TreeMap
Содержание
- 1 Cache Map
- 2 Check if a particular key exists in TreeMap
- 3 Check if a particular value exists in TreeMap
- 4 Get Head Map from TreeMap
- 5 Get lowest and highest key stored in TreeMap
- 6 Get Set view of Keys from TreeMap
- 7 Get Sub Map from TreeMap
- 8 Get Synchronized Map from TreeMap
- 9 Get Tail Map from TreeMap
- 10 Get TreeMap Size
- 11 Iterate through the values of TreeMap
- 12 Remove all values from TreeMap
- 13 Remove value from TreeMap
- 14 TreeMap Class
- 15 TreeMap<Integer, User defined class>
- 16 Viewing Sub Maps
- 17 Working with End Points
Cache Map
<source lang="java">
/*******************************************************************************
* Copyright (c) 2007, 2008 IBM Corporation and Others * All rights reserved. This program and the accompanying materials * are made available under the terms of the Eclipse Public License v1.0 * which accompanies this distribution, and is available at * http://www.eclipse.org/legal/epl-v10.html * * Contributors: * Hisashi MIYASHITA - initial API and implementation * Kentarou FUKUDA - initial API and implementation *******************************************************************************/
import java.util.Iterator; import java.util.LinkedList; import java.util.NoSuchElementException; import java.util.SortedMap; import java.util.TreeMap; /**
* Utility class for cache map. */
public class CacheMap extends TreeMap<String, Object> {
private static final long serialVersionUID = 6681131647931821052L; private final int maxSize; private final int evictSize; private final LinkedList<Object> accessList = new LinkedList<Object>(); /** * Constructor of cache map. If the map exceed the maximum size, the * key/value sets will be removed from map based on specified evict size. * * @param maxSize * maximum size of the map * @param evictSize * number of evict object */ public CacheMap(int maxSize, int evictSize) { this.maxSize = maxSize; this.evictSize = evictSize; } private void evict() { Iterator<Object> it = accessList.iterator(); for (int i = 0; i < evictSize; i++) { if (!it.hasNext()) return; Object key = it.next(); this.remove(key); it.remove(); } } private int searchAccessList(Object key) { return accessList.indexOf(key); } private void accessEntry(Object key) { int idx = searchAccessList(key); if (idx >= 0) { accessList.remove(idx); } accessList.add(key); } public Object put(String key, Object val) { if (size() >= maxSize) evict(); accessEntry(key); return super.put(key, val); } public Object get(Object key) { accessEntry(key); return super.get(key); } /** * Search a key that starts with the specified prefix from the map, and * return the value corresponding to the key. * * @param prefix * target prefix * @return the value whose key starts with prefix, or null if not available */ public Object matchStartsWith(String prefix) { SortedMap<String, Object> smap = super.tailMap(prefix); Object okey; try { okey = smap.firstKey(); } catch (NoSuchElementException e) { return null; } if (!(okey instanceof String)) return null; String key = (String) okey; // System.err.println("MSW:" + key + " / " + prefix); if (!key.startsWith(prefix)) return null; return super.get(key); }
}</source>
Check if a particular key exists in TreeMap
<source lang="java">
import java.util.TreeMap; public class Main {
public static void main(String[] args) { TreeMap<String, String> treeMap = new TreeMap<String,String>(); treeMap.put("1", "One"); treeMap.put("2", "Two"); treeMap.put("3", "Three"); System.out.println(treeMap.containsKey("1")); }
}</source>
Check if a particular value exists in TreeMap
<source lang="java">
import java.util.TreeMap; public class Main {
public static void main(String[] args) { TreeMap<String, String> treeMap = new TreeMap<String, String>(); treeMap.put("1", "One"); treeMap.put("2", "Two"); treeMap.put("3", "Three"); System.out.println(treeMap.containsValue("Three")); }
}</source>
Get Head Map from TreeMap
<source lang="java">
import java.util.SortedMap; import java.util.TreeMap; public class Main {
public static void main(String[] args) { TreeMap<String,String> treeMap = new TreeMap<String,String>(); treeMap.put("1", "One"); treeMap.put("3", "Three"); treeMap.put("2", "Two"); treeMap.put("5", "Five"); treeMap.put("4", "Four"); SortedMap sortedMap = treeMap.headMap("3"); System.out.println("Head Map Contains : " + sortedMap); }
}</source>
Get lowest and highest key stored in TreeMap
<source lang="java">
import java.util.TreeMap; public class Main {
public static void main(String[] args) { TreeMap<String, String> treeMap = new TreeMap<String, String>(); treeMap.put("1", "One"); treeMap.put("2", "Two"); treeMap.put("3", "Three"); treeMap.put("4", "Four"); treeMap.put("5", "Five"); System.out.println("Lowest key: " + treeMap.firstKey()); System.out.println("Highest key: " + treeMap.lastKey()); }
}</source>
Get Set view of Keys from TreeMap
<source lang="java">
import java.util.Iterator; import java.util.TreeMap; import java.util.Set; public class Main {
public static void main(String[] args) { TreeMap<String, String> treeMap = new TreeMap<String, String>(); treeMap.put("1", "One"); treeMap.put("3", "Three"); treeMap.put("2", "Two"); Set st = treeMap.keySet(); Iterator itr = st.iterator(); while (itr.hasNext()){ System.out.println(itr.next()); } st.remove("1"); System.out.println(treeMap.containsKey("1")); }
}</source>
Get Sub Map from TreeMap
<source lang="java">
import java.util.SortedMap; import java.util.TreeMap; public class Main {
public static void main(String[] args) { TreeMap<String, String> treeMap = new TreeMap<String, String>(); treeMap.put("1", "One"); treeMap.put("2", "Two"); treeMap.put("3", "Three"); treeMap.put("4", "Four"); treeMap.put("5", "Five"); SortedMap sortedMap = treeMap.subMap("2", "5"); System.out.println("SortedMap Contains : " + sortedMap); }
}</source>
Get Synchronized Map from TreeMap
<source lang="java">
import java.util.Collections; import java.util.Map; import java.util.TreeMap; public class Main {
public static void main(String[] args) { TreeMap treeMap = new TreeMap(); Map map = Collections.synchronizedMap(treeMap); }
}</source>
Get Tail Map from TreeMap
<source lang="java">
import java.util.SortedMap; import java.util.TreeMap; public class Main {
public static void main(String[] args) { TreeMap<String, String> treeMap = new TreeMap<String,String>(); treeMap.put("1", "One"); treeMap.put("3", "Three"); treeMap.put("2", "Two"); treeMap.put("5", "Five"); treeMap.put("4", "Four"); SortedMap sortedMap = treeMap.tailMap("2"); System.out.println("Tail Map Contains : " + sortedMap); }
}</source>
Get TreeMap Size
<source lang="java">
import java.util.TreeMap; public class Main {
public static void main(String[] args) { TreeMap<String, String> treeMap = new TreeMap<String, String>(); System.out.println("Size of TreeMap : " + treeMap.size()); treeMap.put("1", "One"); treeMap.put("2", "Two"); treeMap.put("3", "Three"); System.out.println("Size of TreeMap after addition : " + treeMap.size()); treeMap.remove("2"); System.out.println("Size of TreeMap after removal : " + treeMap.size()); }
}</source>
Iterate through the values of TreeMap
<source lang="java">
import java.util.Collection; import java.util.Iterator; import java.util.TreeMap; public class Main {
public static void main(String[] args) { TreeMap<String, String> treeMap = new TreeMap<String,String>(); treeMap.put("1", "One"); treeMap.put("2", "Two"); treeMap.put("3", "Three"); Collection c = treeMap.values(); Iterator itr = c.iterator(); while (itr.hasNext()){ System.out.println(itr.next()); } }
}</source>
Remove all values from TreeMap
<source lang="java">
import java.util.TreeMap; public class Main {
public static void main(String[] args) { TreeMap<String,String> treeMap = new TreeMap<String,String>(); treeMap.put("1", "One"); treeMap.put("2", "Two"); treeMap.put("3", "Three"); treeMap.clear(); System.out.println(treeMap.size()); }
}</source>
Remove value from TreeMap
<source lang="java">
import java.util.TreeMap; public class Main {
public static void main(String[] args) { TreeMap<String,String> treeMap = new TreeMap<String,String>(); treeMap.put("1", "One"); treeMap.put("2", "Two"); treeMap.put("3", "Three"); Object obj = treeMap.remove("2"); System.out.println(obj + " Removed from TreeMap"); }
}</source>
TreeMap Class
A TreeMap is a map that maintains its keys ordered within a balanced, red-black tree.
Creating a TreeMap
- public TreeMap(): creates an empty TreeMap
- public TreeMap(Map map): the standard copy constructor
- public TreeMap(Comparator comp): defines a custom sort order
- public TreeMap(SortedMap map): accepts a SortedMap for an optimized copy constructor
TreeMap<Integer, User defined class>
<source lang="java">
import java.util.TreeMap; public class ProductDB {
public static void main(String[] args) { TreeMap<Integer, Product> db = new TreeMap<Integer, Product>(); db.put(1000, new Product("D", 350)); db.put(1011, new Product("p", 15.75)); db.put(1102, new Product("M", 8.50)); db.put(2023, new Product("A", 150)); db.put(2034, new Product("T", 9.99)); System.out.println(db.subMap(1000, 1999) + "\n"); System.out.println(db.tailMap(1011) + "\n"); System.out.println(db.headMap(2023)); System.out.println("First key higher than 2034: " + db.higherKey(2034)); System.out.println("First key lower than 2034: " + db.lowerKey(2034)); }
} class Product {
String desc; double price; Product(String desc, double price) { this.desc = desc; this.price = price; } public String toString() { return "Description=" + desc + ", Price=" + price; }
}</source>
Viewing Sub Maps
<source lang="java">
SortedSet headMap(Object toKey) SortedSet tailMap(Object fromKey) SortedSet subMap(Object fromKey, Object toKey)</source>
{key1=value1}
Working with End Points
The firstKey() and lastKey() methods of TreeMap let you quickly access the keys at the end of the map.
If you need to traverse a map backwards(keep getting the last key and the head map before it):
<source lang="java">
import java.util.TreeMap; public class MainClass {
public static void main(String[] a) { TreeMap map = new TreeMap(); map.put("key1", "value1"); map.put("key2", "value2"); map.put("key3", "value3"); if (!map.isEmpty()) { Object last = map.lastKey(); boolean first = true; do { if (!first) { System.out.print(", "); } System.out.print(last); last = map.headMap(last).lastKey(); first = false; } while (last != map.firstKey()); System.out.println(); } }
}</source>
key3, key2