隨機預言機
在密碼學中，隨機預言機（）是一部預言機，對任何輸入都回傳一個均勻且隨機的輸出（請參考離散型均勻分佈），不過對相同的輸入，該預言機每次都會用同一方法輸出。換句話說，隨機預言機是一個將所有可能輸入與輸出作隨機反映的函數。 限制 只能產生有限個輸出的函數均不是一個隨機預言函數，因為隨機預言機的定義要求其是一個有無限個輸出的函數。 一些刻意設計的簽名和加密方式被證明如果使用隨機預言機的話是安全的，但是使用其他的函式替代隨機預言的話則明顯不安全。…
标签：#散列
共 11 篇文章
分散式雜湊表
分散式雜湊表（，缩写*'）是一類分散式計算系統，用於將關鍵值（key）集合分散到系統中的各個節點，並有效地把查詢訊息轉送至持有相應關鍵值的節點（peer）。此處的節點類似雜湊表中的儲存位置。分散式雜湊表通常面向節點數量極大、且節點經常加入或離開（如網路斷線）的系統設計。在結構化覆盖网络（overlay network）中，參與節點只需與系統中的一小部分節點溝通，也常使用分散式雜湊表。分散式雜湊表可用於建立更複雜的服務，例如分散式檔案系統…
完美散列
对集合S的完美散列函数是一个将S的每个元素映射到一系列无冲突的整数的哈希函数。一个完美散列函数的应用与其他哈希函数的应用基本一致，但不需要任何冲突解决方案。在数学术语中，这是一个完全单射函数. 特性及使用 对于特定集合S的完美散列函数能在常数时间中被计算出，其映射值在一个相对小的范围内，能被一个随机化算法发现，该算法的操作次数与S的大小成正比.任何适合在哈希表中使用的完美散列函数需要至少与S的大小成正比的位数。 一个值的位数被限定范围的…
布隆过滤器
布隆过滤器（）是1970年由伯頓·霍華德·布隆（Burton Howard Bloom）提出的高空间效率的概率数据结构。由一个通过一系列散列函数对样本元素映射而成的二进制位数组组成。布隆过滤器可用于检索一个元素是否在一个集合中，其空间效率和查询时间效率都远超一般算法。它不会产生假阴性（漏报），但有一定的假阳性（误报）率且难以删除元素。 基本概念 如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定…
一致哈希
一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对K/n 个关键字重新映射，其中 K是关键字的数量，n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。 历史 一致哈希由MIT的Karger及其合作者提出，现在这一思想已经扩展到其它领域。在这篇1997年发表的学术论文中介绍了“一致哈希”如何应用于用户易变的分布式Web服务中。哈希表中的每一个代表分布式系统中…
散列函數
散列函数（）又称-{zh-cn:散列算法、哈希函数; zh-tw:雜湊演算法}-，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据计算成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（又叫哈希值）（，，，或）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。如果在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更…
哈希树
哈希树（；Merkle tree），在密码学及计算机科学中是一种树形数据结构，每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签 。哈希树能够高效、安全地验证大型数据结构的内容，是哈希链的推广形式。 哈希树的概念由瑞夫·墨克于 1979 年申请专利，故亦称墨克树（）。 概述 哈希树中，哈希值的求取通常使用诸如SHA-2的加密哈希函数，但如果只是用于防止非故意的数据破坏，也可以使用不安全的校验和取…
索引映射
索引映射（Index mapping）也稱為直接定址（direct addressing）或平凡散列函數（trivial hash function）是计算机科学中對陣列的應用，利用陣列查表來找到主键所有全集分別對應的值。 此方式適用在主鍵全集不大的情形，因此可以針對每一個可能的主鍵分配記憶體。 其效能是源至在任何陣列中查表的时间复杂度都是常數。 適用的陣列 有許多實例中的資料有效值限制在小範圍內。此時適合使用平凡散列函數，以數值作為查…
线性散列
线性散列是由Witold Litwin（1980）发明并被Paul Larson推广的一种动态散列（dynamic hash）算法。线性散列表的每次扩张仅增加一个槽（slot、bucket）， 频繁的单槽扩张可以非常有效控制的冲突链的长度，从而哈希表扩展的代价摊还在每一次插入操作中。因此非常适合用于交互式应用程序。 算法细节 散列表初始化时，先分配任意的数目的散列槽，并在运行过程中检测以下的值： N：最初分配的散列槽数目。 L：它是一个…
线性探测
线性探测是计算机程序解决散列表冲突时所采取的一种策略。散列表这种数据结构用于保存键值对，并且能通过给出的键来查找表中对应的值。线性探测这种策略是在1954年由Gene Amdahl, ,和 所发明，并且最早于1963年由Donald Knuth对其进行分析。 与和双散列一样，线性探测是一种的策略。在这些策略里，散列表的每个单元都存储一对键值对。当散列函数对一个给定值产生一个键，并且这个键指向散列表中某个已经被另一个键值对所占用的单元时，…
懒惰删除
在计算机科学中，懒惰删除（英文：lazy deletion）指的是从一个散列表（也称哈希表）中删除元素的一种方法。在这个方法中，删除仅仅是指标记一个元素被删除，而不是整个清除它。被删除的位点在插入时被当作空元素，在搜索之时被当作已占据。 示例 // javascript var myarr=["first","2nd","3rd","4th"]; delete myarr[2]; // 删除第3个 "3rd" console.info(…