线性散列

✍ dations ◷ 2025-06-14 07:53:29 #线性散列

线性散列是由Witold Litwin（1980）发明并被Paul Larson推广的一种动态散列（dynamic hash）算法。线性散列表的每次扩张仅增加一个槽（slot、bucket），频繁的单槽扩张可以非常有效控制的冲突链的长度，从而哈希表扩展的代价摊还在每一次插入操作中。因此非常适合用于交互式应用程序。

散列表初始化时，先分配任意的数目的散列槽，并在运行过程中检测以下的值：

冲突（Collision）可以通过不同的方式来处理，最典型的处理方法是，每当发生溢出（overflow）插入操作后，与之对应创建一个新的散列槽，表的地址可以用以下的策略进行计算：

添加一个散列槽时：

所有这一切的是，该表分为三个部分；该部分之前 ${displaystyle }$ ${displaystyle }$ 该科从 ${displaystyle }$ ${displaystyle }$ 要 ${displaystyle }$ ${displaystyle }$ 和之后 ${displaystyle }$ ${displaystyle }$ 中。第一个和最后一个部分都存储使用 ${displaystyle }$ ${displaystyle }$ 与中部分储存使用 ${displaystyle }$ ${displaystyle }$ 中。每个时间 ${displaystyle }$ ${displaystyle }$ 到达 ${displaystyle }$ ${displaystyle }$ 表增加了一倍的大小。

Griswold和Townsend 讨论了线性散列在Icon language中的应用。他们讨论了使用线性散列作为动态数组的一种实现的效果，并得出了相关的性能比较。

线性散列用于在Berkely DB中，而Berkerly DB又用于许多的软件中（例如OpenLDAP)。它由C语言实现，原理基于一篇发表于CACM的文章。

相关

肺泡蛋白沉积症肺泡蛋白沉着症（pulmonary alveolar proteinosis，PAP），又名肺泡蛋白沉积症，是一种罕见的肺部疾病。患者体内肺表面活性物质衍生的脂蛋白化合物在肺泡内异常聚积，干扰肺部正常的气
The New Zealand Herald新西兰先驱报（英语：The New Zealand Herald）是在新西兰奥克兰发行的日报，由New Zealand Media and Entertainment所有，是新西兰发行量最大的报纸，2006年达到20万份以上，到2014年12
NFL国家美式橄榄球联盟（National Football League，NFL）是世界最大的职业美式橄榄球联盟，也是世界最具商业价值的体育联盟之一。联盟最早在1920年以美国职业美式橄榄球協会（American
MADS盒MADS盒蛋白（英语：MADS-box）基因是一大类与高等植物花器发育有关的调控基因，具有同源异形框基因的功能。MADS的命名由四个基因的第一个第1个字母组合而成，即酵母MCMI，拟南芥（Arabido
达美连接航空达美连接航空（Delta Connection）是达美航空的区域性航空品牌名。几家不同的区域性航空公司以此名义运营达美的中短程航线。达美全资拥有的航空公司Endeavor Air（英语：Endeavor A
四十年战争四十年战争（缅甸语：အနှစ်လေးဆယ်စစ်；1385年-1424年；又名阿瓦-勃固战争或孟人-缅甸人战争）是说缅甸语的阿瓦王国与说孟语的罕礁瓦底勃固王国之间发生的一场军事冲突
池昌旭池昌旭（韩语：지창욱，1987年7月5日－），韩国男演员，身高182公分。池昌旭自幼生长于京畿道的安养市。由于运动细胞极佳，各项运动都表现甚好。在高中时成绩表现优良，皆保持在班上前五名，甚
尼泊尔共产党（革命毛主义）尼泊尔共产党（革命毛主义）是尼泊尔的一个共产主义政党。2012年，尼泊尔联合共产党（毛主义）发生分裂，尼泊尔共产党－毛主义成立，由莫汉·拜
残酷舞台真实录《残酷舞台真实录 LIVE DVD》（英文:Show on Cruel Stage Live，简称《残酷舞台》）是台湾男歌手罗志祥于2008年7月11日发行的第一张演唱会专辑。DVD内纪录了2007年11月17日-11月18日于台北小巨蛋举行的两场《一支独SHOW 世界巡回演唱会》的精华片段，影片亦穿插了一些访问片段。《残酷舞台》收录了由罗志祥由Show Time至舞所不在时期，合共五张专辑的歌曲。同时收录了罗志祥与表演嘉宾莫文蔚及杨丞琳合跳的舞蹈表演。而嘉宾萧亚轩以及蔡依林部分和《Twinkle》、《力
法兰索瓦丝·德·奥尔良 (1844年－1925年)奥尔良的法兰索瓦丝（法语：Françoise d'Orléans，1844年8月14日－1925年10月28日），法国国王路易-菲利普一世之子法兰索瓦的女儿，母亲是巴西皇帝佩德罗一世的女儿巴西的法兰西丝卡。1863年，法兰索瓦丝与堂哥罗贝尔·德·奥尔良结婚，两人共有3子2女：