数组、链表、哈希表的增删查改效率
数组、链表、哈希表的增删查改效率
由图可知,
-
哈希表
的平均创建时间最长,但是插入、删除和查找平均用时最少。 -
数组
创建用时最少,但是插入、删除操作用时最多,查找用时仅次于链表。 -
链表
除了查找用时最大,其余都排在数组和哈希表之间。
由以上数据可知,数组的优势在于创建数组用时少,可以适用于规模较小的数据。
链表创建时间比哈希表稍快(约17倍),但是查找用时是哈希表的1000倍以上,是数组的7倍左右。这意味着你要花较多的时间来方便你的插入、删除,但是查找还是算了吧,反正我是不会想经常去查链表里存储的东西的。
哈希表在插入、删除、以及查找操作方面有着优异的表现,但是超长的创建时间
提醒:除非你之后要进行大量的增删查改,不然还是用数组来的方便快捷。每次执行代码我的机器总是在创建哈希表的时候要停顿一下。
为什么哈希表能够加快查找效率?
很多语言都提供map的数据类型,map一个很常用的功能,那就是key-value 的存储和查找功能。这种数据类型的实现原理就是通过哈希表来实现快速查找。
哈希表的基本原理:原本无序的集合经过哈希算法被重新调整位置,排列成新序列,也就是hash table(与其说是表,不如说是某种数据结构的数组)
哈希表的好处,查找复杂度为常数量级o(1),快!
哈希表的代价,需要通过哈希算法将原始序列映射到hash table上,并且构建hash table需要分配一段内存,从本质上说这是一种空间换时间的办法。
哈希是什么?为什么哈希存取比较快?
不太恰当的比喻:
XM 指的是“小明”,也指的是“小萌”
XM就是哈希值,小明和小萌就是拥有同一个哈希值的,存在同一个链表的元素。
想要获取小萌,首先使用hashcode获取到这两个人,然后再通过equals获取到小萌。
个人理解
哈希表
其实就是一个一维数组,而数组中的每一个元素都是一个单向链表而已。这样的数据结构解决了 数组的增删元素的不足 和 链表的查询效率的不足。
数组是存在连续的存储空间,而链表的存储空间不连续