|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 11 Aug 2003 18:47:00
To : Alex Mizrahi
Subject : hash table
--------------------------------------------------------------------------------
Mon Aug 11 2003 18:34, Alex Mizrahi wrote to All:
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
AM> 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> как тогда понимать написанное? это конструктивная особенность Lisp'а(типа
AM> hash table ненастоящие), неточность в книге, или как-то всё-таки можно
AM> сделать hash table с константным временем доступа?
Hасколько я помню, хеш-таблицы как раз и делаются для доступа за О(1) в
среднем. Вычисление хэш-функции константное, обращение по вычисленному адресу
тоже. Вот обработка коллизий... Hо если места много, на среднее время коллизии
мало влияют. Вот гарантированное время доступа - константным сделать...
тяжко...
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
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 |
|
|
