注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

民主与科学

独立之人格,自由之思想

 
 
 

日志

 
 

LinkedHashMap简介  

2010-08-09 16:01:55|  分类: JAVA集合容器 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 public class LinkedHashMap<K,V>
 extends HashMap<K,V>
 implements Map<K,V>
 LinkedHashMap是Map 接口的哈希表和链接列表实现,具有可预知的迭代顺序。
 此实现与 HashMap 的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。

 此链接列表定义了迭代顺序,该迭代顺序通常就是将键插入到映射中的顺序(插入顺序)。
 注意,如果在映射中重新插入 键,则插入顺序不受影响。
 (如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true,则调用时会将键 k 重新插入到映射 m 中。)
 此实现可以让客户避免未指定的、由 HashMap(及 Hashtable)所提供的通常为杂乱无章的排序工作,
 同时无需增加与 TreeMap 相关的成本。使用它可以生成一个与原来顺序相同的映射副本,而与原映射的实现无关:
      void foo(Map m) {
          Map copy = new LinkedHashMap(m);
          ...
      }

 如果模块通过输入得到一个映射,复制这个映射,
 然后返回由此副本确定其顺序的结果,这种情况下这项技术特别有用。(客户通常期望返回的内容与其出现的顺序相同。)
 提供特殊的构造方法来创建链接哈希映射,该哈希映射的迭代顺序就是最后访问其条目的顺序,
 从近期访问最少到近期访问最多的顺序(访问顺序)。
这种映射很适合构建 LRU 缓存。
 调用 put 或 get 方法将会访问相应的条目(假定调用完成后它还存在)。
 putAll 方法以指定映射的条目集合迭代器提供的键-值映射关系的顺序,为指定映射的每个映射关系生成一个条目访问。
 任何其他方法均不生成条目访问。特别是,collection 视图上的操作不影响底层映射的迭代顺序。
 此类提供所有可选的 Map 操作,并且允许 null 元素。与 HashMap 一样,它可以为基本操作(add、contains 和 remove)提供稳定的性能,
 假定哈希函数将元素正确分布到桶中。由于增加了维护链接列表的开支,其性能很可能比 HashMap 稍逊一筹,不过这一点例外:
 LinkedHashMap的collection 视图迭代所需时间与映射的大小成比例。HashMap 迭代时间很可能开支较大,因为它所需要的时间与其容量 成比例。
 链接的哈希映射具有两个影响其性能的参数:初始容量和加载因子。它们的定义与 HashMap 极其相似。
 要注意,为初始容量选择非常高的值对此类的影响比对 HashMap 要小,因为此类的迭代时间不受容量的影响。
 注意,此实现不是同步的。如果多个线程同时访问链接的哈希映射,而其中至少一个线程从结构上修改了该映射,
 则它必须 保持外部同步。这一般通过对自然封装该映射的对象进行同步操作来完成。
 如果不存在这样的对象,则应该使用 Collections.synchronizedMap 方法来“包装”该映射。
 最好在创建时完成这一操作,以防止意外的非同步访问:
     Map m = Collections.synchronizedMap(new LinkedHashMap(...));
 结构修改是指添加或删除一个或多个映射关系,或者在按访问顺序链接的哈希映射中影响迭代顺序的任何操作。
 在按插入顺序链接的哈希映射中,仅更改与映射中已包含键关联的值不是结构修改。
 在按访问顺序链接的哈希映射中,仅利用 get 查询映射不是结构修改。)
 Collection(由此类的所有 collection 视图方法所返回)的 iterator 方法返回的迭代器都是快速失败 的:
 在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器自身的移除方法,其他任何时间任何方式的修改,
 迭代器都将抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,
 而不冒将来不确定的时间任意发生不确定行为的风险。
 注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。
 快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序的方式是错误的,
 正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。
 注意1:该实现不是同步的,不是线程安全的。
 注意2:关于哈希映射的概念初始容量和加载因子可参阅《HashMap

 注意3public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)
    构造一个带指定初始容量、加载因子和排序模式的空 LinkedHashMap 实例。
    参数:
        initialCapacity - 初始容量。
        loadFactor - 加载因子。
        accessOrder - 排序模式 - 对于访问顺序,为 true;对于插入顺序,则为 false。 
   这里的“访问”包含了get(),put().
  注意4:如果重复插入一个元素。则后面一个会覆盖前面一个。
  对于按照插入顺序(accessOrder为false)来排序的,是以前面一个插入顺序为准。
  可以参照实例2。
  可以重写 removeEldestEntry(Map.Entry) 方法,以便在将新映射关系添加到映射时自动移除旧的映射关系
protected boolean removeEldestEntry(Map.Entry<K,V> eldest)
    此方法用以提供在每次添加新条目时移除最旧条目的策略。如果需要删除此时最旧的条目,则返回 true。在将新条目插入到映射后,               put 和 putAll 将调用此方法。如果映射表示缓存,则此方法非常有用:
    它允许映射通过删除旧条目来减少内存损耗。
    示例用法:此重写允许映射增加到 100 个条目,然后每次添加新条目时删除最旧的条目,
    始终维持 100 个条目的稳定状态。
         private static final int MAX_ENTRIES = 100;
         protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > MAX_ENTRIES;
         }

    此方法通常不以任何方式修改映射,相反允许映射在其返回值的指引下进行自我修改。
    使用此方法直接修改映射是 允许的,但是如果它执行了此操作,则一定 返回 false(表示该映射不应进行任何进一步的修改)。
    在此方法中修改映射后是否返回 true 是不确定的。
    此实现仅返回 false(这样,此映射的行为将类似于正常映射,即永远不能移除最旧的元素)。 
 removeEldestEntry的目的主要是提供接口。
 在JDK中1.6中的源码如下

     protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        
