Здравствуйте, Pavel Dvorkin, Вы писали:


PD> Не понял. Класс HashMap или какой-то еще hashmap специально для примитивных типов ?
http://b010.blogspot.com/2009/05/speed-comparison-of-1-javas-built-in.html

21.02.12 11:50, Nicht написав(ла):
> Тоесть ты хочешь сказать, что если я реализую хешфункцию так, что она будет возвращать константу, то это никак не скажется на производительности?
> Приведенная магия чисел меня спасет?

С этим, кстати, связана интересная уязвимость. Легко сгенерировать тысячи коротких строк, имеющих одинаковый хеш (по используемой в данном языке формуле). На сервер отправляется небольшой (десятки килобайт) запрос, содержащий эти строки в качестве имён параметров, сервер приложений/фреймворк разбирает его, складывая параметры в хештаблицу и благодаря O(N^2) загрузает на несколько минут. Очень малым трафиком организуется DOS.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>В мэп, как известно, можно добавлять ключи с одинаковым хешкодом, мэп ведет у себя списки по хешкоду.

PD>А если известно, что ключи гарантированно уникальные ? Понятно, что мэп применять можно, но это означает накладные расходы, которые здесь не нужны.

PD>Более того, ключи — просто Long (а реально, я думаю, будет не больше Integer.MAX_VALUE, но это я только так думаю, ручаться на 100% нельзя).

PD>Кроме того, hashmap ведет список ключей по bucket, так что получается, что bucket будет содержать ровно один элемент, так (если hashCode == key) ? Опять же избыточные накладные расходы.

PD>Вопрос : есть ли более простая структура, в которую можно помещать пары key-value при том, что гарантируется уникальность ключей.

PD>Вариант с использование ключа в качестве индекса в массиве не годится : оценить максимальную величину ключа не представляется возможным.

Вы можете воспользоваться IdentityHashMap.
1. Не хранит хэш.
2. Использует операцию "==" на сравнение по ключам.
3. Использует алгоритм linear probing, что в ваших условиях должен принести выгоды по перфорансу.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Не понял. Класс HashMap или какой-то еще hashmap специально для примитивных типов ?

Можно fastutil посмотреть на эту тему
http://fastutil.dsi.unimi.it/

Здравствуйте, Pavel Dvorkin, Вы писали:


PD>Кроме того, hashmap ведет список ключей по bucket, так что получается, что bucket будет содержать ровно один элемент, так (если hashCode == key) ? Опять же избыточные накладные расходы.

Вроде как это не так.
Индекс в таблице вычисляется так:

static int indexFor(int h, int length) {
    return h & (length-1);
}

Так что каждый bucket разделяется между разными хешкодами и зависит от текущего размера таблицы.
Строго говоря на производительность HashMap влияет только распределения твоего hashcode, а не то что он уникальный или не уникальный.

21.02.12 12:40, Nicht написав(ла):
> Здравствуйте, gegMOPO4, Вы писали:
> MOP>21.02.12 12:18, Nicht написав(ла):
>>> Здравствуйте, gegMOPO4, Вы писали:
>>> MOP>С этим, кстати, связана интересная уязвимость. Легко сгенерировать тысячи коротких строк, имеющих одинаковый хеш (по используемой в данном языке формуле). На сервер отправляется небольшой (десятки килобайт) запрос, содержащий эти строки в качестве имён параметров, сервер приложений/фреймворк разбирает его, складывая параметры в хештаблицу и благодаря O(N^2) загрузает на несколько минут. Очень малым трафиком организуется DOS.
>>> Не понятно где там O(N^2), вроде в вырожденом случае хештейбл — это линкед лист и там поиск это O(N). Но в принципе, мысль интересная.
> MOP>O(N) — для добавления N-го параметра. В сумме будет O(N^2).
> Добавляется там за O(1). Добавление происходит в голову списка.
> Единственное, что при большом количестве элементов, там несколько раз будет происходить ресайз таблицы, где происходит поэлеметное копирование. Но это все равно O(N)и он самортизирован на количество добавлений.

Добавление включает поиск.

В мэп, как известно, можно добавлять ключи с одинаковым хешкодом, мэп ведет у себя списки по хешкоду.

А если известно, что ключи гарантированно уникальные ? Понятно, что мэп применять можно, но это означает накладные расходы, которые здесь не нужны.

Более того, ключи — просто Long (а реально, я думаю, будет не больше Integer.MAX_VALUE, но это я только так думаю, ручаться на 100% нельзя).

