Arnold Dumey。
Arnold I. Dumey was the co-inventor of the postal sorting machine and cryptanalyst first for ASA and then NSA. Dumey was also the inventor of Hashing. He published the first hashing paper[1] in 1956 while at IBM, where he co-invented the postal sorter. The "Dumey microsecond" is a term of art in the intelligence community of the United States where Dumey spent much of his career. The Dumey Microsecond was a crucial event that Arnold claimed was common to all projects: It is that microsecond during which you can impact the flow of, or design of, a project. Before this microsecond, it is too early. After, it is too late to have an impact.
Dumey was the longest serving member in the history of the NSA scientific advisor board.
散列函数与冲突及溢出处理方法综述编辑本段回目录
在计算机存储、检索的相关操作中，散列是一种基础的技术。它不是基于关键码比较来进行检索，而是通过函数来直接映射存储地址。这种想法最初是由IBM公司的H.P.Luhn 于1953年1月在一份内部备忘录中提出的(参考[1])，以后经过人们不断的实践研究，产生了各种各样的处理方法，直到最近仍有新成果发表。本文就散列技术中关键的散列函数和冲突溢出处理方法进行了分析、比较、总结，力图展现散列技术的基本思想，发展过程，并期望于以后的研究有一定帮助。
关键词：散列技术，散列函数，冲突，溢出处理，探查序列
检索是基本的应用操作，人们发明了各种各样的检索方法。有一大类的方法基于关键码的比较，如顺序检索，二叉树检索，分块检索等，这些方法所消耗的平均时间与记录集基数相关，记录集很大时，它们的检索效率将会降低 。本文介绍的散列方法是直接根据待检索记录值的检索，不涉及大量的记录关键码之间的比较，运行效率独立于记录集基数 。该方法的基本思想是 ：根据关键码值来确定记录的存储地址，不妨设关键码值为key，希望找到一个精巧的函数hash(key)(称为散列函数) ，可以用它的函数值来代表key的存储地址address 。理想情况下，可以建立key与address之间的一一映射，但通常情况下，总会发生两个以上不同的关键码key1 ,key2，key3……，keyi映射到相同地址的情况，这种情况称为“冲突”，key1 ,key2，key3……，keyi 称为“同义词”，它们有相同的基地址 。解决冲突有两种基本思路：一种是在散列主表外，为每个同义词组建立一个地址链，一般称之为开散列(Open Hashing)；另一种是直接在散列表内寻找空位，但是应该保证在检索时能够再次找到这些位置，这种方法称之为闭散列( Closed Hashing ) 。
散列思想 最初是由IBM的一批研究人员在工程实践中萌生的。H.P.Luhn 最早于1953年1月在一份IBM内部备忘录中提到线性散列方式(类似开散列中的拉链法)，之后不久A.D.Lin提出了处理散列空间块溢出的技术：分级地址法(degenerative addresses) 。同时散列思想还在IBM的另一研究组中形成，这一研究组成员包括：Gene M.Amdahl, Elaine M.Boehme ,N.Rochester 和Arthur L.Samuel, 当时他们正在为IBM 701设计一个汇编程序，为了解决遇到的地址冲突问题，Amdahl设计出了闭散列中的线性探查方法。Arnold I.Dumey在Computers and Automation 上首次公开发表了“散列方法” ，他提到了开散列方法，对闭散列没有涉及，有关散列的另一篇经典的文章是由IBM的W.W.Peterson 发表的。这一领域，近年仍有较好的文章发表，可见很活跃。
下面主要分散列函数，冲突及溢出处理，理论分析三部分来分析介绍散列技术，探讨各种方法的适用范围 ，以期系统化该技术，同时为后面的研究提供参考。
散列函数( HASHING FUNCTIONS )
在理想情况下，我们希望找到这样的散列函数：h(ki) = h (kj) 当且仅当ki= kj 。但是这样优秀的函数非常少。试着考虑一个定义域的基数是31 ，而值域的基数是41的函数集族 。这个集族中共有4131 ≈ 1050 个函数，但是仅有 41 * 40 * …… *11 = 41！/ 10！≈ 10 43 个函数是单根的(即两个自变量的函数值相等 当且仅当它们相等)，这意味着在这个集族中，我们想要的理想函数的比例是1/10million .
虽然理想散列函数的确非常稀少，但是我们可以发现另外一些函数，虽然难免发生冲突的情况，但是经实践证明有着很好的应用价值。设计一个散列函数时，我们需要考虑以下几点：
1. 散列函数的计算复杂度 。散列函数的计算复杂度直接影响到它得到结果的时间，在一些要求快速相应的系统中，过长的运行时间是不允许的。但是在另外的一些应用中，散列函数本身的计算时间影响不大，常见的涉及到外存(如磁盘)数据读取中，由于读外存需要较长的时间，散列函数所消耗的时间就成为次要考虑因素。在这种操作中，主要考虑的是如何减少访外次数，而不是降低散列函数的复杂度。
2. 散列函数的值域 。一般来说，散列表的长度是有限的，如果选取的散列函数的值域超出了散列表的长度，这个函数显然是不合适的。但是如果散列函数的值不能遍历整个散列表，又可能造成空间浪费。
3. 散列函数值的均匀性，也就是尽可能做到不同的关键码具有不同散列函数值 。如果函数值得均匀度直接影响到散列函数的使用效率，均匀度差的函数会带来过多的冲突，从而降低散列函数的利用价值。
4. 关键码的长度 。实际上，这与上面提到的散列函数的计算复杂度相关。考虑做除法的情况，如果关键码的长度超过一个机器字长，那么做除法的复杂度将会大大提高。遇到这种情况，一般会综合多种处理方法解决，常常先对关键码进行“折叠”，然后再使用选定的散列函数处理。折叠法的具体情况在下面有介绍。
5. 散列表的编址方式。存在一些散列函数，它涉及的操作依赖于散列表的编址方式。例如，除余法中选择除数时需要考虑散列表地址是十进制编码还是二进制编码
6. 机器的指令集 。有些机器中有除法指令，在另外一些机器中却仅有乘法指令 。我们应该考虑机器的指令集，以便设计出较为简单的散列函数。
