登录
/
注册
首页
论坛
其它
首页
科技
业界
安全
程序
社区
BBS
广播
Follow
园子
关于
博客
发1篇日志+1圆
记录
发1条记录+2圆币
发帖说明
登录
/
注册
账号
自动登录
找回密码
密码
登录
立即注册
搜索
搜索
关闭
CSDN热搜
程序园
精品问答
技术交流
资源下载
本版
帖子
用户
软件
问答
教程
代码
VIP申请
网盘
联系我们
道具
勋章
任务
设置
我的收藏
退出
腾讯QQ
微信登录
返回列表
首页
›
业界区
›
业界
›
白话算法(6) 散列表(Hash Table)从理论到实用(上) ...
白话算法(6) 散列表(Hash Table)从理论到实用(上)
[ 复制链接 ]
椎蕊
2025-5-29 19:18:43
处理实际问题的一般数学方法是,首先提炼出问题的本质元素,然后把它看作一个比现实无限宽广的可能性系统,这个系统中的实质关系可以通过一般化的推理来论证理解,并可归纳成一般公式,而这个一般公式适用于任何特殊情况。
——R.A. Fisher
在一个解决方案的复杂性之中,理论或者概念的部分通常只占有限的一小部分。理论无法做实际的工作——否则它也不成其为理论了。从理论到实用,需要经过一系列的发明。从实用到更加实用、更加通用,往往需要增加更多的复杂性。有时,这一过程远远超越科学的范畴,成为艺术家的乐园。有时,这一过程引入了过多不必要的复杂性,只是因为人类的自私、愚蠢和目光短浅。
科学不会也不能处理奇迹。科学只能处理重复的事件,艺术却不同。艺术是“就是如此”。在一个创作诞生以前,它是 Nothing——它没有来由、毫无征兆;诞生之后,它就是存在,是合理,是自然和美。我们所谈论的算法,作为一门实用的科学,既有科学的一面,也有艺术的一面。作为科学,它的结构可以分析,它的行为可以预测,它的属性可以量化,它的正确性可以证明。作为艺术,在一个算法诞生之后,有时我们只能说“它能工作”,仅此而已;对于它是如何来到这个世界上的,我们一无所知——这里没有“因为……所以……”,也不是简单的从一般到特殊。创造,似乎和生命一般神秘。我们可以给造物穿上漂亮的科学外衣,欣赏它内在的一致性,但是,最让人着迷的创造性的那一部分,却完全无法加以描述。
所以,当我们进行散列表的从理论到实用之旅时,如果你察觉到一些没有解释的跨越,请不要见怪吧。如果没有这些跨越,我们就完全可以设计一个程序发明这些算法,我们所要学习的算法也就完全会是另外一个样子了。
O(n) 查找和 O(1) 查找,两个模型
如果想知道在《伊利亚随笔选》这本书里是否有一个“囿”字,该怎么做呢?我们只有从第一页的第一行开始,一个字一个字地向后看去,直到找到这个字为止。如果直到最后一页的最后一个字都没有找到它,我们就知道这本书里根本没有这个字。所以,这项工作的复杂度是 O(n)。
再假设有这样一本《会计专用字帖》,它只有9页,每一页上有一个大写的数字:
当会计想要练习“柒”字时,只要她事先知道页码和内容的对应关系,就可以直接翻到第7页,实现 O(1) 复杂度的查找。通过这个模型我们知道,要想达成 O(1) 复杂度的查找,必须满足3个条件:
1. 存储单元(例如一页纸)中存储的内容(例如大写数字)与存储单元的地址(例如页码)必须是一一对应的。
2. 这种一一对应的关系(例如大写数字“柒”在第7页)必须是可以预先知道的。
3. 存储单元是可以随机读取的。这里“随机读取”的意思是可以以任意的顺序读取每个存储单元,并且每次读取所需时间都是相同的。与此相对的,读取磁带里的一首歌就不是随机的——想听第5首歌就不如听第一首歌来得那么方便。
在计算机上实现 O(1) 查找
先来看计算机的硬件设备。计算机的内存支持随机存取,从它的名字 RAM(random-access memory) 可以看得出对于这一点它还真有一点引以为傲呢。
既然硬件支持,我们就可以准备在计算机上模拟会计专业字帖了。第一项任务是向操作系统申请9个存储单元。这里有个小问题,我们得到的存储单元的地址很可能并不是从1到9,而是从134456开始的。好在我们并不需要直接跟操作系统打交道,高级语言会为我们搞定这些琐事。当我们使用高级语言创建一个数组时,相当于申请了一块连续的存储空间,数组的下标是每个存储单元(抽象)的地址。这样我们第一个 O(1) 复杂度的容器 SingleIntSet 很容易就可以完成了,它只能存储 0~9 这10个数字:
public class SingleIntSet
{
private object[] _values = new object[10];
public void Add(int item)
{
_values[item] = item;
}
public void Remove(int item)
{
_values[item] = null;
}
public bool Contains(int item)
{
if (_values[item] == null)
return false;
else
return (int)_values[item] == item;
}
}
复制代码
测试一下:
static void Main(string[] args)
{
SingleIntSet set = new SingleIntSet();
set.Add(3);
set.Add(7);
Console.WriteLine(set.Contains(3)); // 输出 true
Console.WriteLine(set.Contains(5)); // 输出 false
}
复制代码
新术语
:使用高级语言创建了一个整型数组时(例如 int[] values = new int[10]),我们不再把 values[7] 称为“一个存储单元”,因为存储单元的大小是一个字节,在32位操作系统上,values[7] 的大小是4字节,所以我们要使用一个新术语,把 values[7] 称为 values 数组的一个
槽(slot)
。
SingleIntSet2(说实话我真不喜欢这个名字,谁会喜欢?!)
新需求!同样只需要保存10个数字,只不过这次不是保存0~9,而是需要保存10~19,怎么办?很简单,实现一个槽里的值与地址的映射函数 H() 即可:
public class SingleIntSet2
{
private object[] _values = new object[10];
private int H(int value)
{
return value - 10;
}
public void Add(int item)
{
_values[H(item)] = item;
}
public void Remove(int item)
{
_values[H(item)] = null;
}
public bool Contains(int item)
{
if (_values[H(item)] == null)
return false;
else
return (int)_values[H(item)] == item;
}
}
复制代码
测试的时候,使用10~19范围内的数字:
static void Main(string[] args)
{
SingleIntSet2 set = new SingleIntSet2();
set.Add(13);
set.Add(17);
Console.WriteLine(set.Contains(13)); // 输出 true
Console.WriteLine(set.Contains(15)); // 输出 false
}
复制代码
房子不够住,难道睡马路?
这次,还是存储10个数字,只不过数字的范围是0~19。如何把20个数字存放到10个槽里?还能怎么办,2人住1间咯。略微修改一下 H() 函数,其它代码不变:
[code]public class SingleIntSet3{ private object[] _values = new object[10]; private int H(int value) { if (value >= 0 && value = 0 && value
回复
使用道具
举报
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
相关推荐
那些年搞不懂的高深术语——依赖倒置•控制反转•依赖注入•面向接口编程
如何优雅的使用RabbitMQ
分布式锁1 Java常用技术方案
浅谈我对DDD领域驱动设计的理解
游戏编程十年总结(下)
【前端性能】高性能滚动 scroll 及页面渲染优化
验证码对抗之路及现有验证机制介绍
从零开始入门 K8s | 手把手带你理解 etcd
中文写程序,何陋之有?
NHibernate之旅(2):第一个NHibernate程序
公司的中场
[一步一步MVC]第一回:使用ActionSelector控制Action的选择
FFmpeg开发笔记(六十二)Windows给FFmpeg集成H.266编码器vvenc
Android 系统缺陷不完全点评
.net环境下跨进程、高频率读写数据
模板模式
谈谈如何从本质上理解sql语句, 存储过程,ORM之间的联系和取舍。
从零开始学习jQuery (十一) 实战表单验证与自动完成提示插件
高级模式
B
Color
Image
Link
Quote
Code
Smilies
您需要登录后才可以回帖
登录
|
立即注册
回复
本版积分规则
回帖并转播
回帖后跳转到最后一页
签约作者
程序园优秀签约作者
发帖
椎蕊
2025-5-29 19:18:43
关注
0
粉丝关注
7
主题发布
板块介绍填写区域,请于后台编辑
财富榜{圆}
敖可
9986
背竽
9994
猷咎
9992
4
凶契帽
9992
5
终秀敏
9990
6
裴涛
9990
7
里豳朝
9990
8
处匈跑
9990
9
黎瑞芝
9990
10
松菊
9990
查看更多