Map子类重要源码分析对比&HashMap&HashTable&TreeMap&IdentityHashMap&WeakHashMap

时间:2021-02-21 17:19:13

Map是Java最常用的中最常用的集合之一。
它的子类有

HashTable
HashMap
TreeMap
IdentityHashMap
WeakHashMap

HashTable和HashMap的分析对比

参考Blog【单独的对HashMap和HashTable的分析】


【HashMap源码分析】(http://blog.csdn.net/chdjj/article/details/38553163

【HashMap实现原理分析】
http://blog.csdn.net/vking_wang/article/details/14166593

【HashTable源码分析】(http://blog.csdn.net/chdjj/article/details/38581035)


HashTable是jdk1.0产生的,HashMap是jdk1.2产生的。HashMap其实就是在HashTable的细节上做了改动和完善。

HashTable和HashMap的时间复杂度为o(1)。空间复杂度不一定【这个是可以根据构造函数变化的】

主要不同如下

1HashTable是线程安全的。所以跟HashMap比性能差一点。
2HashTable键、值都不能为null,HashMap都可以为null
3HashTable的contains()方法容易让人产生歧义,在HashMap把它删掉了

源码分析:
不同点1

//HashTable
public synchronized V put(K key, V value)
//HashMap
public V put(K key, V value)

不同点2

//HashTable
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}

// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}

addEntry(hash, key, value, index);
return null;
}

其中值不能为空非常明显,至于key不能为空,是在这句代码

int hash = key.hashCode();

hash码根据key的地址产生,key为空自然就会有空指针异常

//HashMap
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}
------------------------------------------------------
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}

判断了key值,value不用管。
不同点3

//HashTable
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}

Entry<?,?> tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
public boolean containsValue(Object value) {
return contains(value);
}

HashTable要了这个contains主要是判断value非空的,到了HashMap这里value已经可以为空了。所以就把这个易混淆的方法丢弃了。

TreeMap

参考Blog


【TreeMap的源码分析】(http://blog.csdn.net/chenssy/article/details/26668941)


这个类与HashMap的不同

1、数据结构不同【可以说这导致了基本都不一样】

TreeMap是有序的,因为它的数据结构是红黑树【一种平衡二叉搜索树】。它的时间复杂度是log2(n);

至于源码及分析,见上面的Blog【强烈推荐一波,这个Blog对源码及红黑树的分析非常到位】

IdentityHashMap

参考Blog


【 IdentityHashMap分析】(http://blog.csdn.net/hudashi/article/details/6947625)


这个类与HashMap的主要不同有两点

1、判断key值相等的方式不同,这也是IdentityHashMap键可以重复的原因
2、数据结构不同【所以IdentityHashMap快一点】

源码如下:

不同点1

 public V put(K key, V value) {
final Object k = maskNull(key);

retryAfterResize: for (;;) {
final Object[] tab = table;
final int len = tab.length;
int i = hash(k, len);

for (Object item; (item = tab[i]) != null;
i = nextKeyIndex(i, len)) {
if (item == k) {
@SuppressWarnings("unchecked")
V oldValue = (V) tab[i + 1];
tab[i + 1] = value;
return oldValue;
}
}

final int s = size + 1;
// Use optimized form of 3 * s.
// Next capacity is len, 2 * current capacity.
if (s + (s << 1) > len && resize(len))
continue retryAfterResize;

modCount++;
tab[i] = k;
tab[i + 1] = value;
size = s;
return null;
}
}

这句代码

if(item == k) !
//HashMap
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

这句代码

 if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

很明显前者根据地址判断相同,后者根据key的hash码和来内容来判断

不同点2

//IdentityHashMap
transient Object[] table;
//HashMap
transient Entry[] table;

IdentityHashMap是通过数组来存储的

 tab[i] = k;
tab[i + 1] = value;

至于HashMap

通过数组table+链Entry

WeakHashMap

参考Blog


【WeakhashMap分析】(http://mikewang.blog.51cto.com/3826268/880775/)


简单理解就是
WeakHashmap中【key, value】中的key,如果除了WeakHashmap自己对之外没有引用了【联系】,那么这个对象就会被gc。
下面是一个简单的代码,代码来自http://www.jb51.net/article/36948.htm

import java.util.*;
import java.util.Hashtable;
/**
* Created by hms on 2017/2/8.
*/

public class MapAnalyze {
public static void main(String[] args) {
String a = new String("a");
String b = new String("b");
Map weakmap = new WeakHashMap();
Map map = new HashMap();
map.put(a, "aaa");
map.put(b, "bbb");


weakmap.put(a, "aaa");
weakmap.put(b, "bbb");

map.remove(a);

a=null;
b=null;

System.gc();
Iterator i = map.entrySet().iterator();
while (i.hasNext()) {
Map.Entry en = (Map.Entry)i.next();
System.out.println("map:"+en.getKey()+":"+en.getValue());
}

Iterator j = weakmap.entrySet().iterator();
while (j.hasNext()) {
Map.Entry en = (Map.Entry)j.next();
System.out.println("weakmap:"+en.getKey()+":"+en.getValue());

}
}
}


/** Output
map:b:bbb
weakmap:b:bbb
*/