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表

好了，重点来了，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树。

平衡二叉树(AVL树)二三树红黑树

到此，关于“java中Hash表与树的介绍”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注创新互联网站，小编会继续努力为大家带来更多实用的文章！