HashTable、HashMap、ConcurrentMap的联系与区别

哈希表

哈希表有多种不同的实现方法，最常用的一种方法—— 拉链法，可以理解为链表的数组
           

从上图我们可以发现哈希表是由数组+链表组成的，一个长度为13的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

HashTable

1.实现了Serializable、Cloneable、Map<K,V>接口

2.继承了Dictionary<K,V>类

3.此类实现一个哈希表，该哈希表将键映射到相应的值。任何非 null 对象都可以用作键或值。

4.是线程安全的，一个人来操作时锁住整表，底层用的是Synchronoused同步代码库

5.哈希值的使用：HashTable直接使用对象的hashCode，计算hash值，直接用key的hashCode()

6.在求hash值对应的位置索引时，用取模运算

7. 在不指定容量的情况下的默认容量为11，不要求底层数组的容量一定要为2的整数次幂，扩容时，将容量变为原来的2倍加1

HashMap

1.实现了Serializable、Cloneable、Map<K,V>接口

2.继承了AbstractMap<K,V>类

3.基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。

4.是线程不安全的

5.哈希值的使用：HashMap重新计算hash值

6.在求位置索引时，用与运算

7.容量默认为16，要求一定为2的整数次幂，扩容时，将容量变为原来的2倍。

ConcurrentMap

线程安全的

默认分为16个桶，每个桶加锁，如果数据量达到一定大小，桶会翻倍

每个桶的元素达到8个以上，数据结构就会变为红黑二叉树（左旋、右旋）

所以，它的效率特别高

package cn.tedu.map;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ConcurrentNavigableMap;
import java.util.concurrent.ConcurrentSkipListMap;

import org.junit.Test;

public class ConcurrentMapDemo1 {
	@Test
	public void createmap(){
		ConcurrentMap<String,String> cm =
			new ConcurrentHashMap<String,String>();
		cm.put("one", "1");
		cm.put("two", "2");
		cm.put("three", "3");
		System.out.println(cm.get("two"));
	}
	@Test
	public void CNMTest(){
		ConcurrentNavigableMap<Integer,String> map = 
			new ConcurrentSkipListMap<Integer,String>();
		map.put(1, "one");
		map.put(2, "two");
		map.put(3, "three");
		map.put(4, "fore");
		map.put(5, "five");
		//含头不含尾
		//ConcurrentNavigableMap<Integer, String> headMap = 
				map.headMap(2);
		//System.out.println(headMap.size());//1
		/*ConcurrentNavigableMap<Integer, String> tailMap = 
				map.tailMap(3);
		System.out.println(tailMap.size());//3*/	
	    ConcurrentNavigableMap<Integer, String> subMap = 
				map.subMap(2, 4);
		System.out.println(subMap.size());//2
		
		
	}
}