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

S>·>Не знаю как в шарпе, но в jdk сделали финт ушами — если ключ реализует Comparable (что на практике почти всегда), то включается бинарный поиск, т.е. сложность в худшем случае падает до O(log(n)).
S>В дотнете используют рандомизацию хешей.
S>https://andrewlock.net/why-is-string-gethashcode-different-each-time-i-run-my-program-in-net-core/
S>Кратко: при каждом запуске программы "foo".GetHashCode() будет иметь разные значения.
S>Более того, если у нас в текущем запуске программы у различных строк foo и bar были одинаковые хеши, то при следующем запуске они скорее всего станут разными.
Похоже это для string только. Для всего остального и пользовательских типов работать не будет. Т.е. достаточно иметь в качестве ключа какой-нибудь int или long и упс.

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

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

А разве данные в соотв. bucket'е отсортированы?

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

S>·>Не знаю как в шарпе, но в jdk сделали финт ушами — если ключ реализует Comparable (что на практике почти всегда), то включается бинарный поиск, т.е. сложность в худшем случае падает до O(log(n)).
S>А разве данные в соотв. bucket'е отсортированы?
В java.util.HashMap используется красно-чёрное дерево для элементов одного бакета, если ключ реализует Comparable.

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

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

S>>Тут поспорю. Если исходить из того, что элементы попадают лишь в свой бакет и не могут быть доступны из соседнего — то да, соглашусь. Сейчас же имеем реализацию, где бакет — это лишь вход в общий массив элементов со сквозным перечислением от места входа до последнего элемента в контейнере, а не в бакете.
·>Если я правильно понял, то от места входа до искомого элемента — это и есть по сути бакет. Т.е. до последнего элемента оно ходить и не должно. Хороший хеш должен давать наиболее точное место входа и совсем немного идти до искомого элемента.
Искомый элемент может и отсутствовать, тогда цикл поиска пройдет до последнего по цепочке всех записей, связанных полем next.

                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
                }

https://github.com/microsoft/referencesource/blob/master/mscorlib/system/collections/generic/dictionary.cs#L297

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

S>>>Тут поспорю. Если исходить из того, что элементы попадают лишь в свой бакет и не могут быть доступны из соседнего — то да, соглашусь. Сейчас же имеем реализацию, где бакет — это лишь вход в общий массив элементов со сквозным перечислением от места входа до последнего элемента в контейнере, а не в бакете.
S>·>Если я правильно понял, то от места входа до искомого элемента — это и есть по сути бакет. Т.е. до последнего элемента оно ходить и не должно. Хороший хеш должен давать наиболее точное место входа и совсем немного идти до искомого элемента.
S>Искомый элемент может и отсутствовать, тогда цикл поиска пройдет до последнего по цепочке всех записей, связанных полем next.
S>if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
Выделенное означает проход не "до последнего элемента в контейнере" а до конца бакета.

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

S>>if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
·>Выделенное означает проход не "до последнего элемента в контейнере" а до конца бакета.

Выделенное отвечает лишь за предусловие для вызова Equals. К условию выхода из цикла оно отношения не имеет. Цикл завершится когда нарушится "i >= 0".

S>Искомый элемент может и отсутствовать, тогда цикл поиска пройдет до последнего по цепочке всех записей, связанных полем next.

Да, но этот связный список (цепочка entries.next) не обязательно охватывает все элементы Dictionary.
Там только bucket с данным хэшем и "объединенные" (coalesced) с ним.
См. картинку из статьи в wiki

(null)
"clq"
"qur"
(null)
(null)
"dim"
"aty"     "qsu"
"rhv"
"qrj"     "ofu"     "gcl"     "ecd"
(null)

It is possible for a newly inserted item to collide with items with a different hash address, such as the case in the example in the image when item "clq" is inserted.
The chain for "clq" is said to "coalesce" with the chain of "qrj," hence the name of the algorithm.

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

S>>Искомый элемент может и отсутствовать, тогда цикл поиска пройдет до последнего по цепочке всех записей, связанных полем next.

M>Да, но этот связный список (цепочка entries.next) не обязательно охватывает все элементы Dictionary.
M>Там только bucket с данным хэшем и "объединенные" (coalesced) с ним.

Все верно, вроде так и есть.

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

S>>>if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
S>·>Выделенное означает проход не "до последнего элемента в контейнере" а до конца бакета.
S>Выделенное отвечает лишь за предусловие для вызова Equals. К условию выхода из цикла оно отношения не имеет. Цикл завершится когда нарушится "i >= 0".
Ах, ну да. Я запутался, там как указал m2user просто цепочки не на весь контейнер, а для каждого отдельного бакета своя цепочка. И плюс ещё отдельно цепочка дырок от удалённых элементов.
Но суть ровно та же, как и в любой классической реализации хештаблицы — константно-быстро найти бакет и линейно перебрать все элементы одного бакета, алгоритм O(n) в худшем случае.

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

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

·>Ах, ну да. Я запутался, там как указал m2user просто цепочки не на весь контейнер, а для каждого отдельного бакета своя цепочка. И плюс ещё отдельно цепочка дырок от удалённых элементов.
·>Но суть ровно та же, как и в любой классической реализации хештаблицы — константно-быстро найти бакет и линейно перебрать все элементы одного бакета, алгоритм O(n) в худшем случае.

Я тоже запутался. Меня смутила сквозная пробежка по всему массиву при перечислении, подумал что все живые элементы связаны одной цепью. Хотя, это не следовало из кода пробежки. В общем, при поиске элемента весь контейнер будет задействован лишь при вырождении хэш функции на наборе данных.