哈希表和树

Posted on Edited on In Disqus: Symbols count in article: 2.1k Reading time ≈ 2 mins.

哈希表

哈希表的本质就用数组支持按照下标随机访问的特性，实现查找、删除、插入数据的时间复杂度为 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) 。

本周的时间实在是不够用的，关于堆、图的题目都还没有练习，下周的课程又开始了，要再加加油了～～