一概荷、IntHashMap
1.1 準備
- 先從官網下載jar包：javasoft-collection.jar式曲，解壓后將jar包build到Java項目中.
1.2 IntHashMap類圖
1.3 IntHashMap流程圖
從上面類圖可以看出IntHashMap和HashMap一樣都是基于Map接口而涉，在Map中最常用的2個方法是put()和get()方法削葱。大家都知道Map是從鍵到值的映射惫撰，每個鍵不能出現(xiàn)重復且每個鍵最多只能映射到一個值瞭空。那么IntHashMap是如何保證鍵的唯一性杆兵？可能大家會想IntHashMap的鍵是int類型雁仲，使用==來比較，這樣子雖然能保證鍵的唯一琐脏。但是隨著元素的增加攒砖，每次都進行比較效率會越來越低。什么樣的數(shù)據結構能快速的存儲元素日裙？答案是數(shù)組吹艇。在HashMap中是通過hash計算出bucketIndex位置找到數(shù)組中對應的元素，那么IntHashMap呢昂拂？IntHashMap亦如此受神，唯一不同的是計算bucketIndex的算法。通過indexFor()方法拿到bucketindex后格侯。它會先去數(shù)組中找這個位置上的元素IntEntry<V>是否存在鼻听，如果存在的話财著，再通過key去查找value,然后將新值替換掉舊value。
代碼清單2如下：
/**
* Returns index for key
*/
protected int indexFor(int key, int length) {
key += ~(key << 9);
key ^= (key >>> 14);
key += (key << 4);
key ^= (key >>> 10);
return key & (length-1);
}
代碼清單2如下：
int i = indexFor(key, table.length);
for (IntEntry<V> e = table[i]; e != null; e = e.next) {
if (e.key == key) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
二撑碴、IntHashMap與HashMap比較
2.1 運行效率比較
創(chuàng)建一個測試類撑教，分別往IntHashMap和HashMap各插入1萬和5萬條數(shù)據來測試它們性能、GC和內存使用
代碼如下：
package com.lll.operator;
import java.util.HashMap;
import java.util.Map;
import ch.javasoft.util.intcoll.IntHashMap;
public class ShiftTest {
// IntHashMap<String> map = new IntHashMap<String>();
HashMap<Integer,String> map = new HashMap<Integer,String>();
public void add()
{
for (int i = 0; i < 10000;i++) {
for(int j = 0;j<50000;j++)
{
if(map.get(j) == null)
{
map.put(j, "小毛驢");
}
}
}
}
public static void main(String[] args) {
long curTime = System.currentTimeMillis();
ShiftTest shiftTest = new ShiftTest();
shiftTest.add();
long curTime2 = System.currentTimeMillis();
System.out.println("耗時:"+(curTime2-curTime)+"ms");
try {
Thread.sleep(5000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
2.2 Visual GC比較
HashMap:
IntHashMap:
2.3 結果分析
10000條數(shù)據測試結果：
IntHashMap
第一次取樣:795ms
第二次取樣:815ms
第三次取樣:807ms
GC時間：NO GC
HashMap
第一次取樣:866ms
第二次取樣:927ms
第三次取樣:861ms
GC時間：11.978ms
50000條數(shù)據測試結果：
IntHashMap
第一次取樣:5166ms
第二次取樣:4817ms
第三次取樣:4997ms
GC時間：NO GC
HashMap
第一次取樣:4388ms
第二次取樣:4430ms
第三次取樣:3876ms
GC時間：40.453ms
從上面的測試結果可以看出灰羽，HashMap會隨著容器大小的變化效率明顯變慢驮履。也許從數(shù)據測試結果來看使用IntHashMap在性能上比HashMap并沒有太大優(yōu)勢甚至效率還要低些，但是從GC上來看明顯IntHashMap更有優(yōu)勢廉嚼。那么是什么讓他們產生這樣的差異玫镐？
2.4 差異一
HashMap在插入元素過程中會在堆中產生大量的Integer實例(如下圖－Profiler界面)，參考代碼清單4怠噪。而IntHashMap不一樣恐似，它是以int作為key值類型(見代碼清單5)，能夠減少Integer實例的產生傍念，減少GC負擔矫夷。
Profiler界面
代碼清單4:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
代碼清單5:
public static class IntEntry<VV> implements IntMap.IntEntry<VV> {
protected final int key;
protected VV value;
protected IntEntry<VV> next;
/**
* Create new entry.
*/
protected IntEntry(int k, VV v, IntEntry<VV> n) {
value = v;
next = n;
key = k;
}
}
2.5 差異二
在遍歷時，IntHashMap(代碼清單6)沒有對hash進行比較憋槐。
代碼清單6
public V get(int key) {
int i = indexFor(key, table.length);
IntEntry<V> e = table[i];
while (true) {
if (e == null)
return null;
if (e.key == key)
return e.value;
e = e.next;
}
}
HashMap遍歷代碼清單7：
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
