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

底层实现

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

哈希冲突