LinkedHashMap ： 记录插入顺序的Map

Dong - 2015年6月27日

今日做一个曲线图，用到map存储数据，开始习惯性的使用了hashmap，结果发现在计算出来结果展现的时候，日期并没有按照预计的顺序排列。比如，统计出来的数据是20150626和20150627两天的，真正在页面上展现的时候，反而是20150626在后面。
经过仔细观察，发现数据对应并没有错，也就是说，是一开始用来存储以天为key值的节点数据的时候顺序是混乱的，在遍历的时候并没有按照存入的顺序进行遍历。

由于日期与数据的列表时分开存储的，计算完成之后再按照日期排序的方法不可取。印象里linkedhashmap和treemap是有顺序的，从网上找资料确认一下，发现，linkedhashmap是可以保留存入的元素的顺序的，遍历的时候是按照存入的顺序遍历，这个符合我的要求。treemap是有个顺序，不过是默认按照key值进行排序，而非存储时候的顺序。但由于我在获取数据列表的时候已经按照时间排序，不需要再次进行排序，因此没有选择用treemap。

LinkedHashMap的实现整理如下：

参考文档地址《http://www.cnblogs.com/children/archive/2012/10/02/2710624.html》

1. LinkedHashMap概述：

LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。

LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。

 

根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。

默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。  可以重写removeEldestEntry方法返回true值指定插入元素时移除最老的元素。

 

2. LinkedHashMap的实现：

对于LinkedHashMap而言，它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。下面我们来分析LinkedHashMap的源代码：

类结构：

  1. public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V>

 

1) 成员变量：

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。看源代码：

 

  1. //true表示按照访问顺序迭代，false时表示按照插入顺序
  2.  private final boolean accessOrder;
  1. /**
  2.  * 双向链表的表头元素。
  3.  */
  4. private transient Entry<K,V> header;
  6. /**
  7.  * LinkedHashMap的Entry元素。
  8.  * 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用。
  9.  */
  10. private static class Entry<K,V> extends HashMap.Entry<K,V> {
  11.     Entry<K,V> before, after;
  12.     ……
  13. }

HashMap.Entry:

  1. static class Entry<K,V> implements Map.Entry<K,V> {
  2.         final K key;
  3.         V value;
  4.         Entry<K,V> next;
  5.         final int hash;
  7.         Entry(int h, K k, V v, Entry<K,V> n) {
  8.             value = v;
  9.             next = n;
  10.             key = k;
  11.             hash = h;
  12.         }
  13. }

 

2) 初始化：

通过源代码可以看出，在LinkedHashMap的构造方法中，实际调用了父类HashMap的相关构造方法来构造一个底层存放的table数组。如：

  1. public LinkedHashMap(int initialCapacity, float loadFactor) {
  2.     super(initialCapacity, loadFactor);
  3.     accessOrder = false;
  4. }

HashMap中的相关构造方法：

  1. public HashMap(int initialCapacity, float loadFactor) {
  2.     if (initialCapacity < 0)
  3.         throw new IllegalArgumentException(“Illegal initial capacity: “ +
  4.                                            initialCapacity);
  5.     if (initialCapacity > MAXIMUM_CAPACITY)
  6.         initialCapacity = MAXIMUM_CAPACITY;
  7.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  8.         throw new IllegalArgumentException(“Illegal load factor: “ +
  9.                                            loadFactor);
  11.     // Find a power of 2 >= initialCapacity
  12.     int capacity = 1;
  13.     while (capacity < initialCapacity)
  14.         capacity <<= 1;
  16.     this.loadFactor = loadFactor;
  17.     threshold = (int)(capacity * loadFactor);
  18.     table = new Entry[capacity];
  19.     init();
  20. }

我们已经知道LinkedHashMap的Entry元素继承HashMap的Entry，提供了双向链表的功能。在上述HashMap的构造器中，最后会调用init()方法，进行相关的初始化，这个方法在HashMap的实现中并无意义，只是提供给子类实现相关的初始化调用。
LinkedHashMap重写了init()方法，在调用父类的构造方法完成构造后，进一步实现了对其元素Entry的初始化操作。

  1. void init() {
  2.     header = new Entry<K,V>(-1, null, null, null);
  3.     header.before = header.after = header;
  4. }

3) 存储：

LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void recordAccess(HashMap m)   ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。

HashMap.put:

 

  1. public V put(K key, V value) {
  2.         if (key == null)
  3.             return putForNullKey(value);
  4.         int hash = hash(key.hashCode());
  5.         int i = indexFor(hash, table.length);
  6.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  7.             Object k;
  8.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  9.                 V oldValue = e.value;
  10.                 e.value = value;
  11.                 e.recordAccess(this);
  12.                 return oldValue;
  13.             }
  14.         }
  16.         modCount++;
  17.         addEntry(hash, key, value, i);
  18.         return null;
  19.     }

重写方法：

  1. void recordAccess(HashMap<K,V> m) {
  2.             LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
  3.             if (lm.accessOrder) {
  4.                 lm.modCount++;
  5.                 remove();
  6.                 addBefore(lm.header);
  7.             }
  8.         }

 

  1. void addEntry(int hash, K key, V value, int bucketIndex) {
  2.     // 调用create方法，将新元素以双向链表的的形式加入到映射中。
  3.     createEntry(hash, key, value, bucketIndex);
  5.     // 删除最近最少使用元素的策略定义
  6.     Entry<K,V> eldest = header.after;
  7.     if (removeEldestEntry(eldest)) {
  8.         removeEntryForKey(eldest.key);
  9.     } else {
  10.         if (size >= threshold)
  11.             resize(2 * table.length);
  12.     }
  13. }
  1. void createEntry(int hash, K key, V value, int bucketIndex) {
  2.     HashMap.Entry<K,V> old = table[bucketIndex];
  3.     Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
  4.     table[bucketIndex] = e;
  5.     // 调用元素的addBrefore方法，将元素加入到哈希、双向链接列表。
  6.     e.addBefore(header);
  7.     size++;
  8. }
  1. private void addBefore(Entry<K,V> existingEntry) {
  2.     after  = existingEntry;
  3.     before = existingEntry.before;
  4.     before.after = this;
  5.     after.before = this;
  6. }

 

4) 读取：

LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。

HashMap.containsValue:

  1. public boolean containsValue(Object value) {
  2.     if (value == null)
  3.             return containsNullValue();
  5.     Entry[] tab = table;
  6.         for (int i = 0; i < tab.length ; i++)
  7.             for (Entry e = tab[i] ; e != null ; e = e.next)
  8.                 if (value.equals(e.value))
  9.                     return true;
  10.     return false;
  11.     }

 

  1.  /*查找Map中是否包含给定的value，还是考虑到，LinkedHashMap拥有的双链表，在这里Override是为了提高迭代的效率。
  2.  */
  3. public boolean containsValue(Object value) {
  4.         // Overridden to take advantage of faster iterator
  5.         if (value==null) {
  6.             for (Entry e = header.after; e != header; e = e.after)
  7.                 if (e.value==null)
  8.                     return true;
  9.         } else {
  10.             for (Entry e = header.after; e != header; e = e.after)
  11.                 if (value.equals(e.value))
  12.                     return true;
  13.         }
  14.         return false;
  15.     }

 

 

  1. /*该transfer()是HashMap中的实现：遍历整个表的各个桶位，然后对桶进行遍历得到每一个Entry，重新hash到newTable中，
  2.  //放在这里是为了和下面LinkedHashMap重写该法的比较，
  3.  void transfer(Entry[] newTable) {
  4.         Entry[] src = table;
  5.         int newCapacity = newTable.length;
  6.         for (int j = 0; j < src.length; j++) {
  7.             Entry<K,V> e = src[j];
  8.             if (e != null) {
  9.                 src[j] = null;
  10.                 do {
  11.                     Entry<K,V> next = e.next;
  12.                     int i = indexFor(e.hash, newCapacity);
  13.                     e.next = newTable[i];
  14.                     newTable[i] = e;
  15.                     e = next;
  16.                 } while (e != null);
  17.             }
  18.         }
  19.     }
  20.  */
  22.  /**
  23.  *transfer()方法是其父类HashMap调用resize()的时候调用的方法，它的作用是表扩容后，把旧表中的key重新hash到新的表中。
  24.  *这里从写了父类HashMap中的该方法，是因为考虑到，LinkedHashMap拥有的双链表，在这里Override是为了提高迭代的效率。
  25.  */
  26.  void transfer(HashMap.Entry[] newTable) {
  27.    int newCapacity = newTable.length;
  28.    for (Entry<K, V> e = header.after; e != header; e = e.after) {
  29.      int index = indexFor(e.hash, newCapacity);
  30.      e.next = newTable[index];
  31.      newTable[index] = e;
  32.    }
  33.  }

 

  1. public V get(Object key) {
  2.     // 调用父类HashMap的getEntry()方法，取得要查找的元素。
  3.     Entry<K,V> e = (Entry<K,V>)getEntry(key);
  4.     if (e == null)
  5.         return null;
  6.     // 记录访问顺序。
  7.     e.recordAccess(this);
  8.     return e.value;
  9. }
  1. void recordAccess(HashMap<K,V> m) {
  2.     LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
  3.     // 如果定义了LinkedHashMap的迭代顺序为访问顺序，
  4.     // 则删除以前位置上的元素，并将最新访问的元素添加到链表表头。
  5.     if (lm.accessOrder) {
  6.         lm.modCount++;
  7.         remove();
  8.         addBefore(lm.header);
  9.     }
  10. }

 

  1. /**
  2.          * Removes this entry from the linked list.
  3.          */
  4.         private void remove() {
  5.             before.after = after;
  6.             after.before = before;
  7.         }

 

 

  1. /**clear链表，设置header为初始状态*/
  2. public void clear() {
  3.  super.clear();
  4.  header.before = header.after = header;
  5. }

 

 

5) 排序模式：

LinkedHashMap定义了排序模式accessOrder，该属性为boolean型变量，对于访问顺序，为true；对于插入顺序，则为false。

  1. private final boolean accessOrder;

一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。看LinkedHashMap的构造方法，如：

  1. public LinkedHashMap(int initialCapacity, float loadFactor) {
  2.     super(initialCapacity, loadFactor);
  3.     accessOrder = false;
  4. }

这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个LinkedHashMap，并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用下面的构造方法构造LinkedHashMap：

  1. public LinkedHashMap(int initialCapacity,
  2.          float loadFactor,
  3.                      boolean accessOrder) {
  4.     super(initialCapacity, loadFactor);
  5.     this.accessOrder = accessOrder;
  6. }

该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建LRU缓存。LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V> eldest)方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。

 

当有新元素加入Map的时候会调用Entry的addEntry方法，会调用removeEldestEntry方法，这里就是实现LRU元素过期机制的地方，默认的情况下removeEldestEntry方法只返回false表示元素永远不过期。

  1.   /**
  2.     * This override alters behavior of superclass put method. It causes newly
  3.     * allocated entry to get inserted at the end of the linked list and
  4.     * removes the eldest entry if appropriate.
  5.     */
  6.    void addEntry(int hash, K key, V value, int bucketIndex) {
  7.        createEntry(hash, key, value, bucketIndex);
  9.        // Remove eldest entry if instructed, else grow capacity if appropriate
  10.        Entry<K,V> eldest = header.after;
  11.        if (removeEldestEntry(eldest)) {
  12.            removeEntryForKey(eldest.key);
  13.        } else {
  14.            if (size >= threshold)
  15.                resize(2 * table.length);
  16.        }
  17.    }
  19.    /**
  20.     * This override differs from addEntry in that it doesn’t resize the
  21.     * table or remove the eldest entry.
  22.     */
  23.    void createEntry(int hash, K key, V value, int bucketIndex) {
  24.        HashMap.Entry<K,V> old = table[bucketIndex];
  25. Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
  26.        table[bucketIndex] = e;
  27.        e.addBefore(header);
  28.        size++;
  29.    }
  31.    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  32.        return false;
  33.    }

此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。如果用此映射构建LRU缓存，则非常方便，它允许映射通过删除旧条目来减少内存损耗。

例如：重写此方法，维持此映射只保存100个条目的稳定状态，在每次添加新条目时删除最旧的条目。

  1. private static final int MAX_ENTRIES = 100;
  2. protected boolean removeEldestEntry(Map.Entry eldest) {
  3.     return size() > MAX_ENTRIES;
  4. }

来源：http://zhangshixi.iteye.com/blog/673789

参考：http://hi.baidu.com/yao1111yao/blog/item/3043e2f5657191f07709d7bb.html

部分修改。

 

 

使用LinkedHashMap构建LRU的Cache

http://tomyz0223.iteye.com/blog/1035686

基于LinkedHashMap实现LRU缓存调度算法原理及应用

http://woming66.iteye.com/blog/1284326

 

 

其实LinkedHashMap几乎和HashMap一样，不同的是它定义了一个Entry<K,V> header，这个header不是放在Table里，它是额外独立出来的。LinkedHashMap通过继承hashMap中的Entry<K,V>,并添加两个属性Entry<K,V>  before,after,和header结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。

分类目录 : 技术

图形化压力测试工具Jmeter

Dong - 2015年6月4日

Jmeter是一款强大的图形界面压力测试工具，完全用Java写成，关于Jmeter的介绍，网上其实有不少的文章，我原本是不想再重复写类似文章的，但我发现有些很关键性的，在我们测试中一定会用到的一些设置或操作很少见到有文章写清楚的，比如有这样的一个常见问题：如何对一个网站的多个链接进行压力测试？因为通常情况下，我们要测试的不是一个链接，假如我们测试的是某一网站的话，而这些链接我们通常都是写入到一个文本文件中，测试的过程中，会随机读取文件中的链接进行压力测试，我们所熟知的一些压力测试工具，例如Siege就可以这样干。

在我使用Jmeter的过程中，我发现我周围有之前使用过Jmeter的同事，但即使如此，他们对如何将多个链接写入到文本文件中并随机读取进行压力测试也不清楚，故我打算还是在有空的时候写一篇这样的文章，以方便使用者。

一、 官方网址

http://jakarta.apache.org/jmeter/

二、 运行

下载解压后，在目录jakarta-jmeter-2.4\bin下可以见到一个jmeter.bat文件，双击此文件，打开初始界面如下图：

Jmeter：图形界面压力测试工具

注意的是上面显示的是中文，如果你想使用其他语言，比如英文，那么通过菜单选项->选择语言->英文即可，当然转为中文也是同样操作。

三、 运行预准备

我们现在要对子猴博客来进行一番压力测试，压力测试对象为随机的几个网页链接，这几个链接是写在一个文本文件中的，在压力测试的时候会随机读取。

1、  建立一个线程组，如下图

Jmeter：图形界面压力测试工具

为什么要建立线程组？原因很简单，因为我们要模拟多个线程（用户）来访问网站。

线程组创建界面如下图：

名称可以随意填写，默认选中“继续”即可。

线程属性部分中，线程数是启动多少个线程，我这里填写的是60，Ramp-Up Period (in seconds)表示线程之间间隔多少时间允许，单位是秒，比如如果填写120，那么120/60=2表示60个线程间每隔2秒钟请求网站。

循环次数：60个线程运行完毕算是一次，循环次数就是这样的一个请求过程运行多少次，我这里填写的是1000.

每次修改一个设置后，别忘记了保存一下。

2、  设置请求服务器、压力链接等信息

接下来很自然的是，我们要测试的网站地址是什么？链接是什么？所以现在我们就来设置这些信息。

右键点击我们刚创建的线程组，在弹出的菜单中，选择添加->Sampler->Http请求，弹出如下图界面：

Jmeter：图形界面压力测试工具

名称：随意填写

注释：可有可无

服务器名称或IP：我这里填写 zihou.me

端口号：我这里填写80

Timesout部分可以不填

HTTP请求部分的协议：http，方法我选择的是GET，Content encoding我填的是UTF-8.

路径：

这里值得一提的就是这个路径，假如你只是对一个链接进行压力测试，那么这里就非常简单了，你就直接填写一个链接就够了，比如http://www.zihou.me，但很多情况下都不是这样的，我们这里需要多个链接，就如同刚开始讲到的那样，我们要将多个链接保存到一个文本文件中，然后随机读取进行压力测试。我们可以这么干，如图：

Jmeter：图形界面压力测试工具

Jmeter：图形界面压力测试工具

在选择一个功能下拉列表中选择_StringFromFile，然后在本机新建一个测试文件text.txt，在第一行（你也可以不在第一行）的值中填写测试文件的路径，如下图：

Jmeter：图形界面压力测试工具

然后点击“生成”按钮，在生成按钮的左边文本框中将生成一个字符串如：

${__StringFromFile(E:\test\test.txt,,,)}

在测试文件中，我们每行写一个URL链接，如下格式：

2011/03/26/3054

2011/03/26/3052

2011/03/26/3042

2011/03/25/3040

2011/03/25/3034

2011/03/24/3027

注意，每行前面并没有http://www.zihou.me这样的信息，因为我们在前面已经填写了服务器地址为zihou.me，这里就没必要再为每个url填写这个相同前缀了；另外，上面的url格式也只是个例子，表示域名后的部分，但很多时候url后面跟的都是各参数，比如http://www.zihou.me/p?a=1&b=3，如果是这种情况，则上面的链接可以写为：

a=1&b=3这样的形式。

现在我们可以来填写前面所说的路径了，如下：

/ ${__StringFromFile(E:\test\test.txt,,,)}

这样一来，当我们并非请求的时候，就会从test.txt中随机选择url来进行压力测试。

另外值得注意的一个地方是，如果参数中有中文的情况，运行的时候可能会出现乱码，这个时候就需要注意你在Jmeter中的编码设置与你要请求的网页编码是一致的。

路径文本框下面的选项，可以按默认的就成，Use multipart/form-data for HTTP POST是当请求中有附件的情况，一般情况下都不用选中的。

同请求一起发送参数部分：

如果你仅仅是对某一个固定的页面进行压力测试，那你就可以不用进行上面所说的在文本文件中设置URL的过程了，直接在这里设置就行了，这里的名称就是参数名，值就是参数值，在这里添加就OK了，但你如果是压力多个链接，那这里你可以不用填。

3、查看运行结果

上面设置好后，接下来很自然的想到如何查看运行结果呢？Jmeter在这方面提供了好些个查看方式，有表格形式，有曲线形式等等，我个人认为查看表格形式就足够了！

鼠标右键点击线程组，在弹出的菜单中选择添加->监听器->用表格查询结果，如下图：

Jmeter：图形界面压力测试工具

Jmeter：图形界面压力测试工具

当然，你也可以选择其他查看方式，你也可以看到在监听器菜单中，有好多种方式。

四、 运行

好了，现在我们终于可以运行了！

选择菜单项运行->启动，如下图：

Jmeter：图形界面压力测试工具

当然，在运行前，你得把所有修改都保存了。

运行后的结果表格如下：

Jmeter：图形界面压力测试工具

各属性如下：

Sample：每个请求的序号

Start Time：每个请求开始时间

Thread Name：每个线程的名称

Label：Http请求名称

Sample Time：每个请求所花时间，单位毫秒

Status：请求状态，如果为勾则表示成功，如果为叉表示失败。

Bytes：请求的字节数

如果Status为叉，那很显然请求是失败了，但如果是勾，也并不能认为请求就一定完全成功了，因为还得看Bytes的字节数是否是所请求网页的正常大小值，如果不是则说明发生了丢包现象，也不是完全成功。

在下面还有几个参数

样本数目：也就是上面所说的请求个数，成功的情况下等于你设定的并发数目乘以循环次数。

平均：每个线程请求的平均时间

最新样本：表示服务器响应最后一个请求的时间

偏离：服务器响应时间变化、离散程度测量值的大小，或者，换句话说，就是数据的分布（这个我不是很理解）。

在上面的参数中，我个人认为只要看Status和Bytes这两个就够了。

好了，主要的就介绍这么多了，其实Jmeter做压力测试的范围远远不止于对Web，它还可以用于Java小服务程序、CGI 脚本、Java 对象、数据库， FTP 服务器等等，更多的使用可以根据自己的需要去研究掌握。

最后还提到的一点是：你一定注意到了，HTTP请求和结果查看都是在线程组这一节点下创建的，其实，你也可以不用一定要在线程组下创建，你在测试计划下建立也可以，但创建在线程组下面可以使得我们的测试意图一目了然，也就是我们的HTTP请求和结果查看都是基于我们设定的线程组的。

转自链接《http://blog.sina.com.cn/s/blog_62192aed0101jdgi.html》

参考链接 Jmeter配置：《http://blog.sina.com.cn/s/blog_62192aed0101jdhb.html》

分类目录 : 技术

近期评论