大约在1951年,一种名为“全员生产维护”(Total Productive Maintenance,TPM)的质量保证手段在日本出现。它关注维护甚于关注生产。TPM的主要支柱之一是所谓的5S原则体系。
5S哲学包括以下概念。
整理(Seiri),或谓组织(想想英语中的 sort 一词)。
整顿(Seiton),或谓整齐(想想英文中的systematize 一词)。
清楚(Seiso),或谓清洁(想想英文中的 shine一词)。
清洁(Seiketsu),或谓标准化。
身美(Shitsuke),或谓纪律(自律)。勒布朗(LeBlanc)法则:稍后等于永不(Later equals never.)。
《编程珠玑续》
内容没有《编程珠玑(第2版)》好
书中例子主要使用的语言也是Awk,对现代程序员很不友好
Don Knuth给出了Fortran程序许多方面(包括性能监视)的经验研究。该论文中有一个被经常引用(而且常常是被错误地引用)的命题:“一个程序中不到4%的语句通常占用了一半以上的运行时间。”
“尾递归”:递归调用位于子程序的最后。通过把函数调用变成赋值和循环,可以消除尾递归。
测试只能证明程序有错误,而不能证明程序没有错误。—Edsger W. Dijkstra,得克萨斯大学
正确的判断来源于经验,然而经验来源于错误的判断。一Fred Brooks,北卡罗来纳大学
Little定律可以表述为“系统中的东西的平均数目等于这些东西离开系统的平均速度乘以每个东西离开系统所花费的平均时间”。(若系统的总体出入流是干衡的,离开速率也就是进入速率。)
尾递归:调用总是程序的最后一个动作。尾递归的程序总能转换成一个等价的while循环。
《程序是怎样跑起来的(第3版)》
“计算机组成原理”图解趣味版,挺不错的极简科普书。
第三版的译者周自恒是也是《代码的未来》的译者。
图 11-9 PIO与DMA的差别
CPU 是寄存器的集合体
BCD就是一种用紧數替代小教的格式,它用4比特来表示0~9的1位十进制数,具体方式在这里不做数述。BCD 格式常用于不允许有计算误差的金融领域。
BCD (Binary Coded Decimal,二进码十进数)是一种数据格式,在大型计算机中比较常用。在编程语言中,COBOL 使用的就是BCD格式。BCD分为非压缩(zoned)和压缩(packed)两种编码方式。对于占用多个字节的数据,将数据的低位存放在内存低地址的方式称为“小端序”(little endian)。与之相对,将数据的高位存放在内存低地址的方式称为“大端序”(big endian)。本章中的图示均采用 Intel 架构 CPU 所使用的小端序方式。
运行环境=操作系统+硬件
WYSIWYG 是“What You See Is What You Get”(所见即所得)的缩写,意思是屏幕上显示的文字和图像(What You See)可以按原样(Is)打印出来(What You Get)。
32位x86架构 CPU的寄存器的名称都是以e开头的,如cax、ebx、ecx、edx等,这是因为16位x86架构 CPU 中对应的寄存器的名称分别为ax、bx、cx、dx,这个e表示扩展(extended)。另外,64位x86架构CPU的对应寄存器的名称分别是rax、rbx、TOx、rdx,都以r开头,这里的r代表寄存器(register)。
《软件开发的201个原则》
这本书的英文原版写于 1995年,翻译开始于2019年(由训练营的百度工程师学员自发)。
这本书是百度“代码的艺术”课程(由作为百度代码规范委员会主席,也是百度技术培训中心金牌讲师的章淼博士开设)的教材。
这本书的作者是计算机科学家(伊利诺伊大学厄巴纳-香槟分校计算机科学博士)Alan M.Davis,曾任Requisite公司的董事会创始成员,被Rational Software收购,后来被IBM收购(1995—1997)。怪不得对需求非常了解。
图 P-1 本书的组织
图 1-1 原则、技术、语言、工具
原则 66 不要重复造轮子
原则 92 程序首先是写给人看的
原则 94 先确保正确,再提升性能
原则 145 衡量开发效率没有完美的方法
原则 147 不要设定不切实际的截止时间
原则 187 如果没有坏,就不要修理它
有两种原型:一次性(throwaway)原型和演进式(evolutionary)原型。一次性原型用快速而粗糙的方式构建,交给客户用以获得反馈,在得到期待的信息后即被废弃。获得的信息被整理进需求规格说明,用于正规的产品开发。演进式原型用高质量的方式构建,交给客户用以获得反馈,获得期待的信息便开始进行修改,以更加贴近客户的需求。重复此过程,直到产品收敛到所期望的样子。
在软件行业,一次次见证了:提供给用户的功能(或性能)越多,用户想要的功能(或性能)就越多。
爱德华 •伯索夫(Edward Bersoff)等人将系统工程的第一定律定义为:无论你处在系统(开发)生命周期中的何处,系统都将发生变化,并且对其进行改变的愿望将在整个生命周期中持续存在。
托尼•霍尔(Tony Hoare)说过:
构建软件设计有两种方法。一种方法是使它简单到明显没有缺陷,另一种方法是使它复杂到没有明显的缺陷。KISS,即 Keep It Simple and Stupid。
耦合和内聚是由 Larry Constantine 和 Edward Yourdon 在20世纪
70年代定义的。它们依然是目前所知用来度量软件系统自身可维护性和适应性的最好方法。简单来说,耦合,是对两个软件组件之间关联程度的度量。内聚,是对一个软件组件内功能之间相关程度的度量。
我们要追求的是低耦合和高内聚。高耦合意味着,当修改一个组件时,很可能需要修改其他组件。低内聚意味着,难以分离出错误原因或者难以判断满足新需求而要修改的位置。虽然大量的错误可证明软件毫无价值,但是零错误并不能说明软件的价值
这是杰拉尔德•温伯格( Gerald Weinberg)的“无差错谬论”(Absence of Ertors Fallacy )。保守估算,在大型系统中,大约一半的软件错误出现在 15%的模块申,80%的软件错误出现在 50%的模块中。Gary OKimato 和GeraldWeinberg 的结论更引人注目,80%的错误是在仅仅 2%的模块中发现的(参见 Weinberg 的《质量 软件 管理》一书,Qualty Software Managetnent, Vol. 1: Systems Thinking, New York: Dorset House, 1992)。因此,在测试软件时,你可以这样认为,在发现了错误的地方,很可能会发现更多的错误。
有效度量测试进度的两个想法是:
1.每周发现新错误的比率。
- 暗中在软件中埋下已知的 bug(Tom Gilb 管这个叫bebugging)后,这些bug 到目前止被发现的百分比。
根据构造性成本模型(COCOMO)(见 Boehm, B., Software EngineeringEconomics, Englewood Cliffs, N.J.: Prentice Hall, 1984)估算,最优秀的人的效率是普通人的四倍。
走动管理,Managing By Walking Around (MBWA),指管理人员通过随机非正规的走动方式,来了解工作状态的管理方式。
假设你有10个人在做一个预期3个月完工的项目。现在你认为你将比计划晚 3个月完工,也就是说,你预估需要60人月(6个月x10个人)。你不能增加10个人并期望项目按计划进行。实际上,很可能因额外的培训和沟通成本,再增加10个人会使项目更进一步延期。这个原则通常叫作布鲁克斯定律(Brooks' Law )。
驻波(英文为 standing wave 或 stationary wave)为两个波长、周期、频率和波速皆相同的正弦波相向行进干涉而成的合成波。
认为灾难是不可能的想法往往导致灾难
这是杰拉尔德•温伯格(Gerald Weinberg)的“泰坦尼克效应"原则。开发大型软件系统需要尽可能多的制衡,以确保产品的质量。一种行之有效的技术是,让独立于开发团队的组织来进行确认和验证(V&V)。确认(Validation)是检查软件开发的每个中间产品以确保其符合之前产品的过程。例如,确认可确保:软件需求满足系统要求,高阶的软件设计可满足所有软件需求(而不是其他需求),算法可满足组件的外部规格说明,代码可实现算法,等等。验证(Verification)是检查软件开发的每个中间产品以确保其满足需求的过程。
你可以将V&V 视为儿童电话游戏的一种解决方案。在这个游戏中,让一群孩子排成一列,通过耳语传递一条特定的口头信息。最后一个孩子说出他/她听到的内容,很少能与敢初的消息相同。确认会使每个孩子问前一个孩子,“你说的是 ×吗?”验证会使每个孩子问第一个孩子,“你说的是×吗?”任何正在使用的大型软件系统都将经历不断的变化,因为系统的使用会使人想出新的功能。它会一直变化,直到从头开始重写变得更划算。这就是曼尼•雷曼(Manny Lehman)的“持续变化定律”(Law of Continuing Change)。
任何经历持续变化的软件系统都会变得越来越复杂,并且变得越来越杂乱无章。由于所使用的所有软件系统都会发生变化(见原则185),并且变化会导致不稳定,因此所有有用的软件系统都将朝着较低的可靠性和可维护性迁移。这就是曼尼•雷曼(Manny Lehman)的“熵增加定律”(Law of Increasing Entropy)。
维护期间对程序的修改(无论是改进功能还是修正缺陷)引入的错误远远超过最初的开发阶段。维护团队报告说,维护期间有 20% 到 50% 的改动会引入更多的错误。
《趁,此身未老》
《孤独远行》
《不过,一场生活》
《去,你的旅行》
《代码的未来》
所谓技术,就是用来解决现实问题的手段。
创造出一种人类和计算机都能够理解的语言(编程语言),并通过这样的语言将人类的意图传达给计算机,这样的行为就叫做编程。
由于通过提高单一CPU的密度来实现性能的提升已经非常困难,因此在一个LSI中集成多个CPU的方法逐渐成为主流。
“巴纳姆效应”是一种心理学现象,指的是将一些原本是放之四海而皆准的、模棱两可的一般性描述往自己身上套,并认为这些描述对自己是准确的。
很多算命先生和自称预言家的人,实际上都是利用了被称为“冷读术”(Cold reading)和“热读术”(Hotreading)的技巧,来让人们相信他们真有不同寻常的“能力”。
冷读术,就是通过观察对方言行举止中的一些细微之处来进行揣测的技巧,就像夏洛克·福尔摩斯对他的委托人所运用的那种技巧差不多。
热读术则是通过事先对对方进行详细的调查,来准确说出对方的情况(逢场作戏)。由助记符自动生成机器语言的汇编器,以及由人类较易懂的算式型语句生成机器语言的编译器,当时都被认为是革新性的技术,被称为“自动编程”。
从编程语言的进化过程来看,一个显著的关键词就是“抽象化”。抽象化就是提供一个抽象的概念,使用者即便不具备关于其内部详细情况的知识,也能够对其进行运用。由于不必了解其内部的情况,因此也被称为“黑箱化”。
在数据抽象化的延长线上,就自然而然产生了面向对象编程的概念。所谓对象,就是抽象化的数据本身,因此面向对象和数据抽象化之间仅仅隔了薄薄的一张纸。
人类一次所能掌握的概念数量是有限的,有说法称,大部分人一次只能驾驭7±2个左右的概念。
在讲述软件开发的一本名著《人月神话》中,作者弗雷德里克·布鲁克斯写道:无论使用什么编程语言,生产一条基本语句所需要的工数几乎是一定的。
在我看来,编程语言的进化动机,不是工具和语言本身的简化,而是将通过这些工具和语言所得到的结果(解决方案)更简洁地表达出来。
基于上述观点,如果要我来预测100年后编程语言的样子,我认为应该会是下面三种情况的其中之一:
(1)变化不大。编程语言的写法从20世纪80年代开始就几乎没有什么进化,今后即便出现新的写法,也只是现有写法的变形而已。(从发展上来看,是比较悲观的未来)
(2) 使用编程语言来编程这个行为本身不存在了。人类可以通过和计算机对话(大概是用自然语言)来查询和处理信息。(类似《星际迷航》中的世界,对于编程语言家来说是比较失落的未来)
(3) 发明了采用更高抽象度写法的编程语言。这种语言在现在很难想象,不过应该是比现在更加强调What,而对于如何解决问题的How部分的细节,则不再需要人类去过问。(难以预测的未来)20年后的语言,应该是在分布处理(多台计算机协作处理)和并行处理(多个CPU协作处理)功能上进行强化,使得开发者不需要特别花心思就能够使用这些功能。
总之,未来的编程语言可能不会像过去的编程语言那样,让语言本身单独存在,而是和编辑器、调试器、性能分析器等开发工具相互配合,以达到提高整体生产效率的目的。
所谓DSL(Domain Specific Language,特定领域语言),是指利用为特定领域(Domain)所专门设计的词汇和语法,简化程序设计过程,提高生产效率的技术,同时也让非编程领域专家的人直接描述逻辑成为可能。DSL的优点是,可以直接使用其对象领域中的概念,集中描述“想要做到什么”(What)的部分,而不必对“如何做到”(How)进行描述。
像以这些迷你语言为代表的,由专用的语言引擎来实现的DSL,称为外部DSL。
内部DSL并不是创造一种新的语言,而是在现有语言中实现DSL,而作为DSL基础的这种现有语言,称为宿主语言。仔细想想就会发现,不涉及对象领域的内部细节,而是在高级层面上进行描述,这就是近半个世纪以来编程语言进化的方向——抽象化。
据说,在诞生了UNIX的AT&T贝尔实验室[插图]中有一句名言:库设计就是语言设计(Library design is languagedesign)。
我们可以通过“编程达人”大卫·托马斯[插图]的这句话理解这一过程:
Programming is a process of designing DSL foryour own application.
(编程就是为自己的应用程序设计DSL的过程)曾经在诸多Ruby相关活动中发表过演讲的著名Rubyist——Glenn Vanderburg认为,构成一种优秀的(内部)DSL的要素包括下列5种:
❑ 上下文(Context)
❑ 语句(Sentence)
❑ 单位(Unit)
❑ 词汇(Vocabulary)
❑ 层次结构(Hierarchy)描述数据所具有的结构的数据,也就是关于数据本身的数据,被称为元数据(Metadata)。
小说中的角色如果知道自己所身处的故事是虚构的,这样的小说就被称为元小说(Metafiction)。
所谓元编程,就是“用程序来编写程序”的意思。
在Ruby和Lisp这样的语言中,由于程序本身的信息是可以被访问的,因此在程序运行过程中也可以对程序本身进行操作,这就是元编程。硬盘的容量比内存大,但相对的,速度却非常缓慢,如果和硬盘之间的数据交换过于频繁,处理速度就会下降,表面上看起来就像卡住了一样,这种现象被称为抖动(Thrushing)。应该有很多人有过计算机停止响应的经历,而造成死机的主要原因之一就是抖动。
将内存管理,尤其是内存空间的释放实现自动化,这就是GC(Garbage Collection)。
所谓垃圾(Garbage),就是需要回收的对象。
如果程序(通过某个变量等等)可能会直接或间接地引用一个对象,那么这个对象就被视为“存活”;与之相反,已经引用不到的对象被视为“死亡”。将这些“死亡”对象找出来,然后作为垃圾进行回收,这就是GC的本质。
所谓根(Root),就是判断对象是否可被引用的起始点。至于哪里才是根,不同的语言和编译器都有不同的规定,但基本上是将变量和运行栈空间作为根。主要的GC算法。
1.标记清除(Mark and Sweep)是最早开发出的GC算法(1960年)。它的原理非常简单,首先从根开始将可能被引用的对象用递归的方式进行标记,然后将没有标记到的对象作为垃圾进行回收。
2.标记清除算法有一个缺点,就是在分配了大量对象,并且其中只有一小部分存活的情况下,所消耗的时间会大大超过必要的值,这是因为在清除阶段还需要对大量死亡对象进行扫描。
复制收集(Copy and Collection)则试图克服这一缺点。在这种算法中,会将从根开始被引用的对象复制到另外的空间中,然后,再将复制的对象所能够引用的对象用递归的方式不断复制下去。
这种算法的另一个好处是它具有局部性(Locality)。在复制收集过程中,会按照对象被引用的顺序将对象复制到新空间中。于是,关系较近的对象被放在距离较近的内存空间中的可能性会提高,这被称为局部性。局部性高的情况下,内存缓存会更容易有效运作,程序的运行性能也能够得到提高。
3.引用计数(Reference Count)方式是GC算法中最简单也最容易实现的一种,它和标记清除方式差不多是在同一时间发明出来的。
它的基本原理是,在每个对象中保存该对象的引用计数,当引用发生增减时对计数进行更新。
实现容易是引用计数算法最大的优点。标记清除和复制收集这些GC机制在实现上都有一定难度;而引用计数方式的话,凡是有些年头的C++程序员(包括我在内),应该都曾经实现过类似的机制,可以说这种算法是相当具有普遍性的。
除此之外,当对象不再被引用的瞬间就会被释放,这也是一个优点。其他的GC机制中,要预测一个对象何时会被释放是很困难的,而在引用计数方式中则是立即被释放的。而且,由于释放操作是针对每个对象个别执行的,因此和其他算法相比,由GC而产生的中断时间(Pause time)就比较短,这也是一个优点。
引用计数最大的缺点,就是无法释放循环引用的对象。
引用计数的第二个缺点,就是必须在引用发生增减时对引用计数做出正确的增减,而如果漏掉了某个增减的话,就会引发很难找到原因的内存错误。
最后一个缺点就是,引用计数管理并不适合并行处理。进一步改良的应用方式
1.分代回收(Generational GC)的基本思路,是利用了一般性程序所具备的性质,即大部分对象都会在短时间内成为垃圾,而经过一定时间依然存活的对象往往拥有较长的寿命。
像这种只扫描新生代对象的回收操作,被称为小回收(Minor GC)。
首先从根开始一次常规扫描,找到“存活”对象。这个步骤采用标记清除或者是复制收集算法都可以,不过大多数分代回收的实现都采用了复制收集算法。
在分代回收中,会对对象的更新进行监视,将从老生代对新生代的引用,记录在一个叫做记录集(remembered set)的表中。在执行小回收的过程中,这个记录集也作为一个根来对待。
这种检查程序需要对所有涉及修改对象内容的地方进行保护,因此被称为写屏障(Write barrier)。
2.在对实时性要求很高的程序中,比起缩短GC的平均中断时间,往往更重视缩短GC的最大中断时间。
为了维持程序的实时性,不等到GC全部完成,而是将GC操作细分成多个部分逐一执行。这种方式被称为增量回收(IncrementalGC)。
3.并行回收的基本原理是,是在原有的程序运行的同时进行GC操作,这一点和增量回收是相似的。像标记清除和复制收集这样,从根开始进行扫描以判断对象生死的算法,被称为跟踪回收(Tracing GC)。
美国IBM公司沃森研究中心的David F. Bacon等人,于2004年发表了一篇题为“垃圾回收的统一理论”(A UnifiedTheory of Garbage Collection)的论文,文中阐述了一种理论,即:任何一种GC算法,都是跟踪回收和引用计数回收两种思路的组合。所谓正常化偏见(normalcy bias)指的是人们的一种心理倾向,对于一些偶然发生的情况,一旦发生了便会不自觉地忽略其危害。
使用特殊返回值这个方法不需要编程语言的支持,是一种非常简便的方法,但它有两个重大的缺点。
第一,由于对错误的检测不是强制进行的,可能会出现没有注意到发生了错误而继续运行程序的情况。
第二,原本的程序容易被错误处理埋没。在Java中调用某个方法时,对于在该方法定义中所声明的异常,如果没有用异常处理来进行捕获,且没有用throws继续抛给上层的话,就会产生一个编译错误,因为异常已经成为方法的数据类型的一部分了。像这样的异常被称为检查型异常(checked exception)。在广泛使用的编程语言中,Java应该是第一个采用检查型异常的语言。
在Icon中,还有一种叫做every的控制结构,它可以对所有的组合进行尝试,直到失败为止。Icon的这种求值方式,由于包含了“继续求值到达到某种目标为止”的含义,因此被称为目标导向求值(Goal-directed evaluation)。
Eiffiel中强调了一种称为Design by Contract(契约式设计,简称DbC)的概念。即所有的方法(在Eiffel中称为子程序)都必须规定执行前需要满足的条件和执行后需要满足的条件,当条件不能满足时,就会产生异常。
这样的思路,就是将对子程序的调用,看作是一种“只要兑现满足先验条件的约定,后验条件就必定得到满足”的契约。如果key不存在的情况完全是超出预计的,错误就应该作为异常来处理;反之,如果key不存在的情况在某种程度上是预计范围内的,那么就应该返回错误值。
所谓函数对象,顾名思义,就是作为对象来使用的函数。
所谓高阶函数,就是用函数作为参数的函数。
高阶函数这样的方式,通过将一部分处理以函数对象的形式转移到外部,从而实现了算法的通用化。
作用域(Scope)指的是变量的有效范围,也就是某个变量可以被访问的范围。
从函数对象中能够对外部变量进行访问(引用、更新),是闭包的构成要件之一。
所谓生存周期(Extent),就是变量的寿命。相对于表示程序中变量可见范围的作用域来说,生存周期这个概念指的是一个变量可以在多长的周期范围内存在并被能够被访问。
在函数对象中,将局部变量这一环境封闭起来的结构被称为闭包(Closure)。因此,C语言的函数指针并不是闭包,JavaScript的函数对象才是闭包。
“过程与数据的结合”是形容面向对象中的“对象”时经常使用的表达。对象是在数据中以方法的形式内含了过程,而闭包则是在过程中以环境的形式内含了数据。JavaScript中方法与函数的区别很模糊,同样一个函数,在作为通常函数调用时,和作为对象的方法调用时,this的值会发生变化。
所谓静态,就是不实际运行程序,仅通过程序代码的字面来确定结果的意思;而所谓动态,就是只有当运行时才确定结果的意思。
有一种叫做JIT(Just In Time)编译的技术,可以在运行时将字节码转换成机器语言,经过转换之后就可以获得和原生编译一样快的运行速度。
在JavaScript中与服务器进行异步通信的API叫做XMLHttpRequest,因此从它所衍生出的手法便被称为Ajax(Asynchronous JavaScript and XML,异步JavaScript与XML)。
所谓CGI(Common Gateway Interface, CGI,通用网关接口),是通过Web服务器的标准输入输出与程序进行交互,从而生成动态HTML页面的接口。
所谓静态,就是无需实际运行,仅根据程序代码就能确定结果的意思;而所谓动态,则是只有到了运行时才能确定结果的意思。
所谓动态运行模式,简单来说,就是运行中的程序能够识别自身,并对自身进行操作。对程序自身进行操作的编程,也被称为元编程(Metaprogramming)。
动态类型的立场是数据拥有类型,且只有数据才拥有类型;而静态类型的立场是数据拥有类型,而存放数据的变量、表达式也拥有类型,且类型是在编译时就固定的。
所谓子类型(Subtype),是指具有继承关系,或者拥有同一接口,即静态类型与数据的类型在系统上“拥有同一性质”。
不考虑某个对象到底是哪一个类的实例,而只关心其拥有怎样的行为(拥有哪些方法),这就是鸭子类型(Duck Typing)。
像这样,以类型的结构来确定可代换性的类型关系,被称为结构子类型(Structural Subtyping);另一方面,像Java这样根据声明拥有继承关系的类型具有可代换性的类型关系,被称为名义子类型(Nominal Subtyping)。
如果忘记对不需要的对象进行释放,程序所占用的内存容量就会不断增大,从而导致内存泄漏(Memory leak)bug;反过来,如果释放了仍然在使用中的对象,就会导致内存空间损坏的悬空指针(Dangling pointer)bug。
JIT是Just In Time Compiler的缩写,指的是在程序运行时将其编译为机器语言的技术。
所谓特殊化,指的是一种在将函数转换为内部表达时所运用的技术。通过假定参数为特定类型,事先准备一个特殊化的高速版本,在函数调用的开头先执行类型检查,当前提条件成立时直接运行高速版本。动态语言运行速度慢的理由之一,就是因为在运行时需要伴随大量的类型检查,而通过特殊化则可以回避这一不利因素。
所谓CoffeeScript,一言以蔽之,就是用Javascript实现的用于编写JavaScript的方便语言。
对于没有任何前提条件的查找,线性查找几乎是唯一的算法,但实际上,大多数情况下,数据和查找条件中都存在着一定的前提。利用这些前提条件,有一些算法就可以让计算量大幅度减少。
从计算量的角度来看,理想的数据结构就是散列表。散列表是表达一个对象到另一个对象的映射的数据结构。Ruby中有一种名为Hash的内建数据结构,它就是散列表。从概念上来看,由于它是一种采用非数值型索引的数组,因此也被称为“联想数组”,但在Ruby中(Perl也是一样)从内部实现上被称为Hash。而相应地,Smalltalk和Python中相当于Hash的数据结构则被称为字典(Dictionary)。
不同的数据拥有相同散列值的情况,被称为“冲突”。
在散列表的实现中,应对冲突的方法大体上可以分为链地址法(chaining)和开放地址法(open addressing)两种。
链地址法是将拥有相同散列值的元素存放在链表中,因此随着元素个数的增加,散列冲突和查询链表的时间也跟着增加,就造成了性能的损失。
开放地址法则是在遇到冲突时,再继续寻找一个新的数据存放空间(一般称为槽)。
在采用链地址法的Ruby的Hash中,当冲突产生的链表最大长度超过5时,就会增加散列表的槽数,并对散列表进行重组。另外,在采用开放地址法的Python中,当三分之二的槽被填满时,也会进行重组。布隆过滤器(Bloom filter)是一种可以判断某个数据是否存在的数据结构,或者也可以说是判断集合中是否包含某个成员的数据结构。
像布隆过滤器这样“偶尔会出错”的算法,被称为概率算法(probabilisticalgorithm)。
在分布式环境下工作的散列表被称为DHT(DistributedHash Table,分布式散列表)。