算法那些事
1、哈希表
1.1 构造规则
- 必须是一致的
- 计算简单
- 散列地址均匀分布
1.2 散列函数构造方法
1)直接定址法
数组其实就是一张哈希表
f(key) = key
1 | // 通用公式 |
2)数字分析法
该方法也是十分简单的方法,就是分析我们的关键字,取其中一段,或对其位移,叠加,用作地址。比如我们的学号,前 6 位都是一样的,但是后面 3 位都不相同,我们则可以用学号作为键,后面的 3 位做为我们的散列地址。如果我们这样还是容易产生冲突,则可以对抽取数字再进行处理。我们的目的只有一个,提供一个散列函数将关键字合理的分配到散列表的各位置。这里我们提到了一种新的方式,抽取,这也是在散列函数中经常用到的手段。
3)折叠法
主要思路是将关键字从左到右分割成位数相等的几部分,然后叠加求和,并按散列表表长,取后几位作为散列地址。
4)除法散列法
在用来设计散列函数的除法散列法中,通过取 key 除以 p 的余数,将关键字映射到 p 个槽中的某一个上,对于散列表长度为 m 的散列函数公式为
1 | // 最经典的算法 |
5)乘法散列法
构造散列函数的乘法散列法主要包含两个步骤
- 用关键字 k 乘上常数 A(0 < A < 1),并提取 k A 的小数部分
- 用 m 乘以这个值,再向下取整
1 | // kA mod 1 的含义是取 keyA 的小数部分,即 kA - ⌊kA⌋ 。 |
6)平方取中法
假设关键字是 321,那么他的平方就是 103041,再抽取中间的 3 位就是 030 或 304 用作散列地址。再比如关键字是 1234 那么它的平方就是 1522756 ,抽取中间 3 位就是 227 用作散列地址.
7)随机数法
取关键字的随机函数值为它的散列地址。也就是 f(key) = random(key)。这里的 random 是 随机函数。
1.2 处理散列冲突的方法
1)开放地址法
开放地址法就是一旦发生冲突,就去寻找下一个空的散列地址,只要列表足够大,空的散列地址总能找到,并将记录存入,为了使用开放寻址法插入一个元素,需要连续地检查散列表,或称为探查,我们常用的有线性探测,二次探测,随机探测。
1 | 线性探测: f,(key) = ( f(key) + di ) MOD m(di = 1,2,3,4,5,6....m-1) |
2)再哈希法
1 | // 利用不同的哈希函数再求得一个哈希地址,直到不出现冲突为止 |
这里的 RH,就是不同的散列函数,你可以把我们之前说过的那些散列函数都用上,每当发生冲突时就换一个散列函数,相信总有一个能够解决冲突的。这种方法能使关键字不产生聚集,但是代价就是增加了计算时间。是不是很简单啊。
3)链地址法
4)公共溢出区法
1.3)散列表性能分析
1.散列函数是否均匀
2.处理冲突的方法
3.散列表的装填因子
2、栈
栈(stack)是限制插入和删除只能在一个位置上进行的表,该位置是表的末端叫做栈的顶(top),对栈的基本操作有 push(进栈)和 pop(出栈),前者相当于插入,后者则是删除最后插入的元素。
Java 中栈的实现
1 | Deque<TreeNode> stack = new LinkedList<TreeNode>();//类型为TreeNode |
3、队列
像栈一样,队列(queue)也是表。然而使用队列时插入在一端进行而删除在另一端进行,遵守先进先出的规则。所以队列的另一个名字是(FIFO)。
队列的基本操作是入队(enqueue):它是在表的末端(队尾(rear)插入一个元素。出队(dequeue):出队他是删除在表的开头(队头(front))的元素。
Java 中队列的实现
1 | Queue<TreeNode> queue = new LinkedList<TreeNode>(); |
4、链表
链表是一种递归的数据结构,他或者为空(null),或者是指向一个结点(node)的引用,该结点含有一个泛型的元素和一个指向另一条链表的引用。