Какой смысл в хеш-таблице?
static IEnumerable<string> Combinations(List<string> characters, int length)
{
for (int i = 0; i < characters.Count; i++)
{
// only want 1 character, just return this one
if (length == 1)
yield return characters[i];
// want more than one character, return this one plus all combinations one shorter
// only use characters after the current one for the rest of the combinations
else
foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
yield return characters[i] + next;
}
}
10 ответов
Это находится недалеко от дубликата: Почему мы используем Hashcode в Hashtable вместо индекса?
Долгое время коротко, вы можете проверить, будет ли ключ уже сохранен очень Быстро и одинаково быстро хранить новое отображение. В противном случае вам придется сохранить отсортированный список клавиш, который намного медленнее хранить и извлекает отображения.
Чего я не понимаю, так это почему значения не хранятся с ключом (строка, число, что угодно) в качестве, ну, в общем, ключа, вместо того, чтобы создавать его хеш и хранить его.
Ну, как вы предлагаете сделать это, с помощью поиска O (1)?
Смысл хеш-таблиц в основном состоит в том, чтобы обеспечить поиск O (1) путем поворота ключ в индекс массива, а затем возвращает содержимое массива по этому индексу. Чтобы сделать это возможным для произвольных ключей, вам нужен
- Способ превратить ключ в индекс массива (такова цель хэша)
- Способ справиться с коллизиями (ключи, которые иметь одинаковый хэш-код)
- Способ регулировки размера массива, когда он слишком мал (вызывает слишком много коллизий) или слишком велик (тратит место)
Основное преимущество использования хэша с целью поиска элементов в таблице, а не использования оригинального ключа пары ключ-значение (который, кстати, обычно хранится и в таблице, поскольку хэш необратим), это ..
... он позволяет отображать все пространство имен [оригинальных] ключей на сравнительно небольшое пространство имен хеш-значений, позволяя хэш-таблице обеспечить производительность O (1) для извлечения элементов.
Эта производительность O (1) становится немного размытой, если учесть дополнительное время для обработки коллизий и тому подобного, но в целом хеш-таблица очень быстрая для хранения и извлечения элементов, в отличие от системной только на значение ключа [original], которое тогда обычно будет O (log N), например, с двоичным деревом (хотя такое дерево более эффективно в пространстве)
Проблема заключается в возвращаемом «строковом» значении. Маршаллер P/Invoke вызовет CoTaskMemFree () по возвращаемому указателю. Это не сработает, если вы не использовали CoTaskMemAlloc () в коде C/C + + для выделения буфера последовательностей. Что довольно необычно.
Лучшее решение - разрешить вызывающему абоненту вашего кода передавать указатель на буфер и длину буфера в качестве аргументов. Таким образом, все распределение памяти происходит с одной стороны. Скотт показал тебе, как это сделать.
-121--2675117-Также рассмотрим скорость. Если ключ является последовательностью, а значения хранятся в массиве, хэш может получить доступ к любому элементу за постоянное время «» near «». Сравните это с поиском последовательности и ее значения.
-121--1742743-Идея хэш-таблицы заключается в предоставлении прямого доступа к ее предметам. Именно поэтому он вычисляет «хеш-код» ключа и использует его для хранения предмета, вместо самого ключа.
Идея состоит в том, чтобы иметь только один хэш-код на ключ. Много раз хеш-функция, которая генерирует хеш-код, делит простое число и использует его остаток в качестве хеш-кода.
Предположим, что в качестве ключа используется таблица с 13 позициями и целым числом, поэтому можно использовать следующую хеш-функцию
f (x) = x% 13
Что я не понимаю, состоит в том, почему значения не хранятся с ключом (строка, номер, что угодно) как то, ну, ключ
и как вы реализуете это?
Компьютеры знают только номера Отказ Таблица HASH - это таблица , то есть массив и когда мы вправе вниз, массив может только , адресованном через неотрицательный индекс. Все остальное это хитрость. Динамические языки, которые позволяют использовать строковые клавиши - они используют хитрость.
И одна такая хитрость, и часто наиболее элегантным, просто вычисляют численное воспроизводимое «хеш» номер ключа и используя это в качестве индекса.
(Есть и другие соображения, такие как уплотнение ключевого диапазона, но это главная проблема.)
В двух словах: хеширование позволяет (1) запросы / вставки / удаления в таблицу. OTOH, сортированная структура (обычно реализована как сбалансированная BST), приносит те же операции O (logn) время.
Зачем взять хэш, вы спрашиваете? Как вы предлагаете хранить ключ «как ключ»? Спросите себя, если вы планируете хранить просто (ключ, значение) пары, как быстро будет ваш поиск / вставки / делеции? Будете ли вы запустить цикл O (N) во всем массиве / списке?
Весь точка наличия хеш-значение заключается в том, что он позволяет преобразовывать все ключи в конечный набор хеш-значений. Это позволяет нам хранить ключи в слотах конечного массива (включение быстрых операций - вместо поиска всего списка вы только ищите только эти клавиши, которые имеют одинаковое хеш-значение), даже если набор возможных ключей может быть чрезвычайно большим или бесконечным (например, Ключи могут быть строки, очень большими числами и т. Д.) С хорошей хэш-функцией, очень немногие клавиши когда-либо будут иметь одинаковые значения хэш, и все операции эффективно оформлены в (1).
Это, вероятно, не имеет особого смысла, если вы не знакомы с HASHING и насколько работают. Лучшее, что нужно сделать в этом случае, состоит в том, чтобы проконсультироваться с соответствующей главой хороших алгоритмов / книги структур данных (я рекомендую CLRS).
Как правило, точка хэш-таблица - хранить некоторое редкое значение - то есть большое пространство ключей и небольшое количество вещей для хранения. Подумайте о струнах. Существует бесчисленное количество возможных строк. Если вы храните имена переменной, используемые в программе, то существует относительно небольшое количество этих возможных строк, которые вы на самом деле используете, даже если вы заранее не знаете, что они.
Hashtable используется для хранения набора значений и их клавиш в (в течение некоторого количества времени) постоянного количества пятен. В простом случае, скажем, вы хотите сохранить каждое целое число от 0 до 10000, используя хеш-функцию I% 10.
Это сделает бы Hastable из 1000 блоков (часто массив), каждый из которых имеет более 10 элементов Отказ Поэтому, если вы должны были искать 1234, он будет немедленно узнать, чтобы искать в таблице-записи на 123, затем начать сравнивать, чтобы найти точное совпадение. Предоставлено, это не намного лучше, чем просто использовать массив из 10000 элементов, но это просто для демонстрации.
Hashtables очень полезны, когда вы точно не знаете, сколько элементов у вас будет, но будет хорошее количество столкновений меньшего количества столкновений на функцию хеша, чем ваше общее количество элементов. (Что делает хеш-функцию «хэш (х) = 0» очень, очень плохо.) У вас могут быть пустые места в вашем столе, но в идеале большинство из них будут иметь некоторые данные.
В некоторых случаях, возможно, что ключ очень длинный или большой, что делает нецелесообразным хранение копий этих ключей. Хранение их сначала позволяет уменьшить использование памяти, а также сократить время поиска.
Также учитывайте скорость. Если ваш ключ - строка, а ваши значения хранятся в массиве, то ваш хэш может получить доступ к любому элементу в 'близком' постоянном времени. Сравните это с поиском строки и ее значения.