相关阅读
【小家java】java5新特性（简述十大新特性） 重要一跃
【小家java】java6新特性（简述十大新特性） 鸡肋升级
【小家java】java7新特性（简述八大新特性） 不温不火
【小家java】java8新特性（简述十大新特性） 饱受赞誉
【小家java】java9新特性（简述十大新特性） 褒贬不一
【小家java】java10新特性（简述十大新特性） 小步迭代
【小家java】java11新特性（简述八大新特性） 首个重磅LTS版本
每篇一句
男人再帅，扛不起责任照样是废物。女人再美，自己不奋斗照样是摆设。人生就要活得漂亮，无论你是谁，宁可做拼搏的失败者，也不要做安于现状的平凡人。
Map的遍历问题，选择哪种方式性能最优？
java8之后提供了lambda表达式的遍历方式。因此如果可以用lambda表达式遍历，那就毫无疑问的直接选择即可。
遍历方式代码如下：
//entrySet方式：key和value一次性都拿出来for (Entry<String, String> entry: map.entrySet()) {key = entry.getKey();value = entry.getValue();}//keySet方式：先拿出key，再去拿valuefor (String key : map.keySet()) {value = map.get(key);}//values方式：当只需要value的时候，这种方式才合适for (String value : map.values()) {}
如果你是遍历HashMap：
遍历既需要key也需要value的时候：keySet与entrySet方法的性能差异取决于key的具体情况，如复杂度（复杂对象）、离散度、冲突率等。换言之，取决于HashMap查找value的开销。entrySet一次性取出所有key和value的操作是有性能开销的，当这个损失小于HashMap查找value的开销时，entrySet的性能优势就会体现出来。例如上述对比测试中，当key是最简单的数值字符串时，keySet可能反而会更高效，耗时比entrySet少10%。总体来说还是推荐使用entrySet。因为当key很简单时，其性能或许会略低于keySet，但却是可控的；而随着key的复杂化，entrySet的优势将会明显体现出来。遍历只需要key的时候：keySet方法更为合适，因为entrySet将无用的value也给取出来了，浪费了性能和空间只遍历value时，使用vlaues方法是最佳选择
如果你是遍历TreeMap：
同时遍历key和value时，与HashMap不同，entrySet的性能远远高于keySet。这是由TreeMap的查询效率决定的，也就是说，TreeMap查找value的开销较大，明显高于entrySet一次性取出所有key和value的开销。因此，遍历TreeMap时强烈推荐使用entrySet方法。只遍历key时，keySet方法更为合适，因为entrySet将无用的value也给取出来了，浪费了性能和空间只遍历value时，使用vlaues方法是最佳选择
综上：lambda遍历是首选。当lambda不适用（比如一边遍历一边需要移除等等），entrySet的遍历方式是最优的方式选择。
HashMap的原理（区分JDK8之前和之后）
哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，而HashMap的实现原理也常常出现在各类的面试题中，重要性可见一斑。
HashMap它包括几个重要的成员变量：table, size, threshold, loadFactor, modCount。
table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。
size是HashMap的大小，它是HashMap保存的键值对的数量。
threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值=“容量*加载因子”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
loadFactor就是加载因子。
modCount是用来实现fail-fast机制的。
在解说HashMap原理之前，科普一下另外一些数据结构的操作性能，对下面的解释也会有帮助.。
数组：查找快，新增、删除慢
采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
线性链表：新增、删除快，查找慢
对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)
二叉树：自平衡的话，新增、删除、查找都不快不慢
对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。
哈希表（重点讲解）：添加，删除，查找等操作都很快 (数组+链表)
相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。
我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。
这样子：我们找位置就这么找：
1、我们通过把当前元素的关键字 通过某个函数（hash算法取模存储位置 = f(关键字)）映射到数组中的某个位置，通过数组下标一次定位就可完成操作。
这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。
2、哈希冲突（哈希碰撞）：如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式，
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。
//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}，主干数组的长度一定是2的次幂，至于为什么这么做，后面会有详细分析。transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Entry是HashMap中的一个静态内部类。代码如下
static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算/*** Creates new entry.*/Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;}
所以综上可以知道，HashMap的整体结构如下：
简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
其它几个重要参数：
//实际存储的key-value键值对的个数transient int size;//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到int threshold;//负载因子，代表了table的填充度有多少，默认是0.75final float loadFactor;//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationExceptiontransient int modCount;
HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值initialCapacity默认为16，loadFactory默认为0.75。看内部源码可以看出来hash值是怎么计算出来的，并且知道扩容的原理：
再来看看addEntry的实现：
void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}
通过以上代码能够得知，当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。
HashMap的扩容机制 resize()
我们分析下resize的源码，鉴于JDK1.8融入了红黑树，较复杂，为了便于理解我们仍然使用JDK1.7的代码，好理解一些，本质上区别不大，具体区别后文再说。
JDK8以后引入了红黑树对查询新能进行了优化。当Hash桶里面的数量大于8或者总容量大于64，就会转为红黑树。这里推荐一篇文章，从源码级别详解这个过程：红黑树在HashMap中的应用
void resize(int newCapacity) {//传入新的容量 Entry[] oldTable = table; //引用扩容前的Entry数组 int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) {//扩容前的数组大小如果已经达到最大(2^30)了 threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了 return; } Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组 transfer(newTable);//！！将数据转移到新的Entry数组里 table = newTable; //HashMap的table属性引用新的Entry数组 threshold = (int) (newCapacity * loadFactor);//修改阈值 }
这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。
void transfer(Entry[] newTable) {Entry[] src = table; //src引用了旧的Entry数组 int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) {//遍历旧的Entry数组 Entry<K, V> e = src[j]; //取得旧Entry数组的每个元素 if (e != null) {src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象） do {Entry<K, V> next = e.next; int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置 e.next = newTable[i]; //标记[1] newTable[i] = e;//将元素放在数组上 e = next; //访问下一个Entry链上的元素 } while (e != null); } } } static int indexFor(int h, int length) {return h & (length - 1); }
在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。
下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。对应的就是下方的resize的注释：
/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ final Node<K,V>[] resize() {
看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码，写的很赞。
为何HashMap的数组长度一定是2的次幂？
如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index，我们先来看看transfer这个方法
void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);//将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。e.next = newTable[i];newTable[i] = e;e = next;}}}
这个方法将老数组中的数据逐个链表地遍历，扔到新的扩容后的数组中，我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后，再通过和 length-1进行位运算得到最终数组索引位置。
hashMap的数组长度一定保持2的次幂，比如16的二进制表示为 10000，那么length-1就是15，二进制为01111，同理扩容后的数组长度为32，二进制表示为100000，length-1为31，二进制表示为011111。从下图可以我们也能看到这样会保证低位全为1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过 h&(length-1)的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)，个人理解。
还有，数组长度保持2的次幂，length-1的低位都为1，会使得获得的数组索引index更加均匀，比如：
我们看到，上面的&运算，高位是不会对结果产生影响的（hash函数采用各种位运算可能也是为了使得低位更加散列），我们只关注低位bit，如果低位全部为1，那么对于h低位部分来说，任何一位的变化都会对结果产生影响，也就是说，要得到index=21这个存储位置，h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。
get方法的实现相对简单，key(hashcode)–>hash–>indexFor–>最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null。
为何建议：重写equals方法需同时重写hashCode方法
各种资料上都会提到，“重写equals时也要同时覆盖hashcode”，我们举个小例子来看看，如果重写了equals而不重写hashcode会发生什么样的问题
/*** Created by chengxiao on /11/15.*/public class MyTest {private static class Person{int idCard;String name;public Person(int idCard, String name) {this.idCard = idCard;this.name = name;}@Overridepublic boolean equals(Object o) {if (this == o) {return true;}if (o == null || getClass() != o.getClass()){return false;}Person person = (Person) o;//两个对象是否等值，通过idCard来确定return this.idCard == person.idCard;}}public static void main(String []args){HashMap<Person,String> map = new HashMap<Person, String>();Person person = new Person(1234,"乔峰");//put到hashmap中去map.put(person,"天龙八部");//get取出，从逻辑上讲应该能输出“天龙八部”System.out.println("结果:"+map.get(new Person(1234,"萧峰")));}}输出：null
理解了HashMap的基本原理，这个肯定很好理解了。因为indexFor–>最终索引位置不一样了，最怕的不是返回null，而是可能返回了一个错误的值，那就最尴尬了。
所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。
HashMap的API简单解析
void clear()Objectclone()boolean containsKey(Object key)boolean containsValue(Object value)Set<Entry<K, V>>entrySet()Vget(Object key)boolean isEmpty()Set<K>keySet()Vput(K key, V value)void putAll(Map<? extends K, ? extends V> map)Vremove(Object key)int size()Collection<V> values()
clear() 的作用是清空HashMap。它是通过将所有的元素设为null来实现的。
public void clear() {modCount++;Entry[] tab = table;for (int i = 0; i < tab.length; i++)tab[i] = null;size = 0;}
containsKey() 的作用是判断HashMap是否包含key。
public boolean containsKey(Object key) {return getEntry(key) != null;}containsKey() 首先通过getEntry(key)获取key对应的Entry，然后判断该Entry是否为null。
这里面其实很多人想问：为什么key是Object类型，这样很不方便啊。比如我们的key是Long类型，然后contans（Integer）类型，是永远get不出来数据。其实这不算Java的bug的，因为java的泛型是1.5以后才引入的，所以为了向下兼容，这里不能和get(K k)一样采用泛型，希望大家能够理解.
备注：HashMap将“key为null”的元素都放在table的位置0处，即table[0]中；“key不为null”的放在table的其余位置！
containsValue() 的作用是判断HashMap是否包含“值为value”的元素。
public boolean containsValue(Object value) {// 若“value为null”，则调用containsNullValue()查找if (value == null)return containsNullValue();// 若“value不为null”，则查找HashMap中是否有值为value的节点。Entry[] tab = table;for (int i = 0; i < tab.length ; i++)for (Entry e = tab[i] ; e != null ; e = e.next)if (value.equals(e.value))return true;return false;}
HashMap实现了Cloneable接口，即实现了clone()方法。
clone()方法的作用很简单，就是克隆一个HashMap对象并返回。
// 克隆一个HashMap，并返回Object对象public Object clone() {HashMap<K,V> result = null;try {result = (HashMap<K,V>)super.clone();} catch (CloneNotSupportedException e) {// assert false;}result.table = new Entry[table.length];result.entrySet = null;result.modCount = 0;result.size = 0;result.init();// 调用putAllForCreate()将全部元素添加到HashMap中result.putAllForCreate(this);return result;}
关于HashMap在Java8中的实现，我推荐参考这篇文章：HashMap在java8中的原理
HashTable的原理
基本和HashMap一样，只是它所有的方法都是被synchronized修饰的，包括toString()方法，所以效率是很低的，基本不会再使用它了。
TreeMap的原理
TreeMap的实现是红黑树算法的实现，所以需要了解TreeMap的原理，需要了解红黑树的原理，这里推荐红黑树原理
所以了解TreeMap的put、get方法的原理，其实都是需要深入了解红黑树对节点的处理。
LinkedHashMap 的原理
HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，因此更准确地说，它是一个将所有Entry节点链入一个双向链表的HashMap。由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap的元素存取过程基本与HashMap基本类似，只是在细节实现上稍有不同。当然，这是由LinkedHashMap本身的特性所决定的，因为它额外维护了一个双向链表用于保持迭代顺序。此外，LinkedHashMap可以很好的支持LRU算法。
虽然LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序。特别地，该迭代顺序可以是插入顺序，也可以是访问顺序。
更具体的解释，我给导向到这里：Map 综述（二）：彻头彻尾理解 LinkedHashMap
HashMap 是基于“拉链法”实现的散列表。一般用于单线程程序中。
Hashtable 也是基于“拉链法”实现的散列表。它一般用于多线程程序中。
WeakHashMap 也是基于“拉链法”实现的散列表，它一般也用于单线程程序中。相比HashMap，WeakHashMap中的键是“弱键”，当“弱键”被GC回收时，它对应的键值对也会被从WeakHashMap中删除；而HashMap中的键是强键。
TreeMap 是有序的散列表，它是通过红黑树实现的。它一般用于单线程中存储有序的映射。
LinkedHashMap：存储需要保证插入顺序的单线程环境中
HashMap为什么线程不安全？有什么影响？
一直以来都知道HashMap是线程不安全的，但是到底为什么线程不安全，在多线程操作情况下什么时候线程不安全？
让我们先来了解一下HashMap的底层存储结构，HashMap底层是一个Entry数组，一旦发生Hash冲突的的时候，HashMap采用拉链法解决碰撞冲突，Entry内部的变量：
final Object key; Object value; Entry next; int hash;
通过Entry内部的next变量可以知道使用的是链表，这时候我们可以知道，如果多个线程，在某一时刻同时操作HashMap并执行put操作，而有大于两个key的hash值相同，如图中a1、a2，这个时候需要解决碰撞冲突，而解决冲突的办法上面已经说过，对于链表的结构在这里不再赘述，暂且不讨论是从链表头部插入还是从尾部初入，这个时候两个线程如果恰好都取到了对应位置的头结点e1，而最终的结果可想而知，a1、a2两个数据中势必会有一个会丢失，如图所示：
看看put方法：
public Object put(Object obj, Object obj1) {if(table == EMPTY_TABLE) inflateTable(threshold); if(obj == null) return putForNullKey(obj1); int i = hash(obj); int j = indexFor(i, table.length); for(Entry entry = table[j]; entry != null; entry = entry.next) {Object obj2; if(entry.hash == i && ((obj2 = entry.key) == obj || obj.equals(obj2))) {Object obj3 = entry.value; entry.value = obj1; entry.recordAccess(this); return obj3; } } modCount++; addEntry(i, obj, obj1, j); return null; }
put方法不是同步的，同时调用了addEntry方法。addEntry方法依然不是同步的，所以导致了线程不安全出现伤处问题，其他类似操作不再说明，源码一看便知，下面主要说一下另一个非常重要的知识点，同样也是HashMap非线程安全的原因，我们知道在HashMap存在扩容的情况，对应的方法为HashMap中的resize方法：
void resize(int i) {Entry aentry[] = table; int j = aentry.length; if(j == 1073741824) {threshold = 2147483647; return; } else {Entry aentry1[] = new Entry[i]; transfer(aentry1, initHashSeedAsNeeded(i)); table = aentry1; threshold = (int)Math.min((float)i * loadFactor, 1.073742E+009F); return; } }
可以看到扩容方法也不是同步的，通过代码我们知道在扩容过程中，会新生成一个新的容量的数组，然后对原数组的所有键值对重新进行计算和写入新的数组，之后指向新生成的数组。
**当多个线程同时检测到总数量超过门限值的时候就会同时调用resize操作**，各自生成新的数组并rehash后赋给该map底层的数组table，结果最终只有最后一个线程生成的新数组被赋给table变量，其他线程的均会丢失。而且当某些线程已经完成赋值而其他线程刚开始的时候，就会用已经被赋值的table作为原始数组，这样也会有问题。
使用线程安全的Map
HashTable或者Collections.synchronizedMap
但是这两位选手都有一个共同的问题：性能。因为不管是读还是写操作，他们都会给整个集合上锁，导致同一时间的其他操作被阻塞。
虽然HashTable和Collections.synchronizedMap解决了HashMap的线程不安全的问题，但是带来了运行效率不佳的问题。
基于以上所述，兼顾了线程安全和运行效率的ConcurrentHashMap就出现了。
Collections.synchronizedMap()和Hashtable一样，实现上在调用map所有方法时，都对整个map进行同步.
ConcurrentHashMap：实现线程安全的HashMap
ConcurrentHashMap与HashMap相比，最关键的是要理解一个概念：segment。
Segment其实就是一个Hashmap 。Segment也包含一个HashEntry数组，数组中的每一个HashEntry既是一个键值对，也是一个链表的头节点。
Segment对象在ConcurrentHashMap集合中有2的N次方个，共同保存在一个名为segments的数组当中。（类比HashMap来理解Segment就好）因此ConcurrentHashMap的结构为：
换言之，ConcurrentHashMap是一个双层哈希表。在一个总的哈希表下面，有若干个子哈希表。（这样的双层结构，类似于数据库水平拆分来理解）ConcurrentHashMap如此的设计，优势主要在于： 每个segment的读写是高度自治的，segment之间互不影响。这称之为**“锁分段技术”**；
看一下并发情况下的ConcurrentHashMap：
– 情景一：不同segment的并发写入
不同的Segment是可以并发执行put操作的
– 情景二：同一segment的并发写入
因为segment的写入是上锁的，因此对 同一segment的并发写入会被阻塞;
– 情景三：同一segment的一写一读
同一segment的写和读是可以并发执行的；
下面简要说说读写的过程：
get：
1.为输入的Key做Hash运算，得到hash值。
2.通过hash值，定位到对应的Segment对象
3.再次通过hash值，定位到Segment当中数组的具体位置。
put：
1.为输入的Key做Hash运算，得到hash值。
2.通过hash值，定位到对应的Segment对象
3.获取可重入锁
4.再次通过hash值，定位到Segment当中数组的具体位置。
5.插入或覆盖HashEntry对象。
6.释放锁。
抛出一个问题：每一个segment各自持有锁，那么在调用size()方法的时候（size()在实际开发大量使用），怎么保持一致性呢？
Size方法的目的是统计ConcurrentHashMap的总元素数量， 肯定要把每个segment内部的元素数量都加起来。
那么假设一种情况，在统计segment元素数量的过程中，在统计结束前，已统计过的segment插入了新的元素，size()返回的数量就会出现不一致的问题。
为解决这个问题，ConcurrentHashMap的Size()方法是通过一个嵌套循环解决的，大体过程如下：
1.遍历所有的Segment。
2.把Segment的元素数量累加起来。
3.把Segment的修改次数累加起来。
4.判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束。
5.如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计。
6.再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等。
7.释放锁，统计结束。
为了不锁所有segment，首先乐观地假设size过程中不会有修改。当尝试一定次数，才无奈转悲观，锁住所有segment以保证一致性。
以上都是基于Java1.7的ConcurrentHashMap原理和代码；ConcurrentHashMap在对Key求Hash值的时候进行了两次Hash，目的是为了实现Segment均匀分布。
jdk1.7中采用Segment + HashEntry的方式进行实现，结构如下：
1.8中放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，结构如下：
只有在执行第一次put方法时才会调用initTable()初始化Node数组，实现如下：
private final Node<K,V>[] initTable() {Node<K,V>[] tab; int sc;while ((tab = table) == null || tab.length == 0) {if ((sc = sizeCtl) < 0)Thread.yield(); // lost initialization race; just spinelse if (pareAndSwapInt(this, SIZECTL, sc, -1)) {try {if ((tab = table) == null || tab.length == 0) {int n = (sc > 0) ? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];table = tab = nt;sc = n - (n >>> 2);}} finally {sizeCtl = sc;}break;}}return tab;}
1.8中使用一个volatile类型的变量baseCount记录元素的个数，当插入新数据或则删除数据时，会通过addCount()方法更新baseCount，通过累加baseCount和CounterCell数组中的数量，即可得到元素的总个数；
HashTable使用一把锁处理并发问题，当有多个线程访问时，需要多个线程竞争一把锁，导致阻塞
