Java8 HashMap源码的简单分析(1)

首先在阅读HashMap源码前,我们需要知道的: 一.数组:连续的存储结构,存储相同类型的数据。对于指定下标的查找,时间复杂度为o(1);对于定值的查找,需要遍历数组,时 间复杂度为o(n),对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn)。 二.单链表:离散的存储结构。单链表是由结点组成,而每个结点是由数据域和指针组成。单链表查询的时间复杂度最大为o(n);插入和删除仅需处理相邻结点之间的引用,时间复杂度为o(1)。 三.红黑树:红黑树是一种平衡二叉树,查询,修改,删除的时间复杂度均为o(lgn)。在jdk1.8后,主要适用于Ha