Каковы преимущества дизайна хэш-подобного сохранения по сравнению с инкрементным - PullRequest
0 голосов
/ 21 марта 2012

Такие сайты, как jsfiddle и tinyurl, не сохраняются в инкрементном порядке.Есть ли какое-то преимущество в этом?

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

Разве инкрементный не намного эффективнее и интуитивнее?

Ответы [ 3 ]

1 голос
/ 22 марта 2012

Сохранение в инкрементном порядке определенно быстрее. Но если ваш массив в настоящее время содержит 1 миллиард элементов, вы добавили 1 миллиард записей и удалили 950 миллионов записей, возможно, вы захотите повторно использовать пространство, а не увеличивать размер массива еще раз. Сколько бы памяти у вас не было, вы когда-нибудь закончите. С хорошей хеш-таблицей вы можете удобно сохранить тот же объем данных, используя массив из 100 миллионов элементов, размер которого вам никогда не нужно изменять.

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

Я всегда предпочитал "карты" или "словари", основанные на двоичных деревьях. Они медленнее, но более гибкие и не используют огромные массивы; память выделяется и освобождается небольшими, управляемыми битами. Они могут справиться с большими колебаниями в размере / использовании. Вам не нужен надежный генератор хеш-кода. Но если вы знаете свои данные, хеш-таблицы обычно лучше.

1 голос
/ 22 марта 2012

Посторонние не всегда могут отличить хеш от последовательного ключа. Вполне возможно, что приложение могло бы использовать некоторую форму последовательного идентификатора для внутреннего использования, но зашифровывать его, прежде чем подвергать его воздействию внешнего мира. Такие подходы, как правило, не следует полагаться на обеспечение безопасности со стороны злоумышленников, которые могут попытаться «угадать» идентификационные коды (они, по сути, представляют собой «безопасность через неизвестность»), но как минимум они могут отговорить людей от действий, основанных на том факте, что Сайт, кажется, присваивает идентификаторы определенным образом Например, сайт может начинаться с одного сервера, который использует последовательные идентификаторы, но может переключиться на наличие двух серверов, один из которых назначает нечетные числа последовательно, а другой - чётные числа последовательно (оба сервера начинаются где-то после наибольшего числа, которое имело был выделен одним сервером). Если бы последовательные идентификаторы были выставлены внешнему миру, было бы возможно, что какой-то сайт мог бы быть закодирован в предположении, что нумерация идентификаторов будет представлять хронологическую последовательность. Даже что-то простое, например умножение идентификатора на некоторую большую константу (игнорирование переполнения), xor'ing с некоторым значением и умножение на некоторую другую константу, приведет к идентификаторам, которые могут быть легко преобразованы обратно в порядковые номера кем-то, кто знает метод, но который будет препятствовать любым предположениям о заказе.

0 голосов
/ 21 марта 2012

Проверка, существует ли запись, может быть выполнена в постоянное время, если базовая структура является хеш-таблицей, поэтому не медленная вообще.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...