HashMap和ConcurrentHashMap
HashMap
在不考虑哈希冲突的情况下，HashMap的增加，删除，查找元素的时间复杂度都为O(1)。效率十分的高。
哈希表的主干是数组。
在增加时把当前的元素时把当前元素的关键字通过哈希函数映射到数组中的某个位置，查找时通过哈希函数确定下标，再直接通过下标获取数组指定元素。
当通过哈希函数计算一个并得到一个元素的下标，但是发现该下标对应位置已经被别的元素占据，这就是所谓的哈希冲突，也叫哈希碰撞。
哈希冲突的解决方法主要有：
1.开放地址法（发生冲突，继续寻找下一块未被占据的地址）
2.再散列函数法。
3.链地址法。
HashMap采用链地址法（数组加链表）解决哈希冲突。
HashMap的主干是一个Entry数组，一个Entry对象包括一个key和对应的value。
下图是HashMap的结构。
HashMap由数组加链表的结构组成。其主体是一个Entry数组，链表主要是为了解决哈希冲突存在的。对于有链表的Entry来说，添加操作的时间复杂度依然不变，但是查找则需要遍历链表。因此HashMap中链表越少越好。
HashMap在不指定的情况下，是在执行put方法时才真正构造table数组的。
当HashMap发生哈希冲突并且HashMap的size大于阈值时，将会执行扩容操作，然后将现有数据copy过去，扩容大小是原来的两倍。
HashTable
HashTable的实现原理和HashMap几乎一样。其区别在于
1.HashTable的key和value不允许为null。
2.HashTable是线程安全的。
HashTable的线程安全开销较大，get和push全都是加锁的（synchronized），相当于给哈希表加锁，所有的操作都是串行的。同时只有一个对象能访问或操作该对象。
ConcurrentHashMap
ConcurrentHashMap采用了分段锁的机制。其主干是Segment数组。Segment继承了ReentrantLock，因此Segment是一个可重入锁。在ConcurrentHashMap中，一个Segment就是一张哈希表。Segment里面维护了一个HashEntry数组。并发环境下，对不同的Segment访问是不用考虑竞争的。（默认的ConcurrentLevel为16，理论上最多允许16个线程并发执行）对于同一个Segment的操作才考虑线程同步。
Segment类似HashMap。
Segment数组大小由concurrentLevel决定，但是不完全等于concurrentLevel。
在执行put方法时，主要执行两步操作
1：确保定位的Segment已经初始化。
2：调用Segment的put方法。
get方法无需加锁。其中所涉及的数据用volatile修饰，保证不会读到过期数据。
原文