学习笔记

本周主要学习内容：

哈希表：也叫散列表，根据键访问值，这种映射函数叫做散列函数，存放记录的数组叫哈希表。

key会传一个值给哈希函数，哈希函数会返回一个下标，然后就把value存在下标指向的这个位置，hash函数选取的好，就会减少hash碰撞，这样查找效率也会高，一旦出现hash碰撞，就在相同下标的位置开链表，存放其他的value。

map: key-value对，key不重复

set: 不重复的元素集合 通过看set的java源代码，发现它背后使用的是map上使用的，set的是map的key，value找了一个object来占位。

hashmap:

这个类基于哈希表的Map接口实现。put(k key, v value)是用来添加键值对，containsKey()和containsValue()判断是否存在该键/值，返回布尔值。get(object key)通过键来找值，remove(object key)通过键来删除键值对。总的来说，查找，添加，删除都是O(1)的时间复杂度。

树：链表的指针指向多个节点的时候，就形成了树的结构。二叉树是指每个节点下只能有两个子节点，

通过前中后序遍历。

二叉搜索树指的是一颗空树或具有下列性质的二叉树：

1.左子树上所有节点的值均小于它的根节点的值 2.右子树上所有节点的值均大于它的根节点的值

3.左右子树也分别为二叉查找树

二叉搜索树的查询和插入都是O(logn)的时间复杂度。

Heap:可以迅速找到一堆数中的最大值或者最小值的数据机构。

将根节点最大的堆叫做大顶堆或大根堆，根节点最小的堆叫做小顶堆或小根堆。

大顶堆：查找O(1),删除O(logn),插入insertO(logn)orO(1)。

二叉堆：通过完全二叉树来实现：1.一个完全树，树种任意节点的值总是大于或等于其子节点的值。

父节点索引为i的话，左孩子为2i+1，右孩子为2i-1父节点为floor((i-1)/2)。

insert插入操作 HeapifyUp

delete删除操作HeapifyDown

图的属性

Graph(V,E)

V-vertex:点

1.度-入度和出度

2.点与点之间：连通与否

E-edge：边

1.有向和无向

2.边长

四种图

基于图的通用算法：DFS,BFS