单独聊聊HashMap

hashmap 在工作中用的比较多，面试也喜欢问。hashmap的在内存中的存储是通过键值对的方式。 key 不允许重复，值可以，键允许一条key的值为空。java7 的时候数据结构为 链表+数组，而到了Java8 的时候就引入了 红黑树。 数组的结构特点是啥，查询快，插入删除慢；链表的结构特点是啥，查询慢， 插入删除快。 查询的时候，得通过指针去找， 而数组是有索引下标的，找值的时候，通过索引下标就能找到，查询起来也快。但插入的时候，数组还得新建新的数组，把原来的数据复制进去，再把新增的数据新增进来，新增就慢了。链表则不然，通过节点依次向后找，元素越多，找的越慢。 新增插入则只需要修改元素的下标地址就可以。删除也是通过移除对应元素的下标地址就可以了。那为啥hashmap 要引入红黑树呢。我觉得嘛，就是为了提高效率。这个效率体现在哪几点呢？ hashmap 很多元素的时候，这个桶就有长长的一个链表，这个时候，单链表有n个元素，遍历的时间复杂度就是O(n)，完全失去了它的优势。所以搞个红黑树撑撑场面。现在的动不动数据量就很大，不优化下，还能当集合中的老大哥嘛，真的是。 Java8就是顺势而为，把其数据结构加入了红黑树。 hashmap在Java7 的时候，hashmap 在put 的时候使用了头插法，会造成的死循环。 Java8 就改了这块， put元素的时候使用了尾插法。但是hashmap是线程不安全的， 在多线程环境下，使用就不行了。综合考虑，还是使用ConcurrentHashMap。