java中Hash表与树的介绍
这篇文章主要介绍“java中Hash表与树的介绍”,在日常操作中,相信很多人在java中Hash表与树的介绍问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”java中Hash表与树的介绍”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
成都创新互联专业IDC数据服务器托管提供商,专业提供成都服务器托管,服务器租用,成都电信服务器托管,成都电信服务器托管,成都多线服务器托管等服务器托管服务。
jdk1.7中HashMap是由Hash表(即数组加链表)这种结构组成,而在jdk1.8后升级成了Hash表+红黑树用来提升数据的查询效率。下面将介绍hash表与红黑树。
Hash表
讲解hash表中我们先介绍线性检索
与二分搜索
:
把所有数据遍历,找到你所需要的数据。其对应的数据结构就是数组、链表等线性结构,这种方式对于大数据而言效率极低,其时间复杂度为O(n)。比如ArrayList中的indexOf
方法:
public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }
二分搜索算是对线性搜索的一个改进,比如说对于【1,2,3,4,5,6,7,8】,我要搜索一个数(假设是2),我先将这个数与4(这个数一般选中位数比较好)比较,小于4则在4的左边【1,2,3】中查找,再与2比较,相等,就成功找到了,这种检索方式好处在于可以省去很多不必要的检索,每次只用查找集合中一半的元素。其时间复杂度为O(logn)。但其也有限制,他的数排列本身就需要是有序的。
好了,重点来了,Hash表闪亮登场,这是一种时间复杂度为O(1)的检索,就是说不管你数据有多少只需要查一次就可以找到目标数据。
Hash表的本质在于可以通过value本身的特征定位到查找集合的元素下标,从而快速查找。一般的Hash函数为:要存入的数 mod(求余) Hash数组长度。
看了上面的讲解,机智的你们肯定已经发现了一个问题,通过求余数得到的地址可能是一样的。这种我们称为Hash冲突,如果数据量比较大而Hash桶比较小,这种冲突就很严重。我们采取如下方式解决冲突问题。
我们可以看到12和0的位置冲突了,然后我们把该数组的每一个元素变成了一个链表头,冲突的元素放在了链表中,这样在找到对应的链表头之后会顺着链表找下去,至于为什么采用链表,是为了节省空间,链表在内存中并不是连续存储,所以我们可以更充分地使用内存。
Hash表实现的HashMap见源码分析之HashMap (JDK7)
树
在JDK1.7中HashMap就采用了Hash表来存储数据,根据key计算出hashcode然后再与Hash数组长度求余得到Hash桶的位置。
如果很多的key产生了Hash冲突,那么每个桶里面的数据量比较大导致链表非常长,这样Hash表的优势就不复存在了,反而倾向于线性检索。
在jdk1.8版本后,java对HashMap做了改进,在链表长度大于8的时候,将后面的数据存在红黑树中,以加快检索速度。
在将红黑树之前我们先讲一讲常见的树:
二叉树就是每个父节点下面有零个一个或两个子节点,在向二叉树中存放数据的时候将比父节点大的数放在右节点,将比父节点小的数放在左节点,这样之后我们在查找某个数的时候只需要将其与父节点比较,大则进入右边并递归调用,小则进入左边递归。 缺点:假如数据本身就是有序的,比如【1,2,3,4,5,6,7】,这样就会导致树的不平衡,二叉树就会退化成为链表。所以我们推出了avl树。
到此,关于“java中Hash表与树的介绍”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!
新闻名称:java中Hash表与树的介绍
文章地址:http://pwwzsj.com/article/ppphsp.html