1 Map
Map 定义了键值存储的数据操作的接口， 主要用于键值的存储，使用键可以得到值，并且不允许重复的键，值可以重复，可以起到数据的快速获取的目的。Java 1.5 后有了 concurrent 包，因此处理 java.utils 里面有 Map 的实现外，concurrent 包中也增加了同步 Map 的实现。
1.1 java.util 中的 Map 实现
1.1.1 HashMap
1. HashMap 继承自AbstractMap, 实现了 Map、Serializable, 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
网友评论