функция id не является хеш-функцией.

?

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

отличная хэш функция

идеальная

Потому что Card(Im(id)) = +inf

идеально равномерная

андрей, вот смотри, я беру элемент из массива

А хеш-функция по определению card(Im(hash)) = M , где M\in N

само значение элемента и будет хэш функцией

потом что я с этим делаю?

Повторюсь в третий раз.

А хеш-функция по определению card(Im(hash)) = M , где M\in N

Это определение возникло из-за того, что память не бесконечно. Но у нас совершенно другие условия.

Это не хеш-функция.

Нет, это определение вообще никак не затрагивает память.

Ок. У нас новая структура данных - суперхештаблица, где ключом является суперхешфункция.

потом я беру остаток от деления этого числа на длину массива

и это будет мой индекс, в массиве

массиве списков

Ок. У нас новая структура данных - суперхештаблица, где ключом является суперхешфункция.

тогда оно работает за логарифм.

тогда оно работает за логарифм.

Почему?

Потому что операция обращения к ячейке бесконечной длины это количество бит в числе, то есть его логарифм -__-

Либо ты сейчас мне хочешь рассказать про вычисления даже не на машине Тьюринга.

потом я беру остаток от деления этого числа на длину массива

Да, окей. Длина массива 100

числа в массиве

100 200 300 400 500 ....

Потому что операция обращения к ячейке бесконечной длины это количество бит в числе, то есть его логарифм -__-

Вот над этим не задумывался. А почему так?

Все будут давать одно и то же число в хеше.

массиве списков

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

Вот над этим не задумывался. А почему так?

Ну потому что весь Computer Science живёт в такой модели вычислений-__-

Плоская память, все дела.

Надо ж понимать откуда все эти асимптотики берутся. Что в основе лежит.

Ну потому что весь Computer Science живёт в такой модели вычислений-__-

А, ты имел ввиду то, что на прочтение числа тратится логарифм?

Да хотя бы на чтение, да.

Там же не сказано, что это uint32_t числа, правильно?

Да хотя бы на чтение, да.

А почему на переход логарифм?

Ну потому что переход состоит из чтения.

Потом выставления нужных битов на мультиплексоре.

Все будут давать одно и то же число в хеше.

ну и что, мы речь вели о сложности вставки в хэш, откуда она линейная тут?

Оттуда, что у тебя все числа имеют одинаковый хеш.

это значит они пойдут в одинаковый список

но сложность вставки будет константа

это значит они пойдут в одинаковый список

И ты возвращаешься к исходной задаче)

Нет.

У тебя надо пройтись в конец этого списка.

У тебя надо пройтись в конец этого списка.

Храни конец, в чём проблема?

Господи, тогда поиск в списке будет линеен.

да, но мы говорили про сложность вставки, а она константа

Господи, тогда поиск в списке будет линеен.

Я знаю. Выше об этом я и написал.

я же говорил что тут дело в разрешении коллизий

Нет, просто ты опиши подробно алгоритм вставки.

если бы я разрешал коллизии поиском свободного места в соседнем элементе

то тогда действительно сложность вставки была бы линейная

Нет, просто ты опиши подробно алгоритм вставки.

В каждой ячейке таблицы храним структуру из 2 элементов - указатель на голову списка и указатель на конец списка.

А после идёт линейная вставка.

В случае со списком вставка линейная, потмоу что тебе надо пройтись по списку.

у меня массив списков

В случае со списком вставка линейная, потмоу что тебе надо пройтись по списку.

Зачем проходить, если можно хранить указатель на конец списка?

std::vector<std::list<int»

Для того чтобы не вставлять элемент повторно.

тут не надо проходить по списку

Потому что в хеш-таблице хранится только одна копия. Опять же по определению.

речь не идёт об исходной задаче

Для того чтобы не вставлять элемент повторно.

Вот в этом случае соглашусь.

речь идёт о вставке в хэш

Ладно, этот спор уже смысла не имеет. Решение - сортировка каким-нибудь устойчивым алгоритмом и линейный проход.

Ладно, этот спор уже смысла не имеет. Решение - сортировка каким-нибудь устойчивым алгоритмом и линейный проход.

не обязательно усточивым.

Просто nlogn-ым

ERROR: S client not available

сортировка heapsort

Хотя опять же не всё так просто.

Ну да, фигню написал.

Если там числа нефиксирвоанной длины, то операция сравнения занимает уже не константу.

там инт)

А хотя нет, константу, если аккуратно вероятности посчитать.

Если там числа нефиксирвоанной длины, то операция сравнения занимает уже не константу.

К сожалению нам придётся ограничить как-то эти числа сверху.

В задаче ограничений не было.

Ты сам хотел бесконечную память и бесконечные числа.

не надо усложнять

там инт)

Алдар, в этом случае там вообще всегда константа.

На все алгоритмы.

ты начал про вставку

Потому что ограничееное число значений и вообще число состояний ограниченное.

Вставка.

Давай.

я поэтому ответил

Какая хеш-функция.

и начал дискутировать)

Ну, если так, то сравнение чисел идёт за log(lenbin(n))

Алдар.

Быстрее врятли можно.

Нет. Просто за log(n)

да, потому что их надо хотя бы прочитать

log(n) это и есть число бит.

числа надо прочитать

Нет. Просто за log(n)

Как?

это уже O(n)

Просто побитово.

Алдар, допустим у тебя ограниченные числа.

Твой алгоритм всё равно работает за квадрат.