[TOC]

HashMap

HashMap 继承于AbstractMap,实现于Map接口;由数组加链表实现,默认大小16,加载因子0.75

众所周知,HashMap是线程不安全的,HashTable才是线程安全的,那么究竟是什么导致线程不安全的呢?

put操作,在多线程模式下,触发扩容机制,导致数据被覆盖;

但是在单线程模式下还是可以使用的,其结构采用数组+链表的形式;通过hashcode 值得到索引,再追加到链表中,当链表的长度大于8时,采用红黑树算法;

为了使其线程安全,在 java.util.Collections 集合中有个Collections.synchronizedMap包装器;该包装器可以使其达到线程安全的效果;

示例如下:

public static void main(String[] args) {
final Map<String, String> map = Collections.synchronizedMap(new HashMap<String, String>());
final Map<String, String> map2 = new HashMap<String, String>();
for (int i = 0; i < 3; i++) {
final int finalI = i;
new Thread(new Runnable() {
@Override
public void run() {
for (int j = 0+ finalI *250; j <250+finalI *250; j++) {
map.put(String.valueOf(j), String.valueOf(j));
map2.put(String.valueOf(j), String.valueOf(j));
}
}
}).start();
}
try {
Thread.sleep(3000);
for (int i = 0; i < map.size(); i++) {
if (!String.valueOf(i).equals(map.get(String.valueOf(i)))) {
System.out.println("map false");
}
if (!String.valueOf(i).equals(map2.get(String.valueOf(i)))) {
System.out.println("map2 false");
}
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}

输出:

map2 false
...
map2 false

补充:hash冲突: 开发寻址法:线性探测法、二次探测法、双重哈希;链表法

HashTable

而hashtable之所以线程安全,因为它的put和get操作均添加有synchronized关键字,进行同步操作,获取锁,使其他线程阻塞等待;

因为当一个线程访问hashtable的同步方法时,其他线程再次尝试访问的时候,会进入阻塞或者轮询状态,比如当线程1使用put进行元素添加的时候,线程2不但不能使用put来添加元素,而且不能使用get获取元素。

虽然达到了线程安全的效果,但是极大的降低了效率,不推荐使用;

既然HashMap是线程不安全的,而HashTable的效率又不是很高,那么有没有除了他俩之外的其他数据结构呢?

答案当然有,如:ConcurrentHashMap等等;

ConcurrentHashMap

通过属性值可知,和HashMap一样,默认容量也是16,大于8转为树,并且还是线程安全的;

private static final int DEFAULT_CAPACITY = 16;
private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final float LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;

ConcurrentHashMap 采用了一种叫做分段锁的机制,分段进行加锁,同时进行读写,大大地提高了效率;比围绕非线程安全Map的Collections.synchronizedMap包装器性能更高。

且在jdk1.8中对ConcurrentHashMap 进行了优化,采用compareAndSwapInt+synchronized 方式进而大大提高了效率。

除此之外,它还提供了一些原子操作的方法:

putIfAbsent

putIfAbsent方法主要是在向ConcurrentHashMap中添加键—值对的时候,它会先判断该键值对是否已经存在。

  • 如果不存在(新的entry),那么会向map中添加该键值对,并返回null;
  • 如果已经存在,那么不会覆盖已有的值,直接返回已经存在的值;

computeIfAbsent

  • 如果 key 对应的 value 不存在,则使用获取 remappingFunction 重新计算后的值,并保存为该 key 的 value,否则返回 value。

LinkedHashMap

  • LinkedHashMap属于HashMap的子类,与HashMap的区别在于LinkedHashMap保存了记录插入的顺序。
  • LinkedHashMap 是一个双向的链表,包含有链表头、尾的指针,因这个特性,所以LinkedHashMap 是有序的,而HashMap是无序的。
  • LinkedHashMap的构造函数中有个 accessOrder 变量,true 表示链表按访问顺序,false 表示按插入顺序;
  • 如下所示,通过对该变量的控制,可以利用LinkedHashMap实现LruCache的核心思想;
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

TreeMap

  • TreeMap实现了SortedMap接口,TreeMap有能力对插入的记录根据key排序,默认按照升序排序,也可以自定义比较强,在使用TreeMap的时候,key应当实现Comparable。

  • TreeMap基于红黑树实现,非线程安全 ;

  • 与HashMap比较:两者均是线程不安全的;通常情况下HashMap通常比TreeMap快些,若是使用排序选择TreeMap,其他情况则建议多使用HashMap;