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

Хеш-таблицы - ассоциативный. Это огромное отличие от массивов, которые представляют собой просто линейные структуры данных. С массивом вы можете сделать что-то вроде этого:

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.

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

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

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

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

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

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

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

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

Массив - это просто упорядоченный список объектов. Сам объект на самом деле не имеет значения ... важно то, что если вы хотите перечислить объекты в порядке вставки, он всегда один и тот же (это означает, что первый элемент всегда имеет индекс 0).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Скажем, вместо этого вы скажете, что если название книги начинается с «А», оно идет в строке 1. Если вторая буква - «В», она идет в строку 1, стойку 2. Если третья буква - «С», это идет в ряду 1, стойке 2, полке 3 ... и так далее, пока вы не определите положение книги. Тогда, основываясь на названии книги, вы сможете точно знать, где она должна быть.

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

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

То, что я еще не заметил особо:

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

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

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

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

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

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

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

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

Если бы я кодировал хеш, с чего бы я вообще начал?

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

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

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

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

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

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

Add the ASCII character codes of all the letters in the make and color, divide by 100, and use the remainder as the hash value.

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

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

На этот вопрос, как мне кажется, уже дан достаточно четкий и по-разному ответ.

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

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

elementAddress = startAddress + sizeOfElement * index

Здесь интересно отметить, что массивы можно абстрагировать / просматривать как хеш-таблицы с index в качестве ключа, а указанную выше функцию как хеш-функцию, которая вычисляет местоположение значения в О (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