专栏首页Java阿呆java源码之数组、链表与哈希表

java源码之数组、链表与哈希表

数组

在java中,数组定义为一种基本类型,其可以通过下标获取到对应位置的数据。数组在内存中是一段连续的存储单元,每个数据依次放在每个单元中。分析这种结构,可以得出以下几个结论:

  • 创建一个数组,必须声明其长度,以在内存中寻找合适的一段连续存储单元。这也意味着数组的大小是固定的,我们无法动态调整其大小。
  • 想要获取数组中第i个元素,其时间复杂度是 O(1),因为可以根据其地址直接找到它。同理修改也是。
  • 数组对查询表现一般,要想查找一个元素,需要遍历,时间复杂度为O(n)。
  • 因为地址连续,想要在数组中插入一个元素是复杂的,因为从插入位置起,后边的所有元素都需要向后移动一位。同理删除也是,只是移动方向为向前。并且,当数组存满时,就无法继续插入了。
  • 因为数组要占据一整块内存,有可能产生许多的碎片,也可能因为找不到合适的内存块,而导致存储失败。

总结起来就是:数组大小固定,查找迅速,增删复杂,需要完整的内存块,容易产生碎片。

链表

链表是一种离散存储结构,其在内存中存储不是连续的,每个数据元素都通过一个指针指向其下一个元素的地址。根据指针域的不同,链表又分为单链表、双向链表、循环链表等。对于单链表而言,可以得出以下几个结论:

  • 声明一个链表时,不需要知道其长度,也不需要连续的内存块,所以其大小可以动态调整。
  • 链表的每个元素都分为数据域和指针域,前者是实际存储的数据,后者则指向下一个元素的地址。和数组相比,每个元素需要占用的内存更大了。
  • 要获取链表的第 i 个元素变得复杂,因为其地址存放在它上一个元素的指针域里,所以只能从第一个元素起,进行 i 次操作。同理修改也是。
  • 链表对查询表现也一般,需要遍历,时间复杂度为O(n)。
  • 增加与删除一个元素更方便了,因为没有对内存地址的限制,我们只需要在对应节点合理处理下指针域的值,就可以把一个元素插入链表或者从链表删除。
  • 链表对内存的要求很小,只要能够存储下一个数据元素的内存块都可以使用,因此不会造成碎片化。

总结起来就是:大小可以动态调整,增删迅速,查找较慢,数据元素所占内存略多,不需要整块内存块,不会造成碎片化。

数组与链表的选择

通过以上分析,数组和链表对我们影响最大的几点区别在于:

  • 数组按位置查找迅速,链表增删方便
  • 数组是固定大小,链表可以随时扩充与缩减
  • 链表每个元素占据内存略多于数组
  • 数组和链表在查询方面表现都比较一般,耗时较长

在数据量很小,内容基本固定时,选择何种数据结构的影响并不大。但当数据量较大时,如果我们需要对数据进行频繁的插入删除,就应该选择链表,如果我们需要频繁的获取某个位置的元素,就应该选择数组。数组与链表并没有明确的优劣之分,根据不同的使用场景进行不同的选择,才是这两种结构使用的最佳方式。

哈希表

无论是数组还是链表,其对数据的查询表现都比较无力,要想知道一个元素是否在数组或链表中,只能从前向后挨个对比。出现这个问题的根源在于,我们没有办法直接根据一个元素找到它存储的位置。哈希表就是解决查询问题的一种方案。

哈希表与Hash函数

通俗来讲,哈希表就是通过关键字来获取数据的一种数据结构,它通过把关键字映射为表中的位置来获取元素,这种映射主要是使用Hash函数。

Hash函数,实际上是建立起key值与int值映射关系的函数。这就好比每个人都有一个身份证号一样,无论是男是女,出生在何处,都可以通过身份证号来分辨,这就是把人的信息映射成一串数字的典型做法。Hash函数和此类似,不过是把任意的Java对象,映射成一个int数值,供哈希表使用。

