【539 week 02】学习总结

[sunrise2075]

第二周学习总结

HashMap小总结

它实现了下面三个接口:

1. Map
2. Cloneable
3. Serializable

它继承了AbstractMap。

哈希表的基本特征就是，使用哈希函数定位表示key/value映射的键值对的存放位置下表。
质量高的哈希函数可以最大程度避免哈希碰撞，也可以说是哈希冲突。
哈希函数的输入值是键值对映射中的键值，输出这个键值对在内部数组中保存的index位置。当发生哈希冲突时，映射到同一位置上的键值对会组成一个链表，key的哈希值相同，但是键值对中值不相同的键值对会被保存在同一个链表。
在最新的Java8种，哈希冲突的键值对数量超过某个数值以后，链表会自动转化为一个数据结构更复杂，查询效率更高的红黑树。

哈希set的底层是基于哈希map实现的。

树和二叉树、二叉搜索树

数组和链表是一位数组，树是一种二位数据结构。

树只有一个根节点，一个根节点可以有至少一个最多不限个数的字节点。

树最常见的数据结构是二叉树，每个父节点最多有两个字节点。

二叉搜索树中父节点的值大于左子树种所有节点的值，小于所有右子树所有节点的值。这种定义本身暗含了一种递归的定义方式。

对二叉树的遍历有前序、中序、后序遍历。

本周课程从二叉搜索树引入递归方法。以前我只知道所谓递归就是函数自己调用自己。通过本节课学习，完善并且加深了对递归的理解认识。递归必须要有递归终止条件。老师的递归模板非常有用。