1 Map
Map 定义了键值存储的数据操作的接口, 主要用于键值的存储, 使用键可以得到值, 并且不允许重复的键, 值可以重复, 可以起到数据的快速获取的目的 Java 1.5 后有了 concurrent 包, 因此处理 java.utils 里面有 Map 的实现外, concurrent 包中也增加了同步 Map 的实现
1.1 java.util 中的 Map 实现
1.1.1 HashMap
1. HashMap 继承自 AbstractMap, 实现了 MapSerializable, Cloneable 接口
2. HashMap 是单向链表数组的存储结构(拉链法), 根据 Key 的 HashCode 值运算后作为数组的 index 存储数据, 根据 key 可以直接获取它的值, 具有很快的访问速度, 遍历时, 取得数据的顺序时完全随机的
3. HashMap 只允许一条记录的键为 Null;
4. HashMap 不支持多线程的同步, 即任意时刻可以有多个线程同时写 HashMap, 可能会导致数据的不一致如果需要同步, 可以使用 Collections 的 synchronizedMap 方法使 HashMap 具有同步的能力, 或者使用 ConcurrentHashMap
5. 不能使用 get() 方法返回 null 值判断是否包含是否包含该键, 而应该使用 constainsKey() 方法来判断
6. 默认的长度为 16, 扩充是按照 2 的指数倍进行扩充, 这一点可以看下 HashMap 的 resize() 方法
- final Node[] resize() {
- Node[] oldTab = table;
- int oldCap = (oldTab == null) ? 0 : oldTab.length;
- int oldThr = threshold;
- int newCap, newThr = 0;
- if (oldCap > 0)
- {
- if (oldCap >= MAXIMUM_CAPACITY) // 长度超过最大限制时不再扩充
- {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
- // 原 size 扩充一倍小于最大限制且旧的 size 大于等于默认大小时,
- // 设置新的大小原来 threshold 一倍, 那么 threshold 在使用无参构造函数时是怎么设置值呢? 在本函数中, 继续向下看
- newThr = oldThr << 1; // double threshold
- } else if (oldThr > 0)
- // 默认 threshold 为 0, 默认的初始化方法, 第一次存放数据时该代码不会执行
- newCap = oldThr;
- else // zero initial threshold signifies using defaults
- {
- // 此处为默认的初始化的 Map , 第一次存放数据执行的地方, 为设置 size 为默认的大小即: 16,
- // 下次调整大小的为默认的 factor (0.75) * 16
- newCap = DEFAULT_INITIAL_CAPACITY;
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
- if (newThr == 0)
- {
- float ft = (float)newCap * loadFactor;
- newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
- }
- threshold = newThr;
- //
- return newTab;
- }
7. 计算 Key 的 hash() 值
- static final int hash(Objectkey)
- {
- int h;
- return(key ==null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
- }
8. hashMap 实际存储的是一个单项链表的数组;
9. 新增元素时, key 为 null 的值直接放到数组的首位, 否则使用 hash()计算的值, 与当前的存储数组的长度 length-1 后有 key 的 hash 做 按位与 (&) 的操作或许下标, 如果该 index 下已经存在项, 则创建新的 node, 并做存储的链表的开始位置, 将 next 指向想一个元素, 否则, 存储新的节点, 下一个元素为 null
10. get() 元素时, 使用 key 的 hashcode 运算后获取到 index, 使用 index 获取链表后进行遍历, 找到 key 对应的值;
11. HashMap 提供了 keySet() 方法集获取 key 的 set 集合, values() 方法获取值的 collection, entrySet() 方法返回了 entry 的 set 集合
1.1.2 Hashtable
1. Hashtable 继承自 java.util.Dictionary 抽象类, 实现了 Map,Cloneable, Serializable 接口;
2. Hashtable 存储结构与 HashMap 一样, 使用的单向链表数组, 但是, hastable 不允许 key 和 value 为 null;
3. key 的 hashCode 是使用的 key 本身的 hashkey;
4. Hashtable 是线程安全, 它使用 synchronized 对 public 的函数加锁实现到了同步;
5. Hashtable 默认大小是 11, 这个在其默认的构造函数里面可以看到:
- public Hashtable()
- {
- this(11, 0.75f);
- }
当需要扩充是, Hashtable 是扩充为原来大小的 1 倍 + 1
- protected void rehash()
- {
- int oldCapacity= table.length;
- Entry[] oldMap= table;
- // overflow-conscious code
- int newCapacity= (oldCapacity << 1) + 1;
- if(newCapacity - MAX_ARRAY_SIZE > 0)
- {
- if(oldCapacity == MAX_ARRAY_SIZE)
- // Keep running with MAX_ARRAY_SIZE buckets
- return;
- newCapacity = MAX_ARRAY_SIZE;
- }
- .........
- }
- 1.1.3 LinkedHashMap
LinkedHashMap 继承自 HashMap, 实现了 Map 接口 LinedHashMap 存入元素默认是按照插入的顺序保存遍历 LinkedHashMap 时, 先得到的记录肯定是先插入的也可以在构造时用带参数, 按照应用次数排序在遍历的时候会比 HashMap 慢, 不过有种情况例外, 当 HashMap 容量很大, 实际数据较少时, 遍历起来可能会比 LinkedHashMap 慢, 因为 LinkedHashMap 的遍历速度只和实际数据有关, 和容量无关, 而 HashMap 的遍历速度和他的容量有关
LinkedHashMap 存储元素 Entry 在 HashMap.Node 的基础上增加了如下的 before 和 after, 使之变成了双向的链表结构, 源码如下:
- static class Entry extends HashMap.Node
- {
- Entry before,after;
- Entry(int hash,K key,V value,Node next)
- {
- super(hash, key, value, next);
- }
- }
- 1.1.4 TreeMap
1. TreeMap 继承自 AbstractMap, 实现了 SortedMap 的接口实现了 NavigableMap 接口, 意味着它支持一系列的导航方法比如返回有序的 key 集合
2. 基于红黑树实现 TreeMap 没有调优选项, 因为该树总处于平衡状态
3. TreeMap 会按照 key 的存储顺序进行排序, 默认使用使用字典升序排列, 可以自己实现 Comparator 来自定义排序规则
TreeMap 提供构造函数如下:
- // 默认构造函数使用该构造函数, TreeMap 中的元素按照自然排序进行排列
- TreeMap()
- // 创建的 TreeMap 包含
- Map TreeMap(Map copyFrom)
- // 指定 Tree 的比较器
- TreeMap(Comparator comparator)
- // 创建的 TreeSet 包含 copyFrom
- TreeMap(SortedMap copyFrom)
关于详细的介绍, 大家可以去看这里 http://www.cnblogs.com/skywang12345/p/3310928.html , 介绍的非常详细, 同时对红黑树也相应的文章进行介绍
1.1.5 WeakHashMap
WeakHashMap 实现了 Map 接口, 继承自 AbstractMap, 与 HashMap 的用法基本相同, 不同的是它使用弱引用作为存储内部数据的方案, 当系统内存不够的时候, 垃圾收集器会自动的清除没有在其他任何地方被引用的键值对在使用 WeakHashMap 进行大量数据的进行缓存时, 如果超过 JVM 的内存大小, 会先对引用的数据进行 GC, 然后再存放新的数据可以看看在执行 put(K k, V v) 方法时, 会执行 getTable 的方法
- public V put(K key, V value)
- {
- Object k = maskNull(key);
- int h = hash(k);
- Entry[] tab = getTable();
- int i = indexFor(h, tab.length);
- return null;
- }
而 getTable() 的方法会执行 expungeStaleEntries(), 移除没有引用的键值对
- private void expungeStaleEntries()
- {
- for (Object x; (x = queue.poll()) != null; )
- {
- synchronized (queue)
- {
- @SuppressWarnings("unchecked")
- Entry e = (Entry) x;
- int i = indexFor(e.hash, table.length);
- Entry prev = table[i];
- Entry p = prev;
- while (p != null)
- {
- Entry next = p.next;
- if (p == e)
- {
- if (prev == e)
- table[i] = next;
- else prev.next = next;
- // Must not null out e.next;
- // stale entries may be in use by a HashIterator
- e.value = null; // Help GC
- size--; break;
- }
- prev = p;
- p = next;
- }
- }
- }
- }
这就是有人觉得使用 WeakHashMap 不靠谱的地方吧
1.2 java.util.concurrent
concurrent 包是 java1.5 后添加的, 包含许多线程安全测试良好高性能的并发构建块
1.2.1 ConcurrentHashMap
ConcurrentHashMap 与 HashMap 非常相似,
ConcurrentHashMap 在线程安全的基础上提供了更好的写并发能力
继承自 AbstractMap, 实现了 ConcurrentMap 接口
基本的操作与 HashMap 是一致的, 一些关键的属性增加了线程同步的控制
1.2.2 ConcurrentSkipListMap
首先简单的介绍下 SkipList 跳表, 跳表也是使用的一种扩展的单向链表的数据结构, 普通的单向链表是一种线性结构, 前一个节点指向后一个节点, 而跳表则是前一个节点可能执行后一个和后续的其他节点, 以空间换时间, 提高了查找的效率
ConcurrentSkipListMap 提供了一种线程安全的排序的映射表内部是 SkipList(跳表)结构实现, 在理论上能够 O(log(n)) 时间内完成查找插入删除等操作
2 参考资料
- http://blog.csdn.net/io_field/article/details/53281884
- http://www.importnew.com/22007.html
- http://blog.csdn.net/ns_code/article/details/36034955
- http://blog.csdn.net/sunxianghuang/article/details/52221913
来源: http://www.jianshu.com/p/bfaf0363a53b