| dbo:abstract
|
- Linear probing is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key–value pairs and looking up the value associated with a given key. It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel and first analyzed in 1963 by Donald Knuth. Along with quadratic probing and double hashing, linear probing is a form of open addressing. In these schemes, each cell of a hash table stores a single key–value pair. When the hash function causes a collision by mapping a new key to a cell of the hash table that is already occupied by another key, linear probing searches the table for the closest following free location and inserts the new key there. Lookups are performed in the same way, by searching the table sequentially starting at the position given by the hash function, until finding a cell with a matching key or an empty cell. As write, "Hash tables are the most commonly used nontrivial data structures, and the most popular implementation on standard hardware uses linear probing, which is both fast and simple."Linear probing can provide high performance because of its good locality of reference, but is more sensitive to the quality of its hash function than some other collision resolution schemes. It takes constant expected time per search, insertion, or deletion when implemented using a random hash function, a 5-independent hash function, or tabulation hashing. Good results can also be achieved in practice with other hash functions such as MurmurHash. (en)
- In de informatica is linear probing een manier om collisies ('botsingen') bij het invoegen van een item in hashtabellen te verhelpen. Wanneer het invoegen op de positie die door de hashfunctie berekend is niet mogelijk is (doordat er al een item aanwezig is), wordt deze positie met een standaard stapgrootte (meestal 1) verhoogd totdat een positie gevonden is (zolang de hashtabel niet vol is). De berekende positie wordt modulo m berekend waarbij m de grootte van de hashtabel is. Hierdoor blijft de berekende waarde in het interval [0, m) van gehele getallen en dus binnen de hashtabel: (h(k) + i) mod m, met i = 0,1,2, ... (stapgrootte is hierbij 1) Linear probing heeft als nadeel dat een lege positie naast een lang aaneengesloten stuk een grotere kans heeft om bezet te worden dan een lege positie naast een korter stuk (of naast een lege positie): lange aaneengesloten stukken hebben een grotere kans om nog langer te worden. Hierdoor worden de items in de hashtabel niet zo goed gespreid als gewenst. (nl)
- 线性探测是计算机程序解决散列表冲突时所采取的一种策略。散列表这种数据结构用于保存键值对，并且能通过给出的键来查找表中对应的值。线性探测这种策略是在1954年由Gene Amdahl, ,和 所发明，并且最早于1963年由Donald Knuth对其进行分析。 与和双散列一样，线性探测是一种的策略。在这些策略里，散列表的每个单元都存储一对键值对。当散列函数对一个给定值产生一个键，并且这个键指向散列表中某个已经被另一个键值对所占用的单元时，线性探测用于解决此时产生的冲突：查找散列表中离冲突单元最近的空闲单元，并且把新的键插入这个空闲单元。同样的，查找也同插入如出一辙：从散列函数给出的散列值对应的单元开始查找，直到找到与键对应的值或者是找到空单元。 正如Thorup和張寅在2012年所写，…“散列表是最常用的普通数据结构，它在硬件上的标准实现中最流行的方法就是使用线性探测。线性探测又快又简单。”线性探测能够提供高性能的原因是因为它的良好的引用局部性，然而它与其他解决散列冲突的策略相比对于散列函数的质量更为敏感。当使用随机散列函数， 或，其用于搜索，插入或删除的预期时间是常数。不過，藉由其他像是私語雜湊的散列函數可以在實作中達到較好的結果。 (zh)
- Линейное зондирование — это схема в программировании для разрешения коллизий в хеш-таблицах, структурах данных для управления наборами и поиска значений, ассоциированных с данным ключом. Схему придумали в 1954 Джин Амдал, и Артур Сэмюэл, а проанализировна она была в 1963 Дональдом Кнутом. Вместе с и линейное зондирование является видом . В этих схемах каждая ячейка хеш-таблицы содержит одну пару ключ-значение. Если хеш-функция даёт коллизию, отображая значение нового ключа в ячейку хеш-таблицы, занятую другим ключом, линейное зондирование просматривает таблицу до ближайшей свободной следующей ячейки и вставляет новый ключ туда. Поиск значения осуществляется тем же образом, путём просмотра таблицы последовательно, начиная с позиции, определённой хеш-функцией, пока не найдёт совпадение ключа, либо пустую ячейку. Как писали Торуп и Чжан, «Хеш-таблицы интенсивно используют нетривиальные структуры данных и большинство имплементаций в аппаратуре использует линейное зондирование, быстрое и простое в реализации».Линейное зондирование может дать высокую производительность вследствие хорошей метода, но оно более чувствительно к качеству хеш-функции, чем другие схемы разрешения коллизий. Среднее ожидаемое время поиска у метода является константой, то же самое верно для вставки и удаления, если в имплементации используется случайный выбор хеш-функции, , или . Однако, на практике, хорошие результаты получаются и с другими функциями хеширования, такими как MurmurHash . (ru)
|
| rdfs:comment
|
- 线性探测是计算机程序解决散列表冲突时所采取的一种策略。散列表这种数据结构用于保存键值对，并且能通过给出的键来查找表中对应的值。线性探测这种策略是在1954年由Gene Amdahl, ,和 所发明，并且最早于1963年由Donald Knuth对其进行分析。 与和双散列一样，线性探测是一种的策略。在这些策略里，散列表的每个单元都存储一对键值对。当散列函数对一个给定值产生一个键，并且这个键指向散列表中某个已经被另一个键值对所占用的单元时，线性探测用于解决此时产生的冲突：查找散列表中离冲突单元最近的空闲单元，并且把新的键插入这个空闲单元。同样的，查找也同插入如出一辙：从散列函数给出的散列值对应的单元开始查找，直到找到与键对应的值或者是找到空单元。 正如Thorup和張寅在2012年所写，…“散列表是最常用的普通数据结构，它在硬件上的标准实现中最流行的方法就是使用线性探测。线性探测又快又简单。”线性探测能够提供高性能的原因是因为它的良好的引用局部性，然而它与其他解决散列冲突的策略相比对于散列函数的质量更为敏感。当使用随机散列函数， 或，其用于搜索，插入或删除的预期时间是常数。不過，藉由其他像是私語雜湊的散列函數可以在實作中達到較好的結果。 (zh)
- Linear probing is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key–value pairs and looking up the value associated with a given key. It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel and first analyzed in 1963 by Donald Knuth. (en)
- In de informatica is linear probing een manier om collisies ('botsingen') bij het invoegen van een item in hashtabellen te verhelpen. Wanneer het invoegen op de positie die door de hashfunctie berekend is niet mogelijk is (doordat er al een item aanwezig is), wordt deze positie met een standaard stapgrootte (meestal 1) verhoogd totdat een positie gevonden is (zolang de hashtabel niet vol is). De berekende positie wordt modulo m berekend waarbij m de grootte van de hashtabel is. Hierdoor blijft de berekende waarde in het interval [0, m) van gehele getallen en dus binnen de hashtabel: (nl)
- Линейное зондирование — это схема в программировании для разрешения коллизий в хеш-таблицах, структурах данных для управления наборами и поиска значений, ассоциированных с данным ключом. Схему придумали в 1954 Джин Амдал, и Артур Сэмюэл, а проанализировна она была в 1963 Дональдом Кнутом. (ru)
|