HashMap在JDK1.7和1.8中的区别
2019-06-22 本文已影响0人
小明今晚加班
在JDK1.7中HashMap底层实现借助 数组+链表，在有哈希冲突的情况下，通过拉链法解决。
但是，如果稍微用点心的话，可以人为造成多个哈希冲突（Hash Collision DoS），最坏情况下，N个key的哈希值都一样，那么遍历的时候时间复杂度为O(n).
在JDK1.8中，为了解决链表过长引起查询过慢的问题，HashMap的底层实现做了修改，数组+链表（或红黑树）。当链表长度大于8的时候，会把链表转为红黑树来存储，我们知道红黑树的特点是查询复杂度在对数级别，因此可解决之前存在的链表过长造成查询不便的问题。（数组+红黑树的存储结构，最坏的查询情况才是lgN）
