eXeLab
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС ВЗЛОМ
выпущен 1 марта!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

Русский / Russian English / Английский

Сейчас на форуме: CSRMO (+5 невидимых)
 · Начало · Статистика · Регистрация · Поиск · ПРАВИЛА ФОРУМА · Язык · RSS · SVN ·

 eXeL@B —› Программирование —› Сверх быстрая хештаблица.
Посл.ответ Сообщение


Ранг: 218.9 (наставник)
Статус: Участник
dotnet

Создано: 4 мая 2015 00:06 · Поправил: Nimnul New!
Цитата · Личное сообщение · #1

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


Ранг: 1002.1 (!!!!)
Статус: Участник

Создано: 4 мая 2015 01:23 New!
Цитата · Личное сообщение · #2


Ранг: 218.9 (наставник)
Статус: Участник
dotnet

Создано: 4 мая 2015 02:53 New!
Цитата · Личное сообщение · #3

reversecode

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


Ранг: 1002.1 (!!!!)
Статус: Участник

Создано: 4 мая 2015 02:58 New!
Цитата · Личное сообщение · #4

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


Ранг: 218.9 (наставник)
Статус: Участник
dotnet

Создано: 4 мая 2015 04:04 · Поправил: Nimnul New!
Цитата · Личное сообщение · #5

reversecode

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


Ранг: 307.7 (мудрец)
Статус: Участник

Создано: 4 мая 2015 05:24 · Поправил: mysterio New!
Цитата · Личное сообщение · #6

Ранг: 370.2 (мудрец)
Статус: Участник

Создано: 4 мая 2015 05:36 New!
Цитата · Личное сообщение · #7

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

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

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


Ранг: 3.0 (гость)
Статус: Участник

Создано: 4 мая 2015 07:30 New!
Цитата · Личное сообщение · #8

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


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

O(1) даст распределенная сортировка
 eXeL@B —› Программирование —› Сверх быстрая хештаблица.

Оригинальный DVD-ROM: eXeL@B DVD !

Вы находитесь на форуме сайта EXELAB.RU
Проект ReactOS