Для одной задачи, мне потребовалась хештаблица, которая должна отдавать элемент строго за O(1), а добавлять элемент можно хоть полгода. Это связанно с тем, что на одно добавление приходится приблизительно 1 << 45 чтений. Вопрос тут упирается в разруливание коллизий. Классические методы для этой задачи не подходят. Т.е. метод со связанными списками, двойным хешированием или методы последовательных проб. Все эти методы, уже делают доступ к элементам больше чем за O(1), даже O(2) уже плохо. Вобщем я решил разруливать коллизии через увеличение несущего массива. Но и тут не обошлось без подводных камней. Моя хеш функция выглядит так: key MOD size. Т.е. индексом массива будет остаток от деления ключа на размер массива. Это классика. С одной стороны дает хорошее распределение, с другой сразу отсекает возможность выхода за границы массива, и эта простота дает фору сложным хешфункциям основанным на битовых операциях с условиями. Проблема заключается в том, что после изменения размера массива, те элементы что уже были добавлены, могут стать коллизионными, т.е. вместо того что бы решать коллизию, создаются новые. Обмозговывая данную ситуацию я пришел к выводу, что новый размер таблицы должен быть числом которое не кратно ни одному ключу из уже добавленных элементов, а во вторых новый размер должен быть примерно вдвое больше текущего. Я подумал, действительно ли мне нужно вычислять этот размер, или может есть другие методики?

-----
have a nice day

| Сообщение посчитали полезным:

--> Link <--

| Сообщение посчитали полезным:

reversecode

>> Среднее время поиска элемента в ней есть O(1), время для наихудшего случая - O(n).

-----
have a nice day

| Сообщение посчитали полезным:

я тебе показал пример как разруливаются коллизии
идеального хеша не существует (с), подбирай его по своим условиям если не хочешь коллизии разруливать списками

| Сообщение посчитали полезным:

reversecode

Тогда может подскажете, как найти некратное число, для массива чисел, которое не больше заданного? И будет лучше если это число будет простым.

-----
have a nice day

| Сообщение посчитали полезным:

оно ? и не оно 2 ?

-----
Don_t hate the cracker - hate the code.

| Сообщение посчитали полезным:

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

Если нет ограничений на время добавления, в бинарном дереве достижима скорость поиска O(log2 n) в любом случае, нужно просто балансировать каждый раз при изменении дерева.

-----
PGP key <0x1B6A24550F33E44A>

| Сообщение посчитали полезным: Coderess

Nimnul пишет:
за O(1), даже O(2) уже плохо

бред, что ты этим хотел сказать?

O(1) даст распределенная сортировка

| Сообщение посчитали полезным: