ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Krotov                     2:5020/400     13 Aug 2003  01:02:19
 To : "Alex Mizrahi"
 Subject : Re: hash table
 -------------------------------------------------------------------------------- 
 

 Alex Mizrahi <miz@matfak.dongu.donetsk.ua> wrote:
 
 AM> в книге о Lisp'е написано следующее:
 AM> --
 AM> A hash table is similar to what is known in some other languages as an
 AM> associative array. It
 AM> is comparable to a single-dimensional array which supports keys which are
 AM> any arbitrary CL
 AM> object, which will match using eql, e.g. symbols or integers. Hash tables
 AM> support virtually
 AM> constant-time lookup of data, which means that the time it takes to look up
 AM> an item in a
 AM> hash table will remain stable, even as the number of entries in the hash
 AM> table increases.
 AM> --
 AM> 
 AM> но я всегда думал что доступ к ассоциативным массивам осуществляется за
 AM> логарифмическое время в лучшем случае..
 AM> как тогда понимать написанное? это конструктивная особенность Lisp'а(типа
 AM> hash table ненастоящие), неточность в книге, или как-то всё-таки можно
 
 Математически-строго обеспечить время поиска и вставки O(1) - невозможно.
 Обеспечить время поиска O(1) можно, если удастся найти совершенную
 хеш-функцию (функцию без коллизий).
 
 Hо если не углубляться в тонкости тервера, а смотреть на хеширование
 просто, по-пролетарски, то можно считать и ожидаемое время поиска и
 время вставки константным. Конечно, если хеш-функция удачная.
 
 -ank
 --- ifmail v.2.15dev5
  * Origin: Hо предпочел стать неверующим равином. (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    hash table   Alex Mizrahi   11 Aug 2003 18:34:53   hash table   Evgenij Masherov   11 Aug 2003 18:47:00   Re: hash table   Alexander Krotov   13 Aug 2003 01:02:19   Re: hash table   Nick Ivanych Kovaliov   13 Aug 2003 10:32:02