【java源码系列】Map

diagram,java设计架构

来自网络 http://www.cnblogs.com/skywang12345/p/3308931.html

Map 接口提供三种collection 视图,允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。

summary

同步(线程安全) order null key null value implementation 增删查改(按key) 查(按value) containsValue C C++(STL) python
HashMap × 无序 hash table (采用seperate chaining解决键冲突)java8采用了哈希表与红黑树结合的方法 O(1) 顺序查找 O(n) 比如redis的实现
LinkedHashmap × 按插入顺序排序 同上
Hashtable 无序 × × 同上
TreeMap 按key自定义排序 红黑树 O(log n)
WeakHashMap
EnumMap
  • HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。
  • HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。

sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁,其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。
Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator,然后其它的线程试图“结构上”更改集合对象,将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的,因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改,再调用set()方法,将会抛出IllegalArgumentException异常。
结构上的更改指的是删除或者插入一个元素,这样会影响到map的结构。

有没有既linked,又线程安全的Map,答案没有。因为多个线程同时操作,不同的执行顺序会产生不同的结果。所以linked的东东都应该不存在线程安全性。不能加锁吗? –by xs

底层实现

HashTable使用Enumeration,HashMap使用Iterator。
HashTable中hash数组默认大小是11,增加的方式是 old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数。

6.哈希值的使用不同,HashTable直接使用对象的hashCode,代码是这样的:
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
而HashMap重新计算hash值,而且用与代替求模:
int hash = hash(k);
int i = indexFor(hash, table.length);

static int hash(Object x) {
  int h = x.hashCode();

  h += ~(h << 9);
  h ^= (h >>> 14);
  h += (h << 4);
  h ^= (h >>> 10);
  return h;
}
static int indexFor(int h, int length) {
  return h & (length-1);
}
以上只是一些比较突出的区别,当然他们的实现上还是有很多不同的,比如
HashMap对null的操作

哈希冲突