HashMap (常考)
HashMap (常考)
只关注一点就行了, 就是是否线程安全. 其他不用记!
HashMap线程不安全, Hashtabe线程安全
Hashtabe的线程安全是大量使用synchronized加锁, 性能差, 已经不会使用了
并发环境下建议使用ConcurrentHashMap, 它的性能更好.
结合ConcurrentHashMap那一节的内容答
HashMap底层数据结构, 1.7和1.8有何不同?
1.7的HashMap是哈希表, 数组 + 链表.
1.8的HashMap是数组 + (链表或红黑树)
HashMap什么时候进行扩容
HashMap 默认的初始化大小为16, 默认负载因子为0.75.
当hashmap中的元素个数超过数组大小*负载因子(loadFactor)时,就会进行数组扩容.
之后每次扩充,容量变为原来的 2 倍
HashMap为什么要使用红黑树, 为啥不用平衡二叉树
当某个位置, Hash冲突严重, 则链表的长度会很长. 那么查找的时候依次比较, 效率会很低 O(n).
将链表转为红黑树, 因为红黑树是排序树, 查找效率一般是O(logN), 使用红黑树就提高了查找效率.
平衡二叉树追求绝对平衡,每次插入新节点之后需要旋转的次数不能预知, 自平衡效率低
红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,自平衡的效率高