【数算-2】递归＆哈希表＆有序表

小鱼儿 2022-10-08 13:23 157阅读 0赞

# 1. 各种排序方式： #

> 需要记忆：

1）选择冒泡插入，插入最优，  
2）快排归并，快排分区分治很优秀  
3）桶计数，划分区域在范围内排序，计数省去排序

# 2. 递归行为： #

> 任何递归行为都可以变成非递归，改为迭代

public int  fun(a,b) {
        
    	// 这是跳出fun函数递归的条件
    	if (a == b) {
        
    		return xx;
    	}
    	int mid = xxx;
    	int a = fun (a, mid);
    	int b = fun (mid+1, b);
    	
    	return Math.max(a,b); 
    }

### 2.1 Master公式计算递归时间复杂度： ###

T ( N ) = a ∗ T ( N / b ) + O ( N ∧ d ) ( 其中的 a , b , d , 的递归函数，可以直接通过Master公式来确定时间复杂度 \\begin\{array\}\{l\} T(N)=a \* T(N / b)+O\\left(N^\{\\wedge\} d\\right)\\\\\\\\(\\text\{ 其中的 \} a, b, d \\text \{ , \} \\text \{ 的递归函数，可以直接通过Master公式来确定时间复杂度 \} \\end\{array\} T(N)=a∗T(N/b)\+O(N∧d)(其中的a,b,d , 的递归函数，可以直接通过Master公式来确定时间复杂度

得到以下通式：

1) log ⁡ b a > d O ( N l o g b a ) 2) log ⁡ b a > d O ( N d ) 3) log b a = = d O ( N d ∗ log ⁡ n ) \\begin\{array\}\{l\} \\text \{ 1) \} \\left.\\log \_\{b\} a>d \\quad \\quad O (\{N\}^\{ \{ log \}\_\{b\} a\}\\right) \\\\ \\text \{ 2) \} \\log \_\{b\} a > d \\quad \\quad O\\left(N^\{d\}\\right) \\\\ \\text \{ 3) \} \\text \{ log \}\_\{b\} a==d \\quad O\\left(N^\{d\} \* \\log \_\{n\}\\right) \\end\{array\}  1) logba>dO(Nlogba) 2) logba>dO(Nd) 3)  log ba==dO(Nd∗logn)

**Tip：**  
a 是调用的次数  
b 是问题规模，  
d 是除了递归过程之外的时间复杂度的值

# 3. 哈希表 #

哈希函数在Java中，最常见的地方是Object类，是native封装好的,对外界是一个黑盒,将无限集转化为有限集的操作.

[哈希函数的介绍][Link 1]http://www.alloyteam.com/2017/05/hash-functions-introduction/

1、ConcurrentHashMap在FWD节点中就是使用的开放地址法  
2、还有链表、树……  
3、算法范围`MD5：0~2^64-1` `SHA1：0~2^128-1` 单位：bit

Tips：  
扩容步骤是，创建一个新的较大的哈希表（假如大小为m），将原哈希表中的数据取出，将键值的哈希值模上m，放入新表对应的桶中，这个过程也叫rehash。（类似寻址算法(hash ^ hash >>> 16) & (n-1) ）

### 3.1 HashMap 和 HashSet的区别 ###

HashMap  <key, value> 
    	put ()
    	remove ()
    	containskey ()
        
    HashSet  <key>
        add()
        contains()
        remove()

HashMap 和 HashSet的区别在于是否存在 value；

对于这个表的操作时间复杂度均为 O（1）

### 3.2 引用传递和值传递 ###

public static void main(String[] args) {
        
        Integer a = 1000000;
        Integer b = 1000000;
    
        //包装类型间的相等判断应该用equals，而不是'=='
        System.out.println(a == b);
        System.out.println(a.equals(b));
    
        Integer c = 127;
        Integer d = 127;
    
        //包装类型间的相等判断应该用equals，而不是'=='
        System.out.println(c == d);
        System.out.println(c.equals(d));
    }
    
    result :  
    "A:\Program Files\Java\jdk-12.0.1\bin\java.exe" -
    false
    true
    true
    true

> \-128 ~ 127内的数字都会变成池里面的东西，和标准的字面值一样。  
> （自动装箱和拆箱）

### 3.3 与HashMap的不同： ###

HashMap 中的 <Integer, String>是采用值传递的。

