学习笔记

HashMap:

get(Object key):哈希表为了解决哈希冲突，有如下解决办法 (1)二次映射法。 (2)哈希函数映射的同一个位置用其他数据结构存储，通常是链表，但是当冲突比较严重时，链表过长，这时候查询的时间 复杂度会无线趋近于O(n)，为了高效查询，会引入红黑树(时间复杂度O(logn))来存储。查的时候需要比对两个值，一个是hash值，当hash 值相等代表映射到了同一个内存地址，然后会比对对应的值是否相等，当两者都相等才判定是同一元素。

put(K key, V value) java里的哈希表支持动态扩容，在++size > threshold时会调用resize方法将size变成原来的两倍， 当同一个哈希函数映射地址总节点大于等于8的时候会将链表转换成红黑树存储，以保证查询的高效性， 而当红黑树节点删减到小于6则会将红黑树转化成链表，节省空间。(java的源码真的不愧为工业级的，里面确实有很多细节性的优化啊)

树和图这两个数据结构当时大学的时候就学的不是很好，这周听超哥的课感觉清晰了很多，以前树的前中后序遍历都不怎么会， 主要是试图人肉递归，很容易把自己绕进去，现在直接背模板，然后让时间消化，一下过程简单了很多。虽然还是有部分理解知识点有疑问， 我理解是遍数过的不够导致的，后续题做多了应该就没啥问题了。

第二周比第一周适应点了，下周加油！！