В сочетании с LeetCode, чтобы рассказать о применении хеш-таблицы в алгоритмических задачах.
от
LeetCodeНекоторые хеш-таблицы обобщаются в первых сотнях вопросов (unordered_map) применительно к алгоритмическим задачам, использование хеш-таблицы в нужный момент может значительно повысить эффективность алгоритма, например: подсчет количества вхождений каждого символа или слова в строку, выбор двух чисел из одномерного массива в сделать то же самое число равно.
Прежде чем начать, сначала кратко ознакомьтесь с хэш-таблицей (также известной как хеш-таблица), нетерпеливые учащиеся могут перейти кРаздел LeetCode.
Введение в хэш-таблицы
Наихудшая временная сложность поиска в хэш-таблице составляет O(n), а средняя временная сложностьO(1), поэтому в идеале хэш-таблицы используются так же, как массивы.
Хеш-таблица использует некоторую алгоритмическую операцию (хеш-функцию) для преобразования ключа в индекс массива для доступа к данным в массиве, к которым можно получить доступ с помощьюKey-valueспособ доступа к данным для достижения эффективности доступа на постоянном уровне. настоящее времяnosqlбаза данных с использованиемkey-valueспособ доступа к сохраненным данным.
Хеш-таблица является классическим примером алгоритма, находящего компромиссы во времени и пространстве. С помощью хеш-функции ключ-значение сопоставляется с адресом доступа к записи для достижения цели быстрого поиска. Если ограничения по памяти нет, мы можем напрямую использовать ключ в качестве индекса массива, и все операции могут быть выполнены только с одним обращением к памяти.
хэш-функция
Хеш-функция — это процесс преобразования ключа в индекс массива.Эта функция должна легко вычисляться и иметь возможность распределять все ключи поровну.
Наиболее часто используемый метод хеш-функции除留余数法, обычно выбираемый делимым素数, чтобы обеспечить равномерное распределение ключевых значений.
Хеш-функция связана с типом ключа, и для каждого типа данных требуется соответствующая хэш-функция; например, тип ключа — целое число, тогда мы можем использовать его напрямую.除留余数法; Когда тип ключа строковый, мы все равно можем использовать除留余数法, вы можете рассматривать строку как особенно большое целое число.
int hash = 0;
for (int i=0;i<s.length();i++){
hash = (R*hash +s.charAt(i)%M);
}
или
Hash hashCode(char *key){
int offset = 5;
Hash hashCode = 0;
while(*key){
hashCode = (hashCode << offset) + *key++;
}
return hashCode;
}
при его использованииhashCode(key) & (size-1)вы можете получитьsize-1диапазон значений хэша
разрешение коллизий
Разные ключевые слова получают один и тот же хеш-адресf(key1)=f(key2), то есть столкновение. Это ситуация, которую мы должны попытаться избежать. Общие методы обработки:
- молния метод
- закон об открытых адресах
молния метод
Каждый элемент в массиве размера M указывает на связанный список, и каждый узел в связанном списке хранит пару ключ-значение, хэш-значение которой является индексом этого элемента. Средняя длина каждого связанного списка — N/M, где N — общее количество пар ключ-значение. Как показано ниже:
Добавить действие:
- Получить hashCode через хэш-функцию
- Получить индекс по хэш-коду
- Если в индексе нет связанного списка, создайте новый узел в качестве первого узла нового связанного списка.
- Если в индексе уже есть связанный список, сначала перейдите, чтобы увидеть, существует ли уже ключ, если да, вернитесь напрямую, если нет, добавьте его в начало связанного списка.
Удалить операцию:
- Получить hashCode через хэш-функцию
- Получить индекс по хэш-коду
- просмотреть связанный список, удалить узел
закон об открытых адресах
Используйте массив размера M для хранения N пар ключ-значение, а при возникновении коллизии напрямую проверяйте следующую позицию в хеш-таблице.
Способ проверки может быть线性检测、平方检测、双哈希и другие методы, основное отличие которых заключается в обнаружении следующей позиции.
Метод двойного хеширования рекомендуется в разделе «Введение в алгоритмы».
// 插入算法
HASH-INSERT(T, k)
i = 0
repeat
j = h(k, i)
if T[j] == NIL
T[j] = k
return j
else
i++
until i == m
error "hash table overflow"
// 搜索算法
HASH-SEARCH(T, k)
i = 0
repeat
j = j(k, i)
if T[j] == k
return j
i++
until T[j] == NIL or i == m
return NIL
Тема хеш-таблицы в LeetCode
Во время моей практики с LeetCode я столкнулся с несколькими сценариями, в которых я мог использовать таблицу для упрощения задачи.
Задача нахождения индекса по значению элемента
дать массивnums = [2, 7, 11, 15], попросите найти два числа так, чтобы их сумма былаtarget = 9.
Эту простую проблему также можно решить быстро, если решить ее с помощью циклического насилия, но временная сложностьO(n^2), если массив очень длинный, порядка миллионов, для завершения цикла потребуется много времени.
Быстрое решение состоит в том, чтобы использовать таблицу для записи индекса каждого значения, а затем зациклить один раз, чтобы определитьtarget-nums[i], набор решений можно быстро найти, когда его нет в таблице.Здесь ключ — это числовое значение, а значение — это индекс, соответствующий числовому значению, что является методом быстрого поиска индекса с использованием числового значения.
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> maps;
int size = nums.size();
for(int i = 0; i < size; ++i)
maps[nums[i]] = i;
for (int i = 0; i < size; ++i) {
int left = target - nums[i];
if(maps.count(left) > 0 && maps[left] != i)
{
return vector<int>({i, maps[left]});
}
}
return vector<int>();
}
Проблема определения количества вхождений элемента
Проблема суждения судоку о законностиа такжезадача на кратчайшую подстроку, содержащую все символыВсе дело в использовании хеш-таблицы для подсчета количества вхождений элемента.
В такой задаче, когда все элементы ограничены, мы также можем использовать массивы.vector<int>вместо хеш-таблицыunordered_map<int,int>、unordered_map<char,int>、Статистика, потому что 1-9 имеют в общей сложности 9 возможностей, а элементы кода ASCII имеют в общей сложности 128 возможностей, что на самом деле является хэш-функциейf(int x){return x;}особые обстоятельства.
проблема судоку
Задача судоку требует, чтобы каждая строка, каждый столбец и вся таблица были разделены на подблоки 9. В каждом подблоке 1-9 могут появляться только один раз и не могут повторяться. Мы можем создать хэш-таблицу для каждой строки и столбца, всего таблиц 27, и добавить элементы в таблицу.Как только элемент в таблице больше 1, можно судить, что судоку не квалифицирован.
bool isValidSudoku(vector<vector<char>>& board)
{
vector<unordered_map<char, int>> rows(9);
vector<unordered_map<char, int>> cols(9);
vector<unordered_map<char, int>> subs(9);
for (int i=0; i<9; i++)
{
for (int j=0; j<9; j++)
{
// row
char ch = board[i][j];
if(ch != '.')
{
rows[i][ch]++;
if(rows[i][ch] > 1)
return false;
cols[j][ch]++;
if(cols[j][ch] > 1)
return false;
int idx = i/3 + j-(j%3);
subs[idx][ch]++;
if(subs[idx][ch] > 1)
return false;
}
}
}
return true;
}
Точно так же при решении задач судоку мы можем использовать метод динамического программирования.Перед вставкой каждого элемента с помощью хеш-таблицы проверьте, является ли вставленный элемент допустимым.Если он не является допустимым, восстановите «место преступления» и вернитесь к предыдущему слой. .
Преобразование данных, которые не являются одним и тем же ключом, в тот же ключ
Некоторые задачи, найти все одинаковые элементы из списка, задачи разных расстановок, напримерGroup Anagramsвопрос.
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Мы можем использовать принцип хеш-таблицы, комбинировать характеристики перестановки и комбинации и преобразовывать все элементы в лексикографическом порядке, чтобы результаты этих элементов были одинаковыми и указывали на один и тот же индекс. То есть я сам написал хэш-функциюf(string){return sort(string);}. Решение проблемы следующее:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
vector<vector<string>> result;
unordered_map<string, vector<string>> map;
for(int i = 0; i < strs.size(); i++)
{
string s = strs[i];
sort(s.begin(), s.end());
map[s].push_back(strs[i]);
}
for(pair<string, vector<string>> pa:map)
{
result.push_back(pa.second);
}
return result;
}
Суммировать
объединить вышеперечисленноеLeetCodeПо проблеме, связанной с хеш-таблицей, мы можем обобщить некоторые идеи хеш-таблицы для повышения эффективности алгоритма в задачах алгоритма.
- В тех задачах, которые необходимо пройти один за другим, чтобы найти элементы, проблема может быть преобразована в поиск индекса по содержимому элемента.Эффективность времени хеш-таблицы в этом отношении очень высока;
- В некоторых задачах статистики частоты строковых слов, задачах судоку и других задачах хеш-функция может использоваться для вычисления количества вхождений элемента в качестве вспомогательного инструмента для алгоритма;
- Есть еще некоторые проблемы, вы можете использовать идею хеш-функции для получения одного и того же результата для нескольких разных элементов, тем самым реализуя кластеризацию.