Основы работы с хэш-таблицами?
https://stackoverflow.com/questions/282712
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я совсем запутался в основных понятиях хэш-таблицы.Если бы я должен был закодировать хэш, с чего бы я вообще начал?В чем разница между хэш-таблицей и просто обычным массивом?
В принципе, если бы кто-нибудь ответил на этот вопрос, я думаю, что на все мои вопросы были бы даны ответы:Если бы у меня было 100 случайно сгенерированных чисел (в качестве ключей), как бы я реализовал хэш-таблицу и почему это было бы выгоднее по сравнению с массивом?
Псевдокод или Java были бы оценены как инструмент обучения...
Решение
Ответы до сих пор помогли определить хеш-таблицы и объяснить некоторые теории, но я думаю, что пример может помочь вам лучше понять их.
В чем разница между хеш-таблицей и обычным массивом?
Хеш-таблица и массив - это структуры, которые позволяют хранить и извлекать данные. Оба позволяют вам указать индекс и получить значение, связанное с ним. Различие, как отметил Дэниел Спивак, состоит в том, что индексы массива являются последовательными , а индексы хеш-таблицы основаны на значении данных , связанных с ними.
Зачем мне использовать хеш-таблицу?
Хеш-таблица может обеспечить очень эффективный способ поиска элементов в больших объемах данных, особенно данных, которые иначе не легко найти. (" Большой " здесь означает ginormous в том смысле, что потребовалось бы много времени для выполнения последовательного поиска).
Если бы я должен был закодировать хеш, как бы я начал?
Нет проблем. Самый простой способ - изобрести произвольную математическую операцию, которую вы можете выполнить с данными, которая возвращает число N (обычно целое число). Затем используйте это число в качестве индекса в массиве "buckets". и сохраните ваши данные в корзине # N . Хитрость заключается в выборе операции, которая стремится разместить значения в разных сегментах таким образом, чтобы вам было легче их найти позже.
Пример. Большой торговый центр ведет базу данных автомобилей и мест стоянки своих клиентов, чтобы помочь покупателям вспомнить, где они припарковались. В базе данных хранятся make , color , номерной знак и место для парковки . При выходе из магазина покупатель находит свою машину, указав ее марку и цвет. База данных возвращает (относительно короткий) список номерных знаков и парковочных мест. Быстрое сканирование определяет местонахождение автомобиля покупателя.
Вы можете реализовать это с помощью SQL-запроса:
SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"
Если данные были сохранены в массиве, который, по сути, является просто списком, вы можете представить реализацию запроса, отсканировав массив для всех соответствующих записей.
С другой стороны, представьте себе правило хеширования:
Добавьте коды символов ASCII всех букв в марке и цвете, разделите на 100 и используйте остаток в качестве значения хеш-функции.
Это правило преобразует каждый элемент в число от 0 до 99, по сути сортируя данные в 100 сегментов. Каждый раз, когда клиенту нужно найти автомобиль, вы можете хэшировать марку и цвет, чтобы найти один контейнер из 100, содержащий информацию. Вы сразу сократили поиск в 100 раз!
Теперь масштабируйте пример до огромных объемов данных, например, базы данных с миллионами записей, которые ищутся по десяткам критериев. "Хорошо" Хеш-функция будет распределять данные в сегменты таким образом, чтобы свести к минимуму дополнительный поиск и сэкономить значительное количество времени.
Другие советы
Во-первых, вы должны понять, что такое хеш-функция. Хеш-функция - это функция, которая берет ключ (например, строку произвольной длины) и возвращает число настолько уникальное, насколько это возможно . Один и тот же ключ всегда должен возвращать один и тот же хеш. Действительно простая функция хеширования строк в Java может выглядеть так:
public int stringHash(String s) {
int h = s.length();
for(char c : s.toCharArray()) {
h ^= c;
}
return h;
}
Хорошую хэш-функцию можно изучить по адресу http://www.azillionmonkeys.com/qed/. hash.html
Теперь хеш-карта использует это хеш-значение для помещения значения в массив. Упрощенный метод Java:
public void put(String key, Object val) {
int hash = stringHash(s) % array.length;
if(array[hash] == null) {
array[hash] = new LinkedList<Entry<String, Object> >();
}
for(Entry e : array[hash]) {
if(e.key.equals(key)){
e.value = val;
return;
}
}
array[hash].add(new Entry<String, Object>(key, val));
}
(На этой карте применяются уникальные ключи. Не на всех картах.)
Можно использовать два разных ключа для хэширования с одним и тем же значением или два разных хэша для сопоставления с одним и тем же индексом массива. Существует много способов борьбы с этим. Самое простое - использовать связанный список (или двоичное дерево) для каждого индекса массива. Если хеш-функция достаточно хороша, вам никогда не понадобится линейный поиск.
Теперь ищем ключ:
public Object get(String key) {
int hash = stringHash(key) % array.length;
if(array[hash] != null) {
for(Entry e : array[hash]) {
if(e.key.equals(key))
return e.value;
}
}
return null;
}
Хеш-таблицы являются ассоциативными . Это огромное отличие от массивов, которые являются просто линейными структурами данных. С массивом вы можете сделать что-то вроде этого:
int[] arr = ...
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + 1);
}
Обратите внимание, как вы получаете элемент из массива, указав точное смещение памяти ( i ). Это отличается от хеш-таблиц, которые позволяют хранить пары ключ / значение, а затем извлекать значение на основе ключа:
Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);
С помощью приведенной выше таблицы мы можем сделать следующий вызов:
int n = table.get("Chris");
... и будьте уверены, что n будет оценено как 18 .
Я думаю, что это, вероятно, ответит на большинство ваших вопросов. Внедрение хеш-таблицы - довольно интересная тема, , которую Википедия хорошо прорабатывает .
"Меня больше интересует, как хэш-таблицы ищут ключ и как этот ключ генерируется".
Хеширование преобразует ключевой объект в число.Это называется "хеширование" - оно создает хэш из объекта.Видишь Хэш-функция.Например, суммирование байтов строки является стандартным методом хэширования.Вы вычисляете сумму по модулю 232 чтобы сохранить хэш приемлемого размера.Хэш всегда дает один и тот же ответ.Это O(1).
Это число дает вам "слот" в хэш-таблице.Учитывая произвольный ключевой объект, хэш-значение вычисляет хэш-значение.Затем хэш-значение дает вам слот в таблице.Обычно
mod( hash, table size ).Это O(1), также.
Это общее решение.Два числовых вычисления, и вы перешли от произвольного объекта в качестве ключа к произвольному объекту в качестве значения.Мало что может быть сделано так быстро.
Преобразование объекта в хэш-значение происходит одним из этих распространенных способов.
Если это "примитивный" объект размером 4 байта, то собственным значением объекта является число.
Адрес объекта равен 4 байтам, тогда адрес объекта можно использовать в качестве хэш-значения.
Простой хэш-функция (MD5, SHA1, что угодно) накапливает байты объекта для создания 4-байтового числа.Расширенные хэши - это не простые суммы байтов, простая сумма недостаточно точно отражает все исходные входные биты.
Ячейкой в хэш-таблице является mod (номер, размер таблицы).
Если этот слот имеет желаемое значение, все готово.Если это не желаемое значение, вам нужно поискать где-нибудь в другом месте.Существует несколько популярных алгоритмов поиска свободного места в таблице.Linear - это простой поиск следующего свободного места.Quadratic - это нелинейное хождение по кругу в поисках свободного слота.Генератор случайных чисел (с фиксированным начальным значением) может быть использован для генерации серии пробников, которые будут распределять данные равномерно, но произвольно.
Алгоритмы зондирования не являются O(1).Если стол достаточно большой, вероятность столкновения невелика, и зонды не имеют значения.Если таблица слишком мала, то происходят коллизии и происходит зондирование.На этом этапе речь идет о "настройке", чтобы сбалансировать параметры зондирования и размер таблицы для оптимизации производительности.Обычно мы просто делаем стол больше.
Видишь Хэш- таблица.
Что-то, что я еще не видел, особо отмечено
Смысл использования хеш-таблицы над массивом - это производительность.
Итерация по массиву обычно занимает от O (1) до O (x), где x - количество элементов в массиве. Однако время поиска вашего элемента будет чрезвычайно переменным , особенно если речь идет о сотнях тысяч элементов в массиве.
Правильно взвешенная хеш-таблица обычно имеет почти постоянное время доступа чуть более O (1), независимо от того, сколько элементов в хеш-таблице.
Вы не хотите использовать хеш-таблицу для 100 случайно сгенерированных чисел.
Хороший способ думать о хеш-таблицах - думать о парах значений. Давайте использовать студентов и скажем, что у каждого есть идентификационный номер студента. В вашей программе вы храните информацию о студентах (имена, номера телефонов, счета и т. Д.). Вы хотите найти всю информацию о студенте, используя только основную информацию (например, имя или идентификатор студента).
Допустим, у вас есть 10000 студентов. Если вы сохраните их все в массиве, то вам придется пройтись по всему массиву, сравнивая идентификатор студента каждой записи с тем, который вы ищете.
Если вместо этого вы " хэш " (см. ниже) их идентификационный номер учащегося до позиции в массиве, тогда вам нужно только искать номера учеников, которые имеют одинаковый хэш. Гораздо меньше работы, чтобы найти то, что вы хотели.
В этом примере предположим, что идентификаторы учеников состоят из 6 цифр. Наша хеш-функция могла бы использовать только 3 нижние цифры номера в качестве «хэш-ключа». Таким образом, 232145 хэшируется в местоположение массива 145. Таким образом, вам нужен только массив из 999 элементов (каждый элемент является списком студентов).
Это должно стать хорошим началом для вас. Вы должны, конечно, прочитать учебник или википедию для такого рода информации. Но я полагаю, что вы уже сделали это и устали читать.
Вот, вкратце, как работает хеш-таблица.
Представьте, что у вас есть библиотека, полная книг. Если бы вы хранили книги в массиве, вы бы поместили каждую книгу на определенное место на полке, а затем, когда кто-то попросил вас найти книгу, вы бы просмотрели все полки - довольно медленно. Если бы кто-то сказал «книга # 12345», вы могли бы найти это довольно легко.
Допустим, вместо этого вы говорите, что если название книги начинается с «A», оно идет в строке 1. Если вторая буква - «B», то она идет в строке 1, стойка 2. Если третья буква - «C». ', он идет в строке 1, стойке 2, полке 3 ... и так далее, пока вы не определите положение книги. Затем, основываясь на названии книги, вы можете точно знать, где она должна быть.
Теперь существуют некоторые проблемы в упрощенном "хешировании". Алгоритм, который я описал - некоторые полки будут перегружены, в то время как другие останутся пустыми, некоторые книги будут назначены в один и тот же слот ... поэтому настоящие хэш-функции тщательно созданы, чтобы избежать подобных проблем.
Но это основная идея.
Я отвечу на эту часть о разнице между хеш-таблицей и массивом ... но, поскольку я никогда ранее не реализовывал алгоритм хеширования какого-либо импорта, я оставлю это кому-то более знающему:)
Массив - это просто упорядоченный список объектов. Сам объект на самом деле не имеет значения ... важно то, что если вы хотите перечислить объекты в порядке вставки, это всегда одинаково (это означает, что первый элемент всегда имеет индекс 0).
Что касается хеш-таблицы, она индексируется по ключам, а не по порядку ... Я думаю, что базовый поиск по алгоритмам хеширования даст вам гораздо больше понимания, чем я могу ... В Википедии есть очень приличный ... что определяет «ведро» что ключи используются для быстрого поиска произвольных объектов, используемых в качестве ключей.
Что касается преимуществ: если важен порядок вставки, необходим массив или какой-то упорядоченный список. Если важен быстрый поиск по произвольному ключу (основанному на различных хеш-функциях), тогда имеет смысл использовать хеш-таблицу.
[Это ответ на комментарий me.yahoo.com/a выше]
Это зависит от вашей хэш-функции. Предположим, что ваша хеш-функция хэширует слово в соответствии с длиной вашего слова, ключ для chris будет 5. Аналогично, ключ для yahoo также будет 5. Теперь оба значения (chris и yahoo) будут меньше 5 (т.е. в «ведре» с ключом 5). Таким образом, вам не нужно делать массив равным размеру ваших данных.
Я полагаю, что к настоящему времени на этот вопрос дан достаточно четкий ответ, причем самыми разными способами.
Я просто хотел бы добавить еще одну точку зрения (которая также может сбить с толку нового читателя).
На уровне наименьшей абстракции массивы - это просто непрерывный блок памяти.Дан начальный адрес (startAddress), размер (sizeOfElement) и тот index для одного элемента адрес элемента вычисляется как:
elementAddress = startAddress + sizeOfElement * index
Здесь интересно отметить, что массивы могут быть абстрагированы / просмотрены как хэш-таблицы с index как ключ и вышеупомянутая функция как хэш-функция, которая вычисляет местоположение значения в O(1)
Хэш-таблица - это структура данных, которая создается для быстрого поиска.
Хэш-таблицы неэффективны, когда количество записей очень мало.
Несколько примеров:
import java.util.Collection;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Set;
public class HashtableDemo {
public static void main(String args[]) {
// Creating Hashtable for example
Hashtable companies = new Hashtable();
// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map
companies.put("Google", "United States");
companies.put("Nokia", "Finland");
companies.put("Sony", "Japan");
// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable
companies.get("Google");
// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable
System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));
// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value
System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));
// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values
Enumeration enumeration = companies.elements();
while (enumeration.hasMoreElements()) {
System.out.println("hashtable values: "+enumeration.nextElement());
}
// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java
System.out.println("Is companies hashtable empty: "+companies.isEmpty());
// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java
System.out.println("Size of hashtable in Java: " + companies.size());
// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java
Set hashtableKeys = companies.keySet();
// you can also get enumeration of all keys by using method keys()
Enumeration hashtableKeysEnum = companies.keys();
// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection
Enumeration hashtableValuesEnum = companies.elements();
Collection hashtableValues = companies.values();
// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.
companies.clear();
}
}
Выходной сигнал:
Does hashtable contains Google as key: true
Does hashtable contains Japan as value: true
hashtable values: Finland
hashtable values: United States
hashtable values: Japan
Is companies hashtable empty: false
Size of hashtable in Java: 3
