【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的操作

哈希冲突