哈希表
哈希表的本质就用数组支持按照下标随机访问的特性,实现查找、删除、插入数据的时间复杂度为 O(1) 。哈希函数就是将 Key 转换为数组下标,将数据存放到指定位置。
而 哈希函数的本质就是取余操作,能将任何 Key,转换为有限范围内的一个数值。比方说任意大的正整数对 5 取余那么结果就是在 [0, 4] 。同理著名的 MD5 哈希函数,对任意长度的输入,其输出都是 128 bit,即 16 字节。
JDK 中 HashMap 将 Key 映射到哈希表数组下标方法是 tab[i = (n - 1) & hash]
,其实就是 tab[i = hash % n]
,tab
就存放数据的数组 table
,hash = key.hashCode() ^ (key.hashCode() >>> 16)
就 Key 的哈希值,n
就是哈希表的数组长度,翻译过来就是将 key 的哈希值对数组长度 - 1进行取余,结果作为数组下标存放数据。
由于数组的存储空间有限,很容易产生哈希碰撞,即不同的 Key 哈希出的数据下标是一样的,如果直接将数据存入数组中,会导致数据存储丢失。HashMap 中将数组称作为 bucket array(桶数组), 每个桶都会对应一条链表,将哈希值相同的元素都放到相同桶对应的链表中,来解决 Hash 碰撞的问题。
哈希表存放数据的位置完全是根据哈希函数的计算来的,所以数据的存放是无序的。即使在 LinkedHashMap
中通过双向链表,实现插入的顺序、或访问的 LRU, 但是还是无法做到对数据的排序,直观一点说就是无法直接获取 “> n” 的数据。
二叉树
树是在数组或链表的基础上赋予了节点位置信息,所谓的升维思想。
几种特殊的二叉树:
在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值,这就是二叉搜索树;
叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点,这就是满二叉树;
如果满二叉树,叶子节点虽然没有排满,但是叶子节点都靠左排列,这就是完全二叉树;
约束完全二叉树每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值,这就是堆。
二叉树的遍历
二叉树的遍历分为前序遍历、中序遍历、后序遍历这些都属于深度优先(DFS),层次遍历属于广度优先(BFS)。在 LeetCode 上这几种遍历题目都有,树的遍历递归写法最为清晰明了,栈的写法比较容易写废,我刷了 3 遍,才写熟练。为了方便理解,我把几种遍历的栈图画出来了,方便理解。
前序遍历
中序遍历
后序遍历
堆
堆是一种特殊的二叉树 - 完全二叉树。在上周的课程,课后作业分析 PriorityQueue
其实就带着学习了堆的特性。以小顶堆为例子,查找最小是 O(1)、删除最小是 O(logn),插入是 O(logn) 或是 O(1)。在堆中插入、删除数据为了维护最小元素在堆顶,分别涉及上浮、下沉的元素交换操作。
堆的应用场景有优先级队列,比方说 JDK 中的 PriorityQueue
。利用优先级队列我们可以解决 K 个有序数列合并
问题,将数列全部加入堆中,再依次取出即可。如果是将 K 个小文件合并成一个大文件,且内存中无法存放全部结果,可以依次从 K 个文件读取并删除第一个元素并放入堆中,然后取出堆顶的元素,放入合并文件中,再找到刚才堆顶元素对应的文件,读取并删除下一个元素,放入堆中,直到堆中无任何元素,合并任务就完成了。优先级队列还有个场景就是 延时/定时任务队列
,我们可以维护一个小顶堆,将到期时间早的放在堆顶,定时检查堆顶元素就可以知道整个队列有没有任务到期,避免了对整个队列的轮询检查,提高了性能。
堆还常用于解决 Top K
问题,根据不同的场景用大顶堆或小顶堆,并保证堆的大小为 K,Top K 就是堆中所有的元素。
总结
这两周的学习,发现数据的存储结构只有两种:数组、链表,他们就是构成计算机数据结构的 “基本粒子”,其他的数据结构只是在其基础上演进。栈、队列、哈希表、树、图底层实现都是数组或链表,或者两者都可以实现。
升维的本质就是给数据的位置增加特殊的位置含义。比方说,树用数组存放,当根的数组下标是 i (i > 0)
,那么左孩子的下标就是 i * 2
,右孩子的下标就是 i * 2 + 1
。
哈希表已经能做到对数据的查找、删除、插入 O(1) 的时间复杂度了,但是数据存储是无序的,不支持有序输出。如果使用二叉搜索树,我们只需要中序遍历,就是序输出了。
当向二叉搜索树有序插入一堆数据时候,二叉搜索树就会显得极度不平衡,退化成了链表,查找从 O(logn) 退化为 O(n),所以又有了平衡二叉查找树 - 红黑树,它能够始终保持在 O(logn) 。
二叉搜索树和堆又有什么关系呢?我们通过对二叉搜索树的中序列遍历可以得到一个有序序列,堆可以通过不断的从堆顶 poll 数据得到一个有序序列,这就是的堆排序;二叉搜索树会有退化不平衡的现象,而堆却不会;二叉搜索树获取最大或最小值都是 O(logn) ,但堆需要根据是大顶堆还是小顶堆才能获取最大值、还是最小值并且时间复杂是 O(1) 。
本周的时间实在是不够用的,关于堆、图的题目都还没有练习,下周的课程又开始了,要再加加油了~~