非基础类key是用引用传递，（）内存地址。

# 4. 有序表： #

TreeMap <Integer, String >

自然排序，可以乱序插入，但是**结果还是有序**的，而且可以获取第一个，最后一个元素。

但是里面的操作都是O（n）的时间复杂度。

### AVL、SB树、红黑树、跳表 ###

**SB树：**  
根据叔叔节点和侄子节点的不同key的数量决定是否平衡（总是保证叔叔节点的数目和兄弟之间的差距在2倍以内。）可以删除的时候省去resize操作，在add的时候进行resize操作。

**红黑树：**  
定义了非常多的规则，而且每条规则都是各自独立的，  
增加节点的时候有五种可能：空树、已存在、父节点为黑节点、父红且叔红、父红且叔黑或空。维护红黑的过程比较复杂。

**AVL树：**  
维护了每个节点的子节点之间的高度差不能大于1。（维护平衡性是最为严格的）

更高级的（非搜索二叉树）  
**跳表**

平衡性都是不同的，

搜索二叉树。内部结构其实是有序的。

1）有序表：key是有序的；java中红黑树实现  
2）使用上和hash表的使用方式一致，  
3）哈希表所有的方法都是O(1)，但有序表所有的方法都是O(log(N))  
4）有序的Api：floorKey、cellingkey

**左旋右旋：**  
LL：右旋  
LR：左旋 =》LL =》右旋  
RL：右旋 =》RR =》左旋  
RR：左旋

**搜索树的删除：**  
1）没有左右孩子：直接删除  
2）有左无右：左孩子代替自己的位置，移除自己  
3）有右无左：右孩子代替自己的位置，移除自己  
4）有左有右：左树的最右节点/右树的最左节点来替换位置  
有没有右树，有的话进行替换操作

## 区别： ##

### 1）时间复杂度： ###

SizeBalanceTree、跳表、红黑树、AVL树：他们在使用上的时间复杂度只在于**常数级别的区别**（没啥不同，只不过是实现的时候各有各的逻辑，各自的操作有差异），但是任何操作时间复杂度都是O(log(N))；

### 2）操作细节： ###

都是基于搜索二叉树来做自己的调整；各种最终的实现都是在做完左旋右旋操作之后进行调整上区别。（resize方法不一样）  
![在这里插入图片描述][b2283305dfdf4140b8f0b19ef8ade3e7.png]  
自平衡二叉搜索树的底层都实现好了左旋右旋的方法，剩下的就随便自己去调用就好了……  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]

### 3）结构： ###

红黑树是江河日下的结构了，实现上来说比较难，SB树和跳表还算是比较容易实现的结构；红黑树的调整：加入有五种情况，删除有八种情况需要考虑。  
但红黑树的引入  
1）解决查找效率问题  
2）尾插法解决了死循环问题

> 裸的搜索二叉树单方向插入造成O（N）的查询效率，如何解决？

## AVL树： ##

调整操作：  
1）任意Node左边节点与右边节点的高度差<=1  
2）每次发生变化之后都需要不断查找节点进行调整，直到最上层的节点

# 5. else #

## 布隆过滤器 ##

> ——在分布式的时候使用，并且具有比较好的拓展性

黑名单过滤器

**特点：**“宁可错杀三千，绝不放过一个”。

**应用：**  
1、爬虫进程之间的去重：维护一个共享的bitMap  
2、处理千亿级别的url黑名单

1.  一共有k个哈希函数 == 》 呈现出k个特征点
2.  长度为m ==》 输出域为m
3.  指定到特定的位置：(hash & (m-1))

// 获取低位状态
    int s = (arr[numIdx] >> (bitIdx & 1))
    // 指定的numIdx进行修改，改为1，或者改0。
    arr[numIdx] = arr[numIdx] | (1 << bitIdx) 
    arr[numIdx] = arr[numIdx] | (~(1 << bitIdx))

## 一致性哈希 ##

涉及key：多种类，而且频率需要均衡。  
在一个hash域中使用虚拟节点技术

[Link 1]: http://www.alloyteam.com/2017/05/hash-functions-introduction/
[b2283305dfdf4140b8f0b19ef8ade3e7.png]: /images/20221005/93de191b1ba94a72bc674893a5f64f21.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20221005/9029d82d2b4d40a5b5e2e139000ebf82.png