Я довольно запутался в основных понятиях таблицы Хэша. Если бы я должен был кодировать хэш, как бы я мог начать? В чем разница между таблицей Hash и обычным массивом?
В принципе, если кто-то ответил на этот вопрос, я думаю, что на все мои вопросы будет дан ответ: Если бы у меня было 100 случайно сгенерированных чисел (как ключи), как бы я мог реализовать хеш-таблицу и почему это было бы выгодно по массиву?
Psuedo-код или Java будут оценены как инструмент обучения...
Ответы до сих пор помогли определить хэш-таблицы и объяснить некоторые теории, но я думаю, что пример может помочь вам лучше понять их.
В чем разница между хэш-таблицей и обычным массивом?
Хэш-таблица и массив - это структуры, которые позволяют хранить и извлекать данные. Оба позволяют указать индекс и получить связанное с ним значение. Разница, как отметил Дэниел Спивак, заключается в том, что индексы массива являются последовательными, а таблицы хеш-таблицы основаны на значении связанных с ними данных.
Почему я должен использовать хеш-таблицу?
Хэш-таблица может обеспечить очень эффективный способ поиска элементов в больших объемах данных, особенно данных, которые в противном случае не могут быть легко доступны для поиска. ( "Большой" здесь означает ginormous в том смысле, что потребуется много времени для последовательного поиска).
Если бы я должен был кодировать хеш, как бы я мог начать?
Нет проблем. Самый простой способ - изобрести произвольную математическую операцию, которую вы можете выполнить на данных, которая возвращает число N (обычно целое число). Затем используйте это число как индекс в массив "ведра" и сохраните свои данные в ведре # N. Хитрость заключается в выборе операции, которая имеет тенденцию размещать значения в разных ковших таким образом, чтобы было легче найти их позже.
Пример: В большом торговом центре хранится база данных автомобилей и парковки своих посетителей, чтобы помочь покупателям запомнить, где они припаркованы. База данных хранит make, color, license plate и parking location. Выйдя из магазина, покупатель находит свою машину, введя ее марку и цвет. База данных возвращает (относительно короткий) список номерных знаков и парковочных мест. Быстрое сканирование позволяет найти покупателя.
Вы можете реализовать это с помощью SQL-запроса:
SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"
Если данные были сохранены в массиве, который по существу является только списком, вы можете представить себе реализацию запроса путем сканирования массива для всех соответствующих записей.
С другой стороны, представьте правило хэша:
Добавьте коды символов ASCII всех букв в make и color, разделите их на 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;
}
Hashtables являются ассоциативными. Это огромное отличие от массивов, которые представляют собой только линейные структуры данных. С массивом вы можете сделать что-то вроде этого:
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.
Я думаю, что это, вероятно, ответит на большинство ваших вопросов. Реализация хеш-таблицы - довольно интересная тема, одна с которой Википедия достаточно хорошо относится.
"Меня больше интересует то, как Hash Tables просматривают ключ и как генерируется ключ".
Хеширование преобразует ключевой объект в число. Это называется "хеширование" - это делает хэш из объекта. См. Функция хэша. Например, суммирование байтов строки является стандартной хеш-техникой. Вы вычисляете сумму по модулю 2 32 чтобы сохранить хэш в управляемом размере. Хэш всегда дает тот же ответ. Это O (1).
Номер дает вам "слот" в HashTable. Для произвольного ключевого объекта хэш-значение вычисляет хеш-значение. Хеш-значение затем дает вам слот в таблице. Обычно mod( hash, table size ). Это O (1).
Это общее решение. Два числовых вычисления, и вы выбрали произвольный объект как ключ к произвольному объекту как значение. Немногие вещи могут быть такими же быстрыми.
Преобразование из объекта в хеш-значение происходит одним из этих общих способов.
Если это "примитивный" объект из 4 байтов, то исходное значение объекта - это число.
Адрес объекта равен 4 байтам, тогда адрес объекта может использоваться как хэш-значение.
Простая хеш-функция (MD5, SHA1, независимо) накапливает байты объекта для создания 4-байтового числа. Передовые хэши - это не простые суммы байтов, простая сумма не отражает достаточно всех исходных входных бит.
Слот в хэш-таблице - мода (число, размер таблицы).
Если этот слот имеет желаемое значение, все готово. Если это не желаемое значение, вам нужно искать где-то еще. Существует несколько популярных алгоритмов зондирования для поиска свободного места в таблице. Линейный - это простой поиск следующего свободного места. Quadratic - это нелинейный прыжок вокруг в поисках свободного слота. Генератор случайных чисел (с фиксированным семенем) может использоваться для генерации серии зондов, которые будут распределять данные равномерно, но произвольно.
Алгоритмы зондирования не O (1). Если таблица достаточно большая, вероятность столкновения низкая, а зонды не имеют значения. Если таблица слишком мала, то происходит столкновение и происходит пробой. В этот момент речь идет о "настройке и настройке" для балансировки зондирования и размера таблицы для оптимизации производительности. Обычно мы просто делаем таблицу больше.
См. Таблица хэшей.
Что-то, чего я еще не видел, особо отметил:
Точка использования хэш-таблицы над массивом - это производительность.
Итерация через массив, как правило, происходит от O (1) до O (x), где x - количество элементов в массиве. Однако время поиска вашего элемента будет чрезвычайно переменным, особенно если мы говорим о сотнях тысяч элементов в массиве.
Правильно взвешенная хеш-таблица обычно имеет почти постоянное время доступа только над O (1), независимо от того, сколько элементов находится в хеш-таблице.
Вы не хотите использовать хэш-таблицу для 100 произвольно сгенерированных чисел.
Хороший способ думать о хэш-таблицах - это думать о парах значений. Позвольте использовать учащихся и сказать, что у каждого есть идентификационный номер ученика. В вашей программе вы храните информацию об учениках (имена, номера телефонов, счета и т.д.). Вы хотите найти всю информацию об ученике, используя только базовую информацию (например, имя или идентификатор студента).
Скажем, у вас 10 000 студентов. Если вы храните их все в массиве, вам нужно пройти весь массив, сравнивая каждый идентификатор студента с тем, который вы ищете.
Если вместо этого вы "хэш" (см. ниже) их идентификационный номер ученика в позицию в массиве, вам нужно только искать ученика, у которого номера имеют одинаковый хеш. Гораздо меньше усилий, чтобы найти то, что вы хотели.
В этом примере пусть скажем, что идентификаторы учащихся - всего 6 цифр. Наша хэш-функция может использовать только нижние 3 цифры номера как "хэш-ключ". Таким образом, 232145 хэшируется до местоположения массива 145. Таким образом, вам нужен только массив из 999 элементов (каждый элемент является списком студентов).
Это должно быть хорошим началом для вас. Вы должны, конечно, прочитать учебник или википедию для такого рода информации. Но я полагаю, вы уже это сделали и устали читать.
Вот, вкратце, как работает хеш-таблица.
Представьте, что у вас есть библиотека, полная книг. Если бы вы хранили книги в массиве, вы бы поставили каждую книгу на место на полке, а затем, когда кто-то попросил вас найти книгу, вы просмотрите все полки - довольно медленно. Если кто-то сказал "book # 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