我的Java学习笔记 二

数组

数组存储数据的方式是在内存中开辟一块连续的空间，按照数组中元素索引的顺序依次存储元素。所以数组元素在逻辑上是连续的，在真实的物理空间中也是连续的。因为这一特性，数组的查询十分便捷，可以直接访问任一数组元素获取该元素的值，其时间复杂度为O（1）。但是数组的删除与插入操作效率较低，因为插入或删除某元素，很可能要同时移动大量的其他元素，其时间复杂度为O（n）。而且因为真实物理地址的连续性，数组一旦初始化完成，其长度就是固定的，所以当数组中元素的存储密度较小时，即数组比较空时，数组对空间的利用率较低。且数组对空间要求比较严苛，因为它总是要求一块完整的空间。

链表

链表存储数据的方式是，在每一个节点中既存放有元素本身，还存放了指向特定元素的指针。比如在单链表中，每个节点就存有元素本身及指向下一个元素的指针，这样所有的链表元素就像一条链子被串了起来。因此链表元素在物理空间中的存储一般是不连续的，因此链表没有索引。不支持随机访问，链表元素的查询需要依次遍历链表中的元素，效率较低，时间复杂度为O（n）。但链表的插入删除操作只需要修改指针就可以完成，不需要移动大量元素，所以效率很高。因为以上特性，链表的空间分配比较灵活，可以利用零散分布的物理空间。但当存储密度较高时，链表的空间利用率低于数组，因为链表需要额外的空间来存储指针。

HashMap

hashmap以键值对的形式存储元素，其结构结合了数组与链表，且在jdk1.8版本之后引入了红黑树。

hashmap在初始状态下，即没放入任何元素时，就是一个默认长度为16的数组，当有新元素要放入时，通过计算新元素键的hashcode获得其在数组中存放的位置即索引。
然后判断，当此位置为空时，直接存入该元素。当有元素存在时，即发生了哈希冲突，此时根据equals方法判断已存放元素的键与新元素的键是否内容相同，如果相同则用新元素的value直接覆盖旧元素。如果键内容不同，则将新元素链接在旧元素之后，即生成了一个链表。

当数组中存放的元素达到阈值（数组长度*负载因子）时，若新存放元素时发生哈希冲突，则数组扩容为原来两倍。原数组内容复制到新数组，且重新计算hashcode获取位置。

当hashmap中任一个链表长度大于8且此时数组长度大于64时，将此链表转化为红黑树。

以下为hashmap的原理图：