Java教程

读数据结构与算法之美(四)

本文主要是介绍读数据结构与算法之美(四),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

4.散列表&哈希&树

18 - 散列表(上):Word文档中的单词拼写检查功能是如何实现的?

散列表:Hash Table,又称哈希表,或者hash表。

散列表,用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,没有数组就没有散列表。

关键字:键(key)、哈希函数、散列值(value)

哈希函数的三个基本要求:

1.散列值是一个非负正数

2.key1==key2 则hash(key1)==hash(key2)

3.key1!=key2 则hash(key1)!=hash(key2)

第三点几乎不可能。无法避免散列冲突。

装载因子:填入表中的元素个数/散列表的长度

解决散列冲突的方法:

1.开放寻址法、2.链表法

19 - 散列表(中):如何打造一个工业级水平的散列表?

散列表的查询效率并不能笼统的说成是O(1)。它跟散列函数、装载因子、散列冲突等都有关系。

如果散列函数设计的不好,或者装载因子过高,都可能导致散列冲突发生的概率升高,查询效率下降

散列函数的设计,不能太复杂。

散列函数生成的值要尽可能随机并且均匀分布。

装载因子过大了怎么办?

可以进行动态扩容。重新申请一个更大的散列表,将数据搬移到这个新散列表中。

装载因子阀值需要选择得当。如果太大,会导致冲突过多;如果太小,会导致内存浪费严重。

如何避免低效的扩容?

当装载因子已经到达阈值,需要先进行扩容,再插入数据。这个时候插入数据就会变得很慢,甚至会无法接受。

为了解决一次性扩容耗时过多的情况,我们可以将扩容操作穿插在插入操作的过程中,分批完成。

当装载因子触发阈值之后,我们只申请新空间,但并不将老的数据搬移到新散列表中。

对应查询操作,先从新散列表中查找,如果没有找到,再去老的散列表中查找。

通过均摊的方法,将一次性扩容的代价均摊到多次插入操作中。

开放寻址法VS链表法

当数据量比较小、装载因子小的时候,适合采用开放寻址法。这也是java中ThreadLocalMap使用开放寻址法解决散列冲突的原因。

链表法比较适合存储大对象、大数据量的散列表,而且它更加灵活,支持更多的优化策略,比如用红黑树(或者跳表)代替链表。

举例分析HashMap

1.初始大小

2.装载因子和动态扩容

3.散列冲突解决方法

4.散列函数

20 - 散列表(下):为什么散列表和链表经常会一起使用?

链表实现的LRU缓存淘汰算法的时间复杂度是O(n),通过散列表可以将这个时间复杂度降低到O(1)。

Redis的有序集合不仅使用了跳表,还使用了散列表。

LRU缓存淘汰系统

一个缓存系统主要包含下面几个操作:

1.往缓存中添加一个数据

2.从缓存中删除一个数据

3.在缓存中查找一个数据

这3个操作都要涉及“查找”操作,如果单纯地采用链表的话,时间复杂度只能是O(n)。

如果将链表和散列表组合使用,可以将这3个操作的时间复杂度降低到O(1)。

23 - 二叉树基础(上):什么样的二叉树适合用数组来存储?

满二叉树:叶子节点都在最底层,除了叶子节点之外,每个节点都有左右两个子节点。

完全二叉树:叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大。

满二叉树,又是完全二叉树的一种特殊情况。

如何表示(或存储)一颗二叉树?

1.基于指针(或者引用)的二叉链式存储法

2.基于数组的顺序存储法

如果某棵二叉树是一棵完全二叉树,那用数组存储无疑是最节省内存的一种方式。

这也是为什么完全二叉树会单独拎出来的原因,也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

二叉树的遍历

1.前序遍历:打印自己→左子节点→右子节点

2.中序遍历:左子节点→打印自己→右子节点

3.后序遍历:左子节点→右子节点→打印自己

 

24 - 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?

1.散列表中的数据是无序存储的,如果要输出有序的数据,需要先进行排序。而二叉查找树的中序遍历,可以在O(n)的时间复杂度输出。

2.散列表扩容耗时很多,散列冲突时性能不稳定。二叉查找树性能也不稳定,但是平衡二叉查找树的性能非常稳定,时间复杂度O(logn)

3.哈希冲突以及哈希函数的耗时,性能不一定高

4.散列表的设计比较复杂

这篇关于读数据结构与算法之美(四)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!