而哈希表,就是一个数组,只是其元素不是按照数组的规则排列的。任何一个元素要放进哈希表中,都必须先通过Hash函数获取到一个int数值,这个数值经过处理后将作为它的存放位置,然后这个元素才能放进哈希表中。

哈希表完全继承了数组的优点,又显著的提高了查询的速度,通过Hash函数使得查询速度达到了O(1)。既然有了哈希表,它这么优秀,为何还需要数组的存在呢?那是因为Hash表是有缺陷的,这个缺陷就是哈希碰撞。

哈希碰撞

Hash函数所做的事,就是无论什么对象,都根据一个规则映射为一个int值。被转换的对象有无数种可能,但是int的值是有限的,它只有2^32个,这样一来,必然会有不同的对象,映射得到相同的int值,这就是所谓的哈希碰撞。发生碰撞之后,就要把不同的元素插入到相同的位置,这时候单纯的使用一维数组已经无法满足需求了。

目前比较通用的解决哈希碰撞的方法,就是使用数组+链表组合的方式。当出现哈希碰撞时,在该位置的数据就通过链表的方式链接起来,如下图所示:

这是当前比较理想的方法,既继承了数组的优点,又在碰撞时继承了链表的优点,这也是哈希表强大的地方之一。

在JDK1.7及之前的版本中,HashMap的存储结构和上图是一致的,在JDK1.8之后还加入了红黑树以进一步优化。

哈希表的优缺点

哈希表是一种优化存储的思想,具体存储元素的依然是其他的数据结构。设计良好的哈希表,能同时兼备数组和链表的优点,它能在插入和查找时都具备良好的性能。然而设计不好的哈希表,有可能会出现较多的哈希碰撞,导致链表过长,从而哈希表会更像一个链表。还有当数据量很大时,为防止链表过长,就需要对数组进行扩容,这时就涉及到了数组的拷贝,其对性能的影响也很严重,所以需要提前对可能的情况有良好的预测,才能真正发挥哈希表的优势。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ConcurrentHashMap源码(一)

    整体流程跟HashMap比较类似,大致是以下几步: (1)如果桶数组未初始化,则初始化; (2)如果待插入元素所在的桶为空,则尝试把此元素直接插入到桶的第一个位...

    Java阿呆
  • ConcurrentHashMap源码(二)

    删除元素跟添加元素一样,都是先找到元素所在的桶,然后采用分段锁的思想锁住整个桶,再进行操作。

    Java阿呆
  • Docker基础(二)

    数据卷是一个可供容器使用的特殊目录,它将主机操作系统目录直接映射进容器,类似Linux中的mount行为。

    Java阿呆
  • 从程序员转型到架构师的Java集合小抄

    以双向链表实现。链表无容量限制,但双向链表本身使用了更多空间,每插入一个元素都要构造一个额外的Node对象,也需要额外的链表指针操作。

    Java知音
  • 关于Java集合的小抄

    在尽可能短的篇幅里,将所有集合与并发集合的特征,实现方式,性能捋一遍。适合所有”精通Java”其实还不那么自信的人阅读。

    哲洛不闹
  • 2018-06-13 关于Java集合的小抄

    Albert陈凯
  • 学习算法必须要了解的数据结构

    简而言之,数据结构是一个以特定形式存储数据的容器。这种“形式”允许数据结构在某些操作中更加高效。

    深度学习与Python
  • 代码面试需要知道的8种数据结构(附面试题及答案链接)

    为了保证可读性,本文采用意译而非直译。另外,本文版权归原作者所有,翻译仅用于学习。

    Fundebug
  • 图解 | 不就是栈吗

    栈(stack)是一种先进后出,后出先进的数据结构。之所以这样,是因为栈是操作受限的线性表,允许元素进出的一端称为栈顶(top),不允许元素进出的一端称为栈底(...

    五分钟学算法
  • css中的block与none

    windseek

扫码关注云+社区

领取腾讯云代金券