经典面试题-说明链表、哈希表、数组的特点

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42528266/article/details/103106190

• 1、链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
  • a)链表的存储在内存中可以是非连续性的，因为链表结构可以通过自身节点中的数据域指针域来找到下一个节点。
  • b)对链表进行删除插入操作时，只需要将其指针域进行修改即可（相对于数组来说内部操作更便捷）
  • c)链表本身不存在下标，所有查询效率略低。

一般而言进行删除修改等操作的时候使用的是链表结构，而查询的时候则使用数组结构,Java中由于linked的内部实现是采用链表结构。

• 2、散列表（Hashtable，也叫哈希表），是根据关键码值（Key Value）而直接进行访问的数据结构
  • a)哈希表最大的优势，就是把数据的存储和查询消耗的时间大大降低，几乎可以看成是常数时间。损失的代价仅仅是消耗比较多的内存，然而在当前可利用内存越来越多的情况下，用空间换时间的做法是相当值得的。而且编码也比较容易。
  • b)散列表查询速度快的原因：
    • i.将键值保存在某处，以便于能很快找到（数组中，这里保存的不是键本身而是键的信息，数组的下标就是这个对象的hashCode）
    • ii.查询的过程就变成了，首先生产该对象的HashCode，然后查询数组，，然后再去保存值的list当中查询
• 3、数组是一种物理存储单元上连续，顺序的存储结构，可以通过下标访问数组元素。
  • a)数组的保存效率高并且具备保存基本类型的能力。
  • b)数组是一种简单的线性序列，这使得访问速度非常快。
  • c)数组在定义时其大小被固定，并且在其声明周期中不可改变。
  • d)数组的查询速度，相对来说是比较快的，因为可以对其索引进行快速便利。