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

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

Более того, ключи — просто 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> Не понял. Класс HashMap или какой-то еще hashmap специально для примитивных типов ?
http://b010.blogspot.com/2009/05/speed-comparison-of-1-javas-built-in.html

Здравствуйте, 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>>В мэп, как известно, можно добавлять ключи с одинаковым хешкодом, мэп ведет у себя списки по хешкоду.

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), исключающий коллизии.

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


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

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

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

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

Здравствуйте, 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);
    }

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

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

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

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);
.>    }
.>

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

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

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

Здравствуйте, 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), а влияет стремление выдавать уникальные значения насколько возможно.