Основы хеш-таблиц?

Question

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

В принципе, если кто-то ответит на этот вопрос, я думаю, что на все мои вопросы ответят: Если бы у меня было 100 случайно сгенерированных чисел (в виде ключей), как бы я реализовал хеш-таблицу и почему это было бы выгодно по сравнению с массивом?

Psuedo-код или Java были бы оценены как инструмент обучения ...

Answer 1

Ответы до сих пор помогли определить хеш-таблицы и объяснить некоторые теории, но я думаю, что пример может помочь вам лучше их понять.

В чем разница между хеш-таблицей и обычным массивом?

Хеш-таблица и массив - это структуры, которые позволяют хранить и извлекать данные. Оба позволяют указать index и получить значение, связанное с ним. Разница, как отметил Дэниел Спивак, состоит в том, что индексы массива последовательные , а индексы хеш-таблицы основаны на значении данных , связанных с ними.

Зачем мне использовать хеш-таблицу?

Хеш-таблица может обеспечить очень эффективный способ поиска элементов в больших объемах данных, особенно данных, которые иначе нелегко найти. («Большой» здесь означает ginormous в том смысле, что для последовательного поиска потребуется много времени).

Если бы я должен был закодировать хеш, как бы я начал?

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

Пример: Большой торговый центр хранит базу данных автомобилей и мест стоянки своих клиентов, чтобы помочь покупателям вспомнить, где они припарковались. В базе данных хранятся make, color, license plate и parking location. При выходе из магазина покупатель находит свою машину, указав ее марку и цвет. База данных возвращает (относительно короткий) список номерных знаков и парковочных мест. Быстрое сканирование определяет местонахождение автомобиля покупателя.

Вы можете реализовать это с помощью SQL-запроса:

SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"

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

С другой стороны, представьте себе правило хеширования:

Добавьте коды символов ASCII всех букв в марке и цвете, разделите на 100 и используйте остаток в качестве значения хеш-функции.

Это правило преобразует каждый элемент в число от 0 до 99, по сути сортируя данные в 100 сегментов. Каждый раз, когда клиенту нужно найти автомобиль, вы можете хэшировать марку и цвет, чтобы найти одно ведро из 100, содержащее информацию. Вы сразу сократили поиск в 100 раз!

Теперь масштабируйте пример до огромных объемов данных, скажем, базы данных с миллионами записей, которые ищутся по десяткам критериев. «Хорошая» хеш-функция распределяет данные по сегментам таким образом, чтобы свести к минимуму дополнительный поиск и сэкономить значительное количество времени.

Answer 2

Во-первых, вы должны понять, что такое хэш-функция. Хеш-функция - это функция, которая берет ключ (например, строку произвольной длины) и возвращает число настолько уникальное, насколько это возможно . Один и тот же ключ всегда должен возвращать один и тот же хеш. Действительно простая функция хеширования строк в 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;
}

Answer 3

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.

Я думаю, что это, вероятно, ответит на большинство ваших вопросов. Реализация хеш-таблицы - довольно интересная тема, одна из которых , к которой Википедия относится вполне сносно .

Answer 4

«Меня больше интересует, как хеш-таблицы ищут ключ и как он генерируется».

1. Хеширование превращает ключевой объект в число. Это называется «хеширование» - оно создает хеш из объекта. См. Функция хеширования . Например, суммирование байтов строки является стандартной техникой хеширования. Вы вычисляете сумму по модулю 2 ³² , чтобы сохранить хеш до приемлемого размера. Хэш всегда дает один и тот же ответ. Это O (1).

2. Число дает вам «слот» в HashTable. Для произвольного ключевого объекта хеш-значение вычисляет хеш-значение. Затем значение хеша дает вам место в таблице. Обычно mod( hash, table size ). Это также O (1).

Это общее решение. Два числовых вычисления, и вы перешли от произвольного объекта в качестве ключа к произвольному объекту в качестве значения. Мало что может быть так быстро.

Преобразование из объекта в хеш-значение происходит одним из этих распространенных способов.

1. Если это «примитивный» объект размером 4 байта, то его собственным значением является число.

2. Адрес объекта составляет 4 байта, тогда адрес объекта можно использовать в качестве значения хеш-функции.

3. Простая хеш-функция (MD5, SHA1, что угодно) накапливает байты объекта для создания 4-байтового числа. Расширенные хеши не являются простыми суммами байтов, простая сумма недостаточно точно отражает все исходные входные биты.

Слот в хеш-таблице является модом (номер, размер таблицы).

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

Алгоритмы зондирования не O (1). Если таблица достаточно велика, вероятность столкновения невелика, и пробы не имеют значения. Если таблица слишком мала, то происходят столкновения и зондирование. В этот момент возникает вопрос «настройки и настройки», чтобы сбалансировать зондирование и размер таблицы для оптимизации производительности. Обычно мы просто увеличиваем стол.

См. Хеш-таблица .

Answer 5

Что-то, чего я еще не видел, особо отмечено:

Смысл использования хеш-таблицы над массивом - это производительность.

Итерация по массиву обычно занимает от O (1) до O (x), где x - количество элементов в массиве. Однако время нахождения вашего предмета будет чрезвычайно переменным , особенно если речь идет о сотнях тысяч элементов в массиве.

Правильно взвешенная хеш-таблица обычно имеет почти постоянную время доступа чуть более O (1), независимо от количества элементов в хеш-таблице.

Answer 6

Вы не хотите использовать хеш-таблицу для 100 случайно сгенерированных чисел.

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

Допустим, у вас 10000 учеников. Если вы сохраните их все в массиве, то вам придется пройтись по всему массиву, сравнивая идентификатор студента каждой записи с тем, который вы ищете.

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

В этом примере, скажем, идентификаторы учеников - это всего лишь 6 цифр. Наша хеш-функция могла бы использовать только 3 нижние цифры номера в качестве «хеш-ключа». Таким образом, 232145 хэшируется в местоположение массива 145. Таким образом, вам нужен только массив из 999 элементов (каждый элемент представляет собой список студентов).

Это должно быть хорошим началом для вас. Вы должны, конечно, прочитать учебник или википедию для такого рода информации. Но я полагаю, что вы уже сделали это и устали читать.

Answer 7

Вот, вкратце, как работает хеш-таблица.

Представьте, что у вас есть библиотека, полная книг. Если бы вы хранили книги в массиве, вы бы поместили каждую книгу на определенное место на полке, а затем, когда кто-то попросил вас найти книгу, вы бы просмотрели все полки - довольно медленно. Если бы кто-то сказал «книга № 12345», вы могли бы найти это довольно легко, хотя.

Допустим, вместо этого вы говорите, что если название книги начинается с «A», оно идет в строке 1. Если вторая буква - «B», то она идет в строке 1, стойка 2. Если третья буква - «C». ', он идет в строке 1, стойке 2, полке 3 ... и так далее, пока вы не определите положение книги. Затем, основываясь на названии книги, вы можете точно знать, где она должна быть.

Теперь, в описанном мною упрощенном алгоритме «хэширования» есть некоторые проблемы - некоторые полки будут перегружены, а другие останутся пустыми, некоторые книги будут назначены в один и тот же слот… так что настоящие хэш-функции тщательно построен, чтобы избежать подобных проблем.

Но это основная идея.

Answer 8

Хеш-таблица - это структура данных, созданная для быстрого поиска.

Хеш-таблицы не эффективны, когда количество записей очень мало.

ссылка

Некоторые примеры:

    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

Answer 9

На этот вопрос, я полагаю, к настоящему времени дан ответ довольно четко и многими различными способами.

Я просто хотел бы добавить другую перспективу (которая также может запутать нового читателя)

На уровне наименьшей абстракции массивы - это просто непрерывный блок памяти. Учитывая начальный адрес (startAddress), размер (sizeOfElement) и index отдельного элемента, адрес элемента вычисляется как:

elementAddress = startAddress + sizeOfElement * index

Интересно отметить, что массивы можно абстрагировать / просматривать как хеш-таблицы с ключом index, а вышеуказанную функцию - как хеш-функцию, которая вычисляет местоположение значения в O (1)

Answer 10

[Это ответ на комментарий me.yahoo.com/a выше]

Это зависит от вашей хэш-функции. Предположим, что ваша хеш-функция хеширует слово в соответствии с длиной вашего слова, ключ для chris будет 5. Аналогично, ключ для yahoo также будет 5. Теперь оба значения (chris и yahoo) будут меньше 5 (т.е. в «ведре» с ключом 5). Таким образом, вам не нужно делать массив равным размеру ваших данных.