空间换时间Space-time Tradeoff

Counting Sort

问题

给定一个序列，需要排序

序列中有有限的元素种类，比如 都是又 1 2 3 4 四个数组成的

解决方案

构建一个数组，数出每个元素的个数。

然后就可以直接输出排序后的序列

Set

定义

什么是

ADT

哆啦A梦的肚兜

功能

可以加元素

可以删除元素

可以检查一个元素在不在

限制

不需要保留顺序, 不知道顺序

元素不能重复

案例

set.add(1)      -> {1}
set.add(2)      -> {1, 2}
set.add(1)      -> {1, 2}
set.remove(1)   -> {2}

对比

Set & Bag

bag 和 set 一样，但是 可以重复

{1, 1, 2}  合法 

Set & List

借用 List 实现 Set

方案

如何实现以下方法

add(e)
contains(e)

Hash

是什么

var / array / link / hash 

机制

有一个 基本 array

任何放进去的元素 都要计算 生辰八字

计算的结果 要 对 array 的尺寸求余

操作的分析和问题

Add 时间复杂度 分析

O(1)

Contains 问题

情况

如何确定一个人在不在之酒店里

解决方案

先用 hash 规则 确定房间，检查是否有人

Contains 时间复杂度 分析

O(1)

Conflict 问题

情况

来的人不是GDG，但是求余也还是0，怎么住？

根本

生辰八字值一样 or 生辰八字不一样 但是 求余之后 一样

名词

Conflict

解决方案

后移

array 里面 套 list

Contains + Conflict 问题

情况

如果一个房间里有多个人，怎么确定一个人在不在

解决方案

先用 hash 规则 确定房间

再用 一般for 循环 遍历这个房间里的每一个人

Capacity 问题

情况

有 100 个包裹

有 10 层货架

每层货架 有 10 个包裹

根本

一个房间里的人太多，以至于不能优化时间复杂度

解决方案

hash 扩容

创建一个更大的 array，对原来的数组里 所有的元素 重新计算 hash

生辰八字 的 专业名词

hash

hashCode() -> int 

hash 的分析和问题

我们应该如何生成生辰八字

要注意哪些内容

hash 的范围 要尽可能的大

反面案例

1 2 

扩容也救不了你

hash 要 尽可能的不要成为有规律的倍数

反面案例

4 8 12 16 20

没有利用到一些格子

hash 要尽可能的均匀分布

反面案例

90% -> 1
10% -> 2 ~ 10000

没有利用到一些格子

同样一个数据 算出的 hash 必须是 稳定的

什么时候算出来都是一样的

否则，contains 会失效

结果

如果 hash 能够均匀分布，并且范围广

内部机制 根据 conflict 变多时，自动扩容

get / contains -> O(1)

Set

使用 Hash 实现 Set

时间复杂度分析

add(e)
contains(e)

Java API

HashSet 基本使用

放到 HashSet 里的人 必须实现

hashCode 
equals