Java Tutorial/Collections/TreeMap

Материал из Java эксперт
Перейти к: навигация, поиск

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

  1. public TreeMap(): creates an empty TreeMap
  2. public TreeMap(Map map): the standard copy constructor
  3. public TreeMap(Comparator comp): defines a custom sort order
  4. 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