AbstractMap

Map的内部实现,key用一个set实现, value用一个Collection

transient volatile Set<K>        keySet = null;
transient volatile Collection<V> values = null;

HashMap

内部就一个Entry数组,有一个装载因子的概念

//默认容量
static final int DEFAULT_INITIAL_CAPACITY = 16;

//默认装载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//长度必须为2的幂次方
transient Entry[] table;

//阈值, = capacity * load factor, 当size达到这个值的时候需要搬家
int threshold;

//装载因子
final float loadFactor;

而Entry对象包含key,value,当前节点的hash值以及一下个Entry对象的指针

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
}

hash函数及下标:

//hash函数, h为key.hashCode()值
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

//通过hash()的返回值,获取在桶中的下标
static int indexFor(int h, int length) {
    return h & (length-1);
}

HashMap在多线程环境下会出现的死循环问题,详细. 有人把这个问题报给了Sun，不过Sun不认为这个是一个问题。因为HashMap本来就不支持并发。要并发就用ConcurrentHashmap ,详见.由此也可见,HashMap不是线程安全的.

HashTable

HashTable不允许value为null, 而HashMap允许.

默认Capacity为11, 负载因子0.75

public Hashtable() {
    this(11, 0.75f);
}

通过key找到其在桶中下标

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

HashTable线程安全的,是通过每个方法都加上synchronized关键字.

public synchronized V get(Object key) {
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
        return e.value;
        }
    }
    return null;
}

public synchronized V put(K key, V value) {
    ...
}

IdentityHashMap

在IdentityHashMap中，判断两个键值k1和 k2相等的条件是 k1 == k2 。在正常的Map 实现（如 HashMap）中，当且仅当满足下列条件时才认为两个键 k1 和 k2 相等：(k1==null ? k2==null : e1.equals(e2))。如下:

public boolean containsKey(Object key) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
    while (true) {
        Object item = tab[i];
        if (item == k)  //判断键值相等
            return true;
        if (item == null)
            return false;
        i = nextKeyIndex(i, len);
    }
}

简单示例:

IdentityHashMap<String,Object> map =newIdentityHashMap<String,Object>();

//这两个entry会同时存在, 因为两次new String("xx")地址不一样
map.put(new String("xx"),"first");
map.put(new String("xx"),"second");

xiaobaoqiu Blog

Think More, Code Less

Java Map

AbstractMap

HashMap

HashTable

IdentityHashMap