在网上看了很多资料,找到一篇讲哈希表的,感觉非常不错,推荐直接去看原文,散列表的基本原理与实现
下面内容是我的一些为加深记忆而复制的笔记,并无新意。
散列表的工作过程:
- 首先我们使用散列函数将给定键转化为一个“数组的索引”,理想情况下,不同的key会被转为不同的索引,但在实际应用中我们会遇到不同的键转为相同的索引的情况,这种情况叫做碰撞。解决碰撞的方法我们后面会具体介绍。
- 得到了索引后,我们就可以像访问数组一样,通过这个索引访问到相应的键值对
在网上看了很多资料,找到一篇讲哈希表的,感觉非常不错,推荐直接去看原文,散列表的基本原理与实现
下面内容是我的一些为加深记忆而复制的笔记,并无新意。
散列表的工作过程:
前面两篇扯了哈希函数是什么及有什么特性(内容多从网上筛选,稍许考证整理而来),这篇接着来说说有哈希函数都有什么应用
在上一篇文章中试着搞清楚到底什么是哈希,这一篇就再接着看看,什么是哈希函数,以及它有什么特点。
一听到「函数,算法」反正我是觉得瞬间胆怯,惧怕,充满了敬畏,就像一个虔诚的穆斯林走向麦加时的心情。
哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入,在计算上是不可能的,所以数据的哈希值可以检验数据的完整性。一般用于快速查找和加密算法 ---《数据结构与算法分析》
搞不清上面文字了,看下面这个图:
刚在吃饭回来的路上,走路时候闲的蛋疼,问了下自己什么是哈希?结果一下给自己搞蒙了。仔细想想工作中每天都在与这个叫哈希的家伙打交道,不是HashMap,就是MD5,SHA1的,但你若问我什么是哈希的,我压根就回答不上了来,或者说给一个确切的解释。直观感觉就是,不是中文“传统”词语,读起来就别扭,很难通过词来达意。
从网上搜了下“哈希”,发现没有直接关于“哈希”这个词的解释,都是周边相关的,例如,哈希函数,哈希算法,散列函数,哈希表什么的。 初步给人感觉这个词语极有可能是一类东西的统称,就像水果,汽车这样词语。
后来又google了英文hash [hæʃ]
发现维基百科中关于hash在计算机方面的解释,也是罗列了一些哈希函数,哈希表这样相关词语。
首先要扯明白的是,二进制比计算机的出现要早几千年,它不是为计算机量身打造的。十进制我们平时生活经常用到,一种有趣的说法是,之所以人们生活中更常用十进制,是以为我们有十个手指头,更容易学习理解其「逢十进一」的规则,使用起来只要掰指头,孩子教育也容易多了。
但是十进制这种掰指头的使用场景,在计算机中却难以行通。据说早期的计算机,也是用十进制,利用齿轮的不同位置表示不同的数值,毕竟这种计算装置更接近人类的思考方式。比如说一个计算设备有十个齿轮,它们连接起来,每一个齿轮有十格,小齿轮转一圈大齿轮走一格,就像钟表。这就是一个简单的十位十进制的数据表示设备了,可以表示0到9999999999的数字。 配合其他的一些机械设备,这样一个简单的基于齿轮的装置就可以实现简单的十进制加减法了。
例如:两套这样的装置A,B,且规定顺时针加法,逆时针转是减。那么当要计算5+3时候,第一步,先在A,B装置上顺时针初始化5和3. 接着用一个传动装置连接它们两个,且传动的规则是,逆时针转动B时候,A顺时针转(加法),这样我们只需要把B装置上的3,一直转到最初状态也就是0. A装置就自动计算出了5+3的值。 为了节省体力,我们可以转动时候用水流来带动且搞一个卡子,当装置回到0位置时候就卡住,水推不动了。当要计算大数字时候(意味着要转很久),我们祖先去狩猎吃饭,等回来时候就可以直接看到结果了。
端午假期待在家里没事,生性厌倦社交,自然不会在这难得的大好之光主动去找人灯红酒绿。在房间里走来走去,无聊至极就想到了一个和自己做游戏的事「想一个常用到词语,然后去验证自己对这个词语的理解是否正确,或接近规范」
首先这个词语肯定不是「最早发现于汉朝xxx王的墓中」,不是国产的。英文Byte[baɪt]
,翻译成中文字节,我觉得还好,至少比计算机世界中其他奇葩的翻译,譬如句柄,套接字 要强1024倍。
字节,在计算机中是用来表示一个完整字符的,这里的字符指英语语言系统中的字符,例如 A B C a b c...因为现代计算机是人美国人发明的。那为什么一个字节能表示一个完整的英文字母呢?
我们知道现在计算机 一个字节代表八个比特(英语:Bit) 也就是 1Byte=8Bit
,而 比特(英语:Bit),指二进制中的一位,是信息的最小单位。Bit是Binary digit(二进制数位)的缩写.
实际工作中不时会遇到需要在服务器上临时请求一个url,看下这个url返回的数据是否正常或者查看一些http响应头信息,以验证自己临时一个想法,这时候如果还从服务器切换到桌面,再打开浏览器,输入url,F12...就显得特别繁琐,会打断这种工作的「连续性」。
还好,linux下我们可以通过
curl
这个命令来模拟浏览器发起一次请求,然后得到和提取数据。
下面看示例,发起一次get请求,查看北京市的经纬度(返回json数据):
[od]$ curl -XGET "http://gc.ditu.aliyun.com/geocoding?a=北京市"
{"lon":116.40752,"level":1,"address":"","cityName":"","alevel":4,"lat":39.90403}
上面,-XGET
是可以省略的,默认就是get方式。其它常见参数还有-XPOST,-XPUT,-XDELETE
X后面可以有空格,例如-X GET
在之前一篇文章《【Linux】配置文件貌似被人动了》中,说到过一种直观的比较两个文件的命令diff -y file1 file2
.今天再说一个也常用的,习惯的,易于接受的参数-u
该缩写来自单词 unified ['ju:nifaid] 统一,一致
即命令diff -u file1 file2
,少啰嗦,看命令示例:
下面,先看要比较的两个文件的内容:
[work]$ cat ./test1.txt
111
222
331
555
[work]$ cat ./test2.txt