本文转载自微信公众号《Java极客技术》，作者鸭血范。转载本文请联系Java极客技术公众号。如果你是一名Java程序员，你一定对HashMap不陌生。巧的是，只要去面试，大概率都会被问到HashMap。那你一定要读读这篇文章。HashMap的底层数据结构先说一下HashMap的底层数据结构。HashMap的底层数据结构在1.7版本和1.8版本有些不同，但一般都是以数组+链表的形式实现。1.7版本是这样的：1.8版本是这样的：very可以很明显的看出1.8版本多了一颗树？还是红黑的？这是分析1.7版本HashMap实现的不足之处。1.7版本主要是数组+链表，所以如果有hash值，总会发生碰撞，对应的链表结构会越来越长。这个时候如果要再进行查询操作，会非常耗时，所以怎么优化这个就是1.8版本想要实现的1.8版本。数组+链表+红黑树实现。当链表长度大于8时，链表会转为红黑树。这时候，问题就来了。为什么把链表给红黑树的值设置为8呢？因为链表的时间复杂度是n/2，而红黑树的时间复杂度是logn。当n等于8时，log8小于8/2。这时候红黑树的搜索速度会更快。为什么小于6的时候转链表，7的时候不转链表？频繁的从链表切换到红黑树，再从红黑树切换到链表，开销会很大，尤其是频繁的从链表切换到红黑树的时候，需要旋转。为什么要把链表转成红黑树而不是平衡二叉树（AVL树）呢？因为AVL树比红黑树保持更严格的平衡。在AVL树中从根到最深叶子的路径最多为1.44lg(n+2)，而在红黑树中最多为2lg(n+1)，所以AVL树搜索的效果会是快点。如果是搜索密集型任务，用AVL树比较好。相反，对于插入密集型的任务，使用红黑树的效果更好。AVL树将存储每个节点上的平衡因子。AVL树的旋转优于红黑树。旋转更难平衡和调试。如果都是O(lgn)次查找，AVL树可能需要O(logn)次旋转，而红黑树最多需要两次旋转才能达到平衡。为什么HashMap线程不安全？?HashMap的线程不安全主要体现在两个方面：扩容引起的死循环和数据覆盖扩容引起的死循环。这个问题只会在1.7及之前的版本出现，因为在1.7及之前的版本中，Implementation，使用headinsertion的方式，会导致循环链表的问题。什么时候触发扩容？如果存储的数据大于当前HashMap的长度（Capacity）*负载因子（LoadFactor，默认为0.75），那么就会发生Expansion。比如当前容量为16，16*0.75=12，当存储到第13个元素时，判断需要扩容，那么此时HashMap会先进行扩容操作。扩容并不是简单地扩大原有的容量而已。展开时，先新建一个Entry空数组，长度是原数组的两倍。扩容完成后，会再次进行ReHash，即将原Entry数组中的数据重新散列到新的数组中。假设现在有一个Entry数组，大小为2，那么当我们插入第二个元素时，大于2*0.75，那么此时就会发生扩容，如下图：扩容完成后,因为采用了head插入方式,所以后面的元素会放在head位置,所以可能是这样的:第一条记录是A.next=B,展开后是B.next=A,那么最后可能是这样：很明显是造成了死循环，比较好的是1.8版本以后，采用了尾部插入的方式解决了这个问题。还有一个问题，1.8版本没有解决，就是数据覆盖的问题。假设线程A和线程B同时执行put操作，特殊巧合这两个不同数据的hash值相同，位置数据为null，那么线程A和B应该都执行看跌操作。假设线程A在要插入数据的时候被挂起，然后线程B正常执行插入数据，然后线程A拿到CPU时间片开始插入数据，那么线程B的数据就被覆盖了，因为HashMap做的不加锁put操作，不能保证下一个线程获取到的值一定是未修改的值，所以HashMap是不安全的。既然HashMap线程不安全，你推荐一个安全的？如果推荐，那么肯定推荐ConcurrentHashMap。说到ConcurrentHashMap，还有一个比较有意思的地方，就是ConcurrentHashMap1.7版本和1.8版本的实现也是不一样的。在1.7版本中，ConcurrentHashMap使用段锁（ReentrantLock+Segment+HashEntry）实现，即将一个HashMap分成多个段，然后为每个段分配一个锁，以支持多线程环境下的访问。但是这个锁的粒度太大了，因为你直接锁了一个section，所以1.8版本又做了优化，使用CAS+synchronized+Node+红黑树来实现，降低了锁的粒度，使用synchronized同时与ReentrantLock相比，会节省更多的内存空间。HashMap其实是可以扩展的，比如HashMap和HashTable的区别，ConcurrentHashMap1.7版本和1.8版本的具体实现等等。不过这篇文章已经很长了，就此打住吧~
