-
Notifications
You must be signed in to change notification settings - Fork 22
哈希表(Hash Table)
L edited this page Mar 16, 2020
·
1 revision
摘抄自HashMap实现原理分析、java中HashMap与Hash表详解
数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端
数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难
链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易
哈希表((Hash table)既满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便
哈希表有多种不同的实现方法,最常用的一种方法是拉链法
,我们可以理解为“链表的数组”
哈希表是由数组+链表组成的
,一个长度为16的数组中,每个元素存储的是一个链表的头结点
哈希表(Hash Table)是一种数据结构
;
哈希函数,是支撑哈希表的一类函数;
Map是映射、地图的意思,在Java中Map表示一种把K映射到V的数据类型;
HashMap是Java中用哈希数据结构实现的Map;
哈希算法,是一类算法;