1、哈希表

1.1 构造规则
  • 必须是一致的
  • 计算简单
  • 散列地址均匀分布
1.2 散列函数构造方法
1)直接定址法

数组其实就是一张哈希表
f(key) = key

1
2
// 通用公式
f(key) = a * key + b a,b均为常数
2)数字分析法

该方法也是十分简单的方法,就是分析我们的关键字,取其中一段,或对其位移,叠加,用作地址。比如我们的学号,前 6 位都是一样的,但是后面 3 位都不相同,我们则可以用学号作为键,后面的 3 位做为我们的散列地址。如果我们这样还是容易产生冲突,则可以对抽取数字再进行处理。我们的目的只有一个,提供一个散列函数将关键字合理的分配到散列表的各位置。这里我们提到了一种新的方式,抽取,这也是在散列函数中经常用到的手段。

3)折叠法

主要思路是将关键字从左到右分割成位数相等的几部分,然后叠加求和,并按散列表表长,取后几位作为散列地址。

4)除法散列法

在用来设计散列函数的除法散列法中,通过取 key 除以 p 的余数,将关键字映射到 p 个槽中的某一个上,对于散列表长度为 m 的散列函数公式为

1
2
// 最经典的算法
f(k) = k mod p (p <= m)

5)乘法散列法

构造散列函数的乘法散列法主要包含两个步骤

  • 用关键字 k 乘上常数 A(0 < A < 1),并提取 k A 的小数部分
  • 用 m 乘以这个值,再向下取整
1
2
// kA mod 1 的含义是取 keyA 的小数部分,即 kA - ⌊kA⌋ 。
f (k) = ⌊ m(kA mod 1) ⌋
6)平方取中法

假设关键字是 321,那么他的平方就是 103041,再抽取中间的 3 位就是 030 或 304 用作散列地址。再比如关键字是 1234 那么它的平方就是 1522756 ,抽取中间 3 位就是 227 用作散列地址.

7)随机数法

取关键字的随机函数值为它的散列地址。也就是 f(key) = random(key)。这里的 random 是 随机函数。

1.2 处理散列冲突的方法
1)开放地址法

开放地址法就是一旦发生冲突,就去寻找下一个空的散列地址,只要列表足够大,空的散列地址总能找到,并将记录存入,为了使用开放寻址法插入一个元素,需要连续地检查散列表,或称为探查,我们常用的有线性探测二次探测随机探测

1
2
3
线性探测: f,(key) = ( f(key) + di ) MOD m(di = 1,2,3,4,5,6....m-1)

二次探测: f,(key) = ( f(key) + di ) MOD m(di =1^2 , -1^2 , 2^2 , -2^2 .... q^2, -q^2, q<=m/2)
2)再哈希法
1
2
// 利用不同的哈希函数再求得一个哈希地址,直到不出现冲突为止
f,(key) = RH,( key ) (i = 1,2,3,4.....k)

这里的 RH,就是不同的散列函数,你可以把我们之前说过的那些散列函数都用上,每当发生冲突时就换一个散列函数,相信总有一个能够解决冲突的。这种方法能使关键字不产生聚集,但是代价就是增加了计算时间。是不是很简单啊。

3)链地址法

4)公共溢出区法

1.3)散列表性能分析

1.散列函数是否均匀

2.处理冲突的方法

3.散列表的装填因子

2、栈

栈(stack)是限制插入和删除只能在一个位置上进行的表,该位置是表的末端叫做栈的顶(top),对栈的基本操作有 push(进栈)和 pop(出栈),前者相当于插入,后者则是删除最后插入的元素。

Java 中栈的实现
1
2
Deque<TreeNode> stack = new LinkedList<TreeNode>();//类型为TreeNode
Stack<TreeNode> stack = new Stack<TreeNode>();

3、队列

像栈一样,队列(queue)也是表。然而使用队列时插入在一端进行而删除在另一端进行,遵守先进先出的规则。所以队列的另一个名字是(FIFO)。

队列的基本操作是入队(enqueue):它是在表的末端(队尾(rear)插入一个元素。出队(dequeue):出队他是删除在表的开头(队头(front))的元素。

Java 中队列的实现
1
Queue<TreeNode> queue = new LinkedList<TreeNode>();

4、链表

链表是一种递归的数据结构,他或者为空(null),或者是指向一个结点(node)的引用,该结点含有一个泛型的元素和一个指向另一条链表的引用。

单链表

双向链表

5、树

5.1 相关概念