return false;
    }
    
void addEntry(int hash, K key, V value, int bucketIndex) {
        createEntry(hash, key, value, bucketIndex);
      
  // Remove eldest entry if instructed, else grow capacity if appropriate
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        } else {
            if (size >= threshold)
                resize(2 * table.length);
        }
    }

实例1

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.ConcurrentLinkedQueue;
public class Test {
 /**
  * @param args
  */

 public static void main(String[] args) {
  ConcurrentLinkedQueue<Integer> queue=new ConcurrentLinkedQueue<Integer> ();
  // TODO Auto-generated method stub
  for(int i=0;i<1;i++)
   new Thread(new ThreadProducer(queue)).start();
  for(int i=0;i<1;i++)
   new Thread(new ThreadConsumer(queue)).start();
 }
}

class CacheLRU<K,V> extends LinkedHashMap<K,V>
{
    private static final int MAX_ENTRIES = 800;
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
       return size() > MAX_ENTRIES;
    }
}

class Image
{
 byte[] data;
 Image(byte indexData[])
 {
  data=new byte[indexData.length*4];
 }
}

class ThreadProducer implements Runnable
{
 ThreadProducer(ConcurrentLinkedQueue<Integer> queue)
 {
  this.queue=queue;
  blRun=true;
 }
 ConcurrentLinkedQueue<Integer> queue;
 static int cnt=0;
 static boolean blRun=true;
 public void run()
 {
  int val=0;
  Random random =new Random(System.currentTimeMillis());
  while(blRun)
  {
   cnt=(cnt+1)&0xFFFFFFFF;
   try{
    val=random.nextInt()%1000;
    if(val<0)
     val=-val;
    if(cnt>10000)
    {
     val=-1;
     blRun=false;
    }
    queue.add(new Integer(val));
   Thread.sleep(1);
   }catch(InterruptedException e)
   {
    e.printStackTrace();
   }
  }
 }
}

class ThreadConsumer implements Runnable
{
 LinkedHashMap<Integer,Image> cache=new CacheLRU<Integer,Image>();
 ConcurrentLinkedQueue<Integer> queue;
 static int cacheSuccessCount=0;
 static int allCount=0;
 static boolean blRun=true;
 
ThreadConsumer(ConcurrentLinkedQueue<Integer> queue)
 {
  this.queue=queue;
  blRun=true;
 }
 
public void run()
 {
  Integer key;
  Image img;
  
while(blRun)
  {
  
 try{
    if(!queue.isEmpty())
    {
     key=queue.poll();
     if(key.intValue()==-1)
     {
      blRun=false;
      break;
     }
     System.out.println("read image "+key);
     img=cache.get(key);
     if(img==null)
     {
      byte imgIndexData[]=new byte[10];
      img=new Image(imgIndexData);
      System.out.println("load image");
      cache.put(key, img);
     }
     else
     {
      System.out.println("use the  cache image");
      cacheSuccessCount++;
     }
     allCount++;
    }
   Thread.sleep(1);
   }catch(InterruptedException e)
   {
    e.printStackTrace();
   }
  }
  System.out.println("cache size:"+cache.size());
  System.out.println("total:"+allCount+" success count:"+cacheSuccessCount);
  System.out.println("success rate:"+cacheSuccessCount*100/allCount);
 }
}

实例2

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.ConcurrentLinkedQueue;
public class Test {
 /**
  * @param args
  */

 public static void main(String[] args) {
  LinkedHashMap<Integer,People> map=new LinkedHashMap<Integer,People>(16,(float) 0.75,false);
  People p1=new People("robin",1,28);
  People p2=new People("robin",2,29);
  People p3=new People("harry",3,30);
  map.put(new Integer(100), p1);
  map.put(new Integer(1), p3);
  map.put(new Integer(2), null);
  map.put(new Integer(100), p2);

  for(People p:map.values())
  {
   System.out.println("people:"+p);
  }
 }
}
class People{
 String name;
 int id;
 int age;
 public People(String name,int id)
 {
  this(name,id,0);
 }
 public People(String name,int id,int age)
 {
  this.name=name;
  this.id=id;
  this.age=age;
 }
 public String toString()
 {
  return id+name+age;
 }
 public boolean equals(Object o)
 {
  if(o==null)
   return false;
  if(!(o instanceof People))
   return false;
  People p=(People)o;
  boolean res=name.equals(p.name);
  if(res)
   System.out.println("name "+name+" is double");
  else
   System.out.println(name+" vS "+p.name);
  return res;
 }
 public int hashCode()
 {
  return name.hashCode();
 }
}

结束
  评论这张
 
阅读(2475)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017