数组、线性表、二叉树、哈希表的对比_线性表和哈希表的区别

介绍哈希表之前,我们可以了解下其他结构在新增、查找等基础操作的执行性能

• 数组：一段连续的存储单元来存储数据。指定下标的查找，时间复杂度为O(1)；通过给定值的查找，需要遍历数组，逐一对比给定关键字和数组元素，时间复杂度为O(n),当然，对于有序数组，则可采用二分查找，插值查找，可将复杂度提高到O(logn)。对于一般的插入和删除操作，牵扯到元素的移动，其平均复杂度也为O(n)
• 线性链表：对于链表的新增、删除等操作，仅需处理节点间的引用即可，时间复杂度为O(n),而查找操作需要遍历链表进行逐一比对，复杂度为O(n)
• 二叉树：对于一颗相对平衡的有序二叉树，对其进行插入、查找、删除等操作，平均复杂度为O(logn)
• 哈希表：其中HashMap采用的是是数组+链表的结合结构，数组是HashMap的主体，链表是为了解决哈希冲突存在的，如果定位到的数组位置不含链表，对于查找、添加操作很快，一次寻址；如果定位到的数组包含链表，对于添加操作，需要遍历，所以HashMap中链表出现越少越好。利用数组的高效定位查找元素，利用链表的新增和删除快，同样这个是解决哈希冲突的一种方式，叫做链地址法