Кроме того, hashmap ведет список ключей по bucket, так что получается, что bucket будет содержать ровно один элемент, так (если hashCode == key) ? Опять же избыточные накладные расходы.

Вопрос : есть ли более простая структура, в которую можно помещать пары key-value при том, что гарантируется уникальность ключей.

Вариант с использование ключа в качестве индекса в массиве не годится : оценить максимальную величину ключа не представляется возможным.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD> В мэп, как известно, можно добавлять ключи с одинаковым хешкодом, мэп ведет у себя списки по хешкоду.

PD> А если известно, что ключи гарантированно уникальные ? Понятно, что мэп применять можно, но это означает накладные расходы, которые здесь не нужны.
Вряд ли. У тебя хешкод может быть MIN_INT..MAX_INT, т.е. 4 миллиарда значений. Хешмап держит массив небольшой величины, значит хешкод в число 0..длина_массива. И реаллоцирует массив при слишком большом количестве коллизий. Если ты сможешь свой код как-то вычислительно легко преобразовать в число 0..небольшое_число, то да, можешь выделить массив такой длины и искать просто по индексу. Есть такой ли способ? Зависит от твоих данных.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>А если известно, что ключи гарантированно уникальные ? Понятно, что мэп применять можно, но это означает накладные расходы, которые здесь не нужны.
Это вы про остаток от деления?

PD>Кроме того, hashmap ведет список ключей по bucket, так что получается, что bucket будет содержать ровно один элемент, так (если hashCode == key) ? Опять же избыточные накладные расходы.
Это про ссылку на null & hash которые хранятся в Entry?

PD>Вопрос : есть ли более простая структура, в которую можно помещать пары key-value при том, что гарантируется уникальность ключей.
мне кажется — нет.
Возмите hashmap, который работает с примитивными типами, там расходов по памяти будет прилично меньше.

Здравствуйте, StanislavK, Вы писали:

SK>Возмите hashmap, который работает с примитивными типами, там расходов по памяти будет прилично меньше.

Не понял. Класс HashMap или какой-то еще hashmap специально для примитивных типов ?

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Вопрос : есть ли более простая структура, в которую можно помещать пары key-value при том, что гарантируется уникальность ключей.
1) Дерево
2) Если ключи известны заранее, то можно построить идеальный хэш — http://en.wikipedia.org/wiki/Perfect_hash_function

Здравствуйте, Cyberax, Вы писали:

PD>>Вопрос : есть ли более простая структура, в которую можно помещать пары key-value при том, что гарантируется уникальность ключей.
C>1) Дерево

Там все же log, хеш-таблица лучше

C>2) Если ключи известны заранее, то можно построить идеальный хэш — http://en.wikipedia.org/wiki/Perfect_hash_function

Увы, неизвестны, и более того, точно известно, что их набор будет меняться по времени. Ключ — просто ID из таблицы БД.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>В мэп, как известно, можно добавлять ключи с одинаковым хешкодом, мэп ведет у себя списки по хешкоду.

PD>>А если известно, что ключи гарантированно уникальные ? Понятно, что мэп применять можно, но это означает накладные расходы, которые здесь не нужны.

PD>>Более того, ключи — просто Long (а реально, я думаю, будет не больше Integer.MAX_VALUE, но это я только так думаю, ручаться на 100% нельзя).

PD>>Кроме того, hashmap ведет список ключей по bucket, так что получается, что bucket будет содержать ровно один элемент, так (если hashCode == key) ? Опять же избыточные накладные расходы.

PD>>Вопрос : есть ли более простая структура, в которую можно помещать пары key-value при том, что гарантируется уникальность ключей.

PD>>Вариант с использование ключа в качестве индекса в массиве не годится : оценить максимальную величину ключа не представляется возможным.

А>Вы можете воспользоваться IdentityHashMap.
А>1. Не хранит хэш.
А>2. Использует операцию "==" на сравнение по ключам.
А>3. Использует алгоритм linear probing, что в ваших условиях должен принести выгоды по перфорансу.


Ссори, поторопился с ответом.


Зная, что Long — immutable, думал что:
Long l1 = Long.valueOf( 55555 );
Long l2 = Long.valueOf( 55555 );
System.out.println( l1 == l2 );
Всегда вернет true (по аналогии с Boolean). Это не так.

18.02.12 16:57, Pavel Dvorkin написав(ла):
> В мэп, как известно, можно добавлять ключи с одинаковым хешкодом, мэп ведет у себя списки по хешкоду.
>
> А если известно, что ключи гарантированно уникальные ? Понятно, что мэп применять можно, но это означает накладные расходы, которые здесь не нужны.

Связный список — не единственная возможная реализация хештаблицы.

> Более того, ключи — просто Long (а реально, я думаю, будет не больше Integer.MAX_VALUE, но это я только так думаю, ручаться на 100% нельзя).
>
> Кроме того, hashmap ведет список ключей по bucket, так что получается, что bucket будет содержать ровно один элемент, так (если hashCode == key) ? Опять же избыточные накладные расходы.

Нет. В среднем — количество_элементов/количество_bucket-ов. Для отдельных bucket-ов коллизии могут быть (и практически наверняка будут) и при среднем меньше 1. Это, кстати, источник уязвимости, на который недавно обратили внимание и стали бороться (в Perl, Ruby, PHP, Python и, кажется, Java7).

> Вопрос : есть ли более простая структура, в которую можно помещать пары key-value при том, что гарантируется уникальность ключей.

Да, есть. Для целых ключей — линейный массив.

> Вариант с использование ключа в качестве индекса в массиве не годится : оценить максимальную величину ключа не представляется возможным.

Это единственный вариант с O(1), исключающий коллизии.

Здравствуйте, gegMOPO4, Вы писали:

MOP>Да, есть. Для целых ключей — линейный массив.
>> Вариант с использование ключа в качестве индекса в массиве не годится : оценить максимальную величину ключа не представляется возможным.

MOP>Это единственный вариант с O(1), исключающий коллизии.

См. выделенное.

Здравствуйте, Nicht, Вы писали:

N> Строго говоря на производительность HashMap влияет только распределения твоего hashcode, а не то что он уникальный или не уникальный.
Не влияет. Возвращённое функцией hashCode() число уродуется вот этой функцией

    /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

20.02.12 11:28, Pavel Dvorkin написав(ла):
> Здравствуйте, gegMOPO4, Вы писали:
> MOP>Да, есть. Для целых ключей — линейный массив.
>>> Вариант с использование ключа в качестве индекса в массиве не годится : оценить максимальную величину ключа не представляется возможным.
> MOP>Это единственный вариант с O(1), исключающий коллизии.
> См. выделенное.

Как максимум это Long.MAX_VALUE. А массив может расти по мере надобности.

Если множество ключей сгруппировано кластерами, с большими промежутками между ними, можно использовать многоуровневый массив — эдакое дерево фиксированной небольшой высоты (тоже O(1)). Но без этого дополнительного предположения — только линейный массив.

Здравствуйте, ., Вы писали:

.>Здравствуйте, Nicht, Вы писали:

N>> Строго говоря на производительность HashMap влияет только распределения твоего hashcode, а не то что он уникальный или не уникальный.
.>Не влияет. Возвращённое функцией hashCode() число уродуется вот этой функцией
.>

.>    /**
.>     * Applies a supplemental hash function to a given hashCode, which
.>     * defends against poor quality hash functions.  This is critical
.>     * because HashMap uses power-of-two length hash tables, that
.>     * otherwise encounter collisions for hashCodes that do not differ
.>     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
.>     */
.>    static int hash(int h) {
.>        // This function ensures that hashCodes that differ only by
.>        // constant multiples at each bit position have a bounded
.>        // number of collisions (approximately 8 at default load factor).
.>        h ^= (h >>> 20) ^ (h >>> 12);
.>        return h ^ (h >>> 7) ^ (h >>> 4);
.>    }
.>

Тоесть ты хочешь сказать, что если я реализую хешфункцию так, что она будет возвращать константу, то это никак не скажется на производительности?
Приведенная магия чисел меня спасет?

Здравствуйте, gegMOPO4, Вы писали:

MOP>21.02.12 11:50, Nicht написав(ла):
>> Тоесть ты хочешь сказать, что если я реализую хешфункцию так, что она будет возвращать константу, то это никак не скажется на производительности?
>> Приведенная магия чисел меня спасет?

MOP>С этим, кстати, связана интересная уязвимость. Легко сгенерировать тысячи коротких строк, имеющих одинаковый хеш (по используемой в данном языке формуле). На сервер отправляется небольшой (десятки килобайт) запрос, содержащий эти строки в качестве имён параметров, сервер приложений/фреймворк разбирает его, складывая параметры в хештаблицу и благодаря O(N^2) загрузает на несколько минут. Очень малым трафиком организуется DOS.

Не понятно где там O(N^2), вроде в вырожденом случае хештейбл — это линкед лист и там поиск это O(N). Но в принципе, мысль интересная.

21.02.12 12:18, Nicht написав(ла):
> Здравствуйте, gegMOPO4, Вы писали:
> MOP>С этим, кстати, связана интересная уязвимость. Легко сгенерировать тысячи коротких строк, имеющих одинаковый хеш (по используемой в данном языке формуле). На сервер отправляется небольшой (десятки килобайт) запрос, содержащий эти строки в качестве имён параметров, сервер приложений/фреймворк разбирает его, складывая параметры в хештаблицу и благодаря O(N^2) загрузает на несколько минут. Очень малым трафиком организуется DOS.
> Не понятно где там O(N^2), вроде в вырожденом случае хештейбл — это линкед лист и там поиск это O(N). Но в принципе, мысль интересная.

O(N) — для добавления N-го параметра. В сумме будет O(N^2).

Здравствуйте, Nicht, Вы писали:

N>>> Строго говоря на производительность HashMap влияет только распределения твоего hashcode, а не то что он уникальный или не уникальный.
.>>Не влияет. Возвращённое функцией hashCode() число уродуется вот этой функцией
N>Тоесть ты хочешь сказать, что если я реализую хешфункцию так, что она будет возвращать константу, то это никак не скажется на производительности?
N>Приведенная магия чисел меня спасет?
Может я не правильно понял что ты имеешь в виду, но распределение хешкода не влияет (т.е. значения могут быть все сосредоточены в небольшом интервале, а не по всем возможным значениям int), а влияет стремление выдавать уникальные значения насколько возможно.

Здравствуйте, gegMOPO4, Вы писали:

MOP>21.02.12 12:18, Nicht написав(ла):
>> Здравствуйте, gegMOPO4, Вы писали:
>> MOP>С этим, кстати, связана интересная уязвимость. Легко сгенерировать тысячи коротких строк, имеющих одинаковый хеш (по используемой в данном языке формуле). На сервер отправляется небольшой (десятки килобайт) запрос, содержащий эти строки в качестве имён параметров, сервер приложений/фреймворк разбирает его, складывая параметры в хештаблицу и благодаря O(N^2) загрузает на несколько минут. Очень малым трафиком организуется DOS.
>> Не понятно где там O(N^2), вроде в вырожденом случае хештейбл — это линкед лист и там поиск это O(N). Но в принципе, мысль интересная.

MOP>O(N) — для добавления N-го параметра. В сумме будет O(N^2).

Добавляется там за O(1). Добавление происходит в голову списка.
Единственное, что при большом количестве элементов, там несколько раз будет происходить ресайз таблицы, где происходит поэлеметное копирование. Но это все равно O(N)и он самортизирован на количество добавлений.

Здравствуйте, Nicht, Вы писали:

N>Но в принципе, мысль интересная.
Это не просто интересная мысль, а реальная уязвимость в PHP и Tomcat. Сравнительно недавно только исправили.
Tomcat по-умолчанию принимает POST запросы размером до 2Мб и, напрямую, парсит POST параметры в HashMap.
Если параметры набить ключами с совпадающими String.hashCode(), то специально сформированый запрос в 2Мб укладывает одно ядро Core i5 на 40 минут!
Никакой распределенной атаки не нужно. С одного узла можно завалить таким образом почти любой сервер.

Здравствуйте, gegMOPO4, Вы писали:

MOP>21.02.12 12:40, Nicht написав(ла):
>> Здравствуйте, gegMOPO4, Вы писали:
>> MOP>21.02.12 12:18, Nicht написав(ла):
>>>> Здравствуйте, gegMOPO4, Вы писали:
>>>> MOP>С этим, кстати, связана интересная уязвимость. Легко сгенерировать тысячи коротких строк, имеющих одинаковый хеш (по используемой в данном языке формуле). На сервер отправляется небольшой (десятки килобайт) запрос, содержащий эти строки в качестве имён параметров, сервер приложений/фреймворк разбирает его, складывая параметры в хештаблицу и благодаря O(N^2) загрузает на несколько минут. Очень малым трафиком организуется DOS.
>>>> Не понятно где там O(N^2), вроде в вырожденом случае хештейбл — это линкед лист и там поиск это O(N). Но в принципе, мысль интересная.
>> MOP>O(N) — для добавления N-го параметра. В сумме будет O(N^2).
>> Добавляется там за O(1). Добавление происходит в голову списка.
>> Единственное, что при большом количестве элементов, там несколько раз будет происходить ресайз таблицы, где происходит поэлеметное копирование. Но это все равно O(N)и он самортизирован на количество добавлений.

MOP>Добавление включает поиск.

А, туплю. Ты прав. Проверяется существование такого ключа.

Здравствуйте, gegMOPO4, Вы писали:

MOP>Как максимум это Long.MAX_VALUE. А массив может расти по мере надобности.

С переаллокацией и копированием. Мы не в Win API с VirtualAlloc/MEM_RESERVE/MEM_COMMIT

MOP>Если множество ключей сгруппировано кластерами, с большими промежутками между ними, можно использовать многоуровневый массив — эдакое дерево фиксированной небольшой высоты (тоже O(1)). Но без этого дополнительного предположения — только линейный массив.

Ничего не сгруппировано, никаких зависимостей нет.

21.02.12 14:03, Pavel Dvorkin написав(ла):
> Здравствуйте, gegMOPO4, Вы писали:
> MOP>Как максимум это Long.MAX_VALUE. А массив может расти по мере надобности.
> С переаллокацией и копированием. Мы не в Win API с VirtualAlloc/MEM_RESERVE/MEM_COMMIT

Заполнение массива всё равно O(N) (где N — максимальный индекс), а доступ — O(1).

> MOP>Если множество ключей сгруппировано кластерами, с большими промежутками между ними, можно использовать многоуровневый массив — эдакое дерево фиксированной небольшой высоты (тоже O(1)). Но без этого дополнительного предположения — только линейный массив.
> Ничего не сгруппировано, никаких зависимостей нет.

Тогда эта задача имеет пустое множество решений. Но на самом деле зависимости есть, вы упоминали, что скорее всего индексы будут до Integer.MAX_VALUE (и наверняка есть другие предположения). Для реальных данных можно подобрать удовлетворяющее решение, если правильно переформулировать задачу. Сортированный массив, бинарное дерево, дерево фиксированной глубины — что-то при определённых условиях может подойти.

Здравствуйте, gegMOPO4, Вы писали:

>> MOP>Как максимум это Long.MAX_VALUE. А массив может расти по мере надобности.
>> С переаллокацией и копированием. Мы не в Win API с VirtualAlloc/MEM_RESERVE/MEM_COMMIT

MOP>Заполнение массива всё равно O(N) (где N — максимальный индекс), а доступ — O(1).

Хэш нет, там O(N) никогда не будет. А задерки не нужны.

>> MOP>Если множество ключей сгруппировано кластерами, с большими промежутками между ними, можно использовать многоуровневый массив — эдакое дерево фиксированной небольшой высоты (тоже O(1)). Но без этого дополнительного предположения — только линейный массив.
>> Ничего не сгруппировано, никаких зависимостей нет.

MOP>Тогда эта задача имеет пустое множество решений. Но на самом деле зависимости есть, вы упоминали, что скорее всего индексы будут до Integer.MAX_VALUE (и наверняка есть другие предположения). Для реальных данных можно подобрать удовлетворяющее решение, если правильно переформулировать задачу. Сортированный массив, бинарное дерево, дерево фиксированной глубины — что-то при определённых условиях может подойти.

Собственно, говоря, против мэпа (хешмэпа) я ничего против не имею. Вопрос был просто о том, нельзя ли его ускорить, сыграв на уникальности ключей.

В общем виде (есть произвольное множество хотя бы int, не говоря уж о long, надо O(1) на все операции) — конечно, не имеет решения ). Но я такого решения и не просил

И все же VirtualAlloc/MEM_RESERVE, с ее помощью можно на int (в x64) решение получить . Мне там 4GB адресного пространства не жалко, а реальной памяти понадобится максимум 4К * nKeys.

22.02.12 14:58, Pavel Dvorkin написав(ла):
> Здравствуйте, gegMOPO4, Вы писали:
>>> MOP>Как максимум это Long.MAX_VALUE. А массив может расти по мере надобности.
>>> С переаллокацией и копированием. Мы не в Win API с VirtualAlloc/MEM_RESERVE/MEM_COMMIT
> MOP>Заполнение массива всё равно O(N) (где N — максимальный индекс), а доступ — O(1).
> Хэш нет, там O(N) никогда не будет. А задерки не нужны.

Вообще-то, для заполнения коллекции N независимыми элементами всегда нужно по крайней мере O(N) времени (нужно добавить каждый элемент).

> Собственно, говоря, против мэпа (хешмэпа) я ничего против не имею. Вопрос был просто о том, нельзя ли его ускорить, сыграв на уникальности ключей.

Можно. Зависит от сценария использования. Если ключи гарантированно уникальны, то можно при добавлении не искать ключ в списке, а сразу добавлять в него. Возможно, выгоднее будет в bucket-е непрерывный массив, а не список (это нужно тестировать). Если коллекция сперва заполняется, а потом много используется без вставки/удаления (или очень редкими), то массивы в bucket-ах стоит отсортировать после заполнения и потом использовать бинарный поиск. И, разумеется, выгода будет от использования long вместо Long и тем более Object, — и по памяти, и по доступу, и по о�
�ерациям хеша и сравнения.

> В общем виде (есть произвольное множество хотя бы int, не говоря уж о long, надо O(1) на все операции) — конечно, не имеет решения ). Но я такого решения и не просил

Ну, ваши требования поначалу были довольно категоричны.

> И все же VirtualAlloc/MEM_RESERVE, с ее помощью можно на int (в x64) решение получить . Мне там 4GB адресного пространства не жалко, а реальной памяти понадобится максимум 4К * nKeys.

Кхм, если я правильно понимаю, о чём вы, то это то, что я упоминал с самого начала — дерево фиксированной высоты (2, 3 или 4, не помню, как в современных процессорах). То же можно реализовать и на Java — разрезать индекс на биты (по 16, например, или по 10) и использовать во вложенных массивах. Исходя из особенностей задачи практичнее для индексов меньше M1 хранить значения прямо в массиве, меньше M2 — в подмассивах (дерево высоты 2), меньше M3 — в подподмассивах (высоты 3) и т.д. Тогда для большинства ключей вложенность будет небольшой, быстрее доступ.

Разумеется, в худшем случае (каждое число на отдельной странице) виртуальное пространство очень быстро станет физическим. Поэтому на совести предоставившего информацию о природе данных.

Здравствуйте, Blazkowicz, Вы писали:

B>Здравствуйте, Nicht, Вы писали:

N>>Но в принципе, мысль интересная.
B>Это не просто интересная мысль, а реальная уязвимость в PHP и Tomcat.

а где томкат там и Glassfish — тоже надо обновиться (на 3.1.2)

Здравствуйте, GarryIV, Вы писали:

B>>Это не просто интересная мысль, а реальная уязвимость в PHP и Tomcat.
GIV>а где томкат там и Glassfish — тоже надо обновиться (на 3.1.2)
У исследователей в документе длинный список был, там и RoR и груви и пр. Просто публичных сайтов на GlassFish не так много, как на Tomcat.

Здравствуйте, gegMOPO4, Вы писали:

>> Хэш нет, там O(N) никогда не будет. А задерки не нужны.

MOP>Вообще-то, для заполнения коллекции N независимыми элементами всегда нужно по крайней мере O(N) времени (нужно добавить каждый элемент).

Да, только заполнение идет по времени очень неторопливо, так что на одно заполнение там O(почти 1), а на все — несущественно. А вот переаллокация пройзойдет однажды, и не быстро, и именно при одном добавлении.

>> В общем виде (есть произвольное множество хотя бы int, не говоря уж о long, надо O(1) на все операции) — конечно, не имеет решения ). Но я такого решения и не просил

MOP>Ну, ваши требования поначалу были довольно категоричны.

Почему ? См. исходное письмо. Я там никого не просил дать O(1).

>> И все же VirtualAlloc/MEM_RESERVE, с ее помощью можно на int (в x64) решение получить . Мне там 4GB адресного пространства не жалко, а реальной памяти понадобится максимум 4К * nKeys.

MOP>Кхм, если я правильно понимаю, о чём вы, то это то, что я упоминал с самого начала — дерево фиксированной высоты (2, 3 или 4, не помню, как в современных процессорах). То же можно реализовать и на Java — разрезать индекс на биты (по 16, например, или по 10) и использовать во вложенных массивах. Исходя из особенностей задачи практичнее для индексов меньше M1 хранить значения прямо в массиве, меньше M2 — в подмассивах (дерево высоты 2), меньше M3 — в подподмассивах (высоты 3) и т.д. Тогда для большинства ключей вложенность будет небольшой, быстрее доступ.

Да, с одной разницей — это придется сделать, а в Win API это уже сделано.

MOP>Разумеется, в худшем случае (каждое число на отдельной странице) виртуальное пространство очень быстро станет физическим. Поэтому на совести предоставившего информацию о природе данных.

Конечно. На этом-то и вся игра : значения ключей произвольные от 0 до maxint, а самих их мало.