Хэш: Как это работает внутри?

Question

Это может звучать как очень неопределенный вопрос, но это не так. Я просмотрел Hash Function описание на wiki, но это не очень полезно понять.

Я ищу простые ответы на довольно сложные темы, такие как Hashing. Вот мои вопросы:

1. Что мы подразумеваем под хешированием? Как это работает внутри страны?
2. Какой алгоритм следует?
3. В чем разница между HashMap, HashTable и HashList?
4. Что мы подразумеваем под «Constant Time Complexity» и почему различная реализация хэша дает постоянную работу во времени?
5. И наконец, почему в большинстве вопросов интервью Hash и LinkedList спрашивают, есть ли какая-то конкретная логика для этого из проверки знаний собеседника?

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

Answer 1

1. Here хорошее объяснение о хэширования. Например, вы хотите сохранить строку «Rachel», вы применяете хеш-функцию к этой строке, чтобы получить ячейку памяти. myHashFunction(key: "Rachel" value: "Rachel") --> 10. Функция может возвращать 10 для ввода «Rachel», поэтому, если у вас есть массив размером 100, вы храните «Rachel» в индексе 10. Если вы хотите получить этот элемент, вы просто вызываете GetmyHashFunction("Rachel"), и он вернется 10. Обратите внимание, что для этого Например, ключ «Rachel», а значение «Rachel», но вы можете использовать другое значение для этого ключа, например, дату рождения или объект. Ваша хэш-функция может возвращать одну и ту же ячейку памяти для двух разных входов, в этом случае у вас будет столкновение с вами, если вы реализуете свою собственную хеш-таблицу, о которой вы должны позаботиться, возможно, используя связанный список или другие методы.

2. Here - некоторые распространенные хэш-функции. Хорошая хэш-функция удовлетворяет тому, что: каждый ключ одинаково вероятен для хэша в любом из n слотов памяти независимо от того, где хэширует любой другой ключ. Один из методов называется методом деления. Наведем ключ k в один из n слотов, взяв остаток k, деленный на n. h(k) = k mod n. Например, если ваш размер массива составляет n = 100, и ваш ключ является целым числом k = 15, то h(k) = 10.

3. Hashtable синхронизирован, а Hashmap - нет. Hashmap позволяет вводить нулевые значения в качестве ключа, но Hashtable этого не делает.

4. Цель хэш-таблицы состоит в том, чтобы иметь постоянную временную сложность O (c) при добавлении и получении элементов. В связанном списке размера N, если вы хотите получить последний элемент, вам нужно пройти весь список до тех пор, пока вы его не получите, поэтому сложность - O (N). С хэш-таблицей, если вы хотите получить элемент, вы просто передаете ключ, и хеш-функция вернет вам нужный элемент. Если хеш-функция хорошо реализована, она будет находиться в постоянном времени. O (c) Это означает, что вам не нужно перемещать все элементы, хранящиеся в хеш-таблице. Вы получите элемент «мгновенно».

5. Кауса программирует на/разработчик ученый должен знать о структурах данных и сложности =)

Answer 2

1. Хеширование означает создание уникального числа, которое представляет собой значение.
2. Различные типы значений (Integer, String и т. Д.) Используют разные алгоритмы для вычисления хэш-кода.
3. HashMap and HashTable - ; они представляют собой набор ключей unqiue, каждый из которых связан со значением.
   Java не имеет класса HashList. A Hash Набор представляет собой набор уникальных значений.
4. Получение элемента из хеш-таблицы является постоянным временем относительно размера таблицы.
   Вычисление хеша не обязательно постоянное время относительно хэширования значения.
   Например, вычисление хэша строки включает в себя итерирование строки и не является постоянным временем относительно размера строки.
5. Это вещи, которые люди должны знать.

Answer 3

1. хеширование преобразует заданный объект (в терминах Java - объект) к некоторому числу (или последовательности). Хеш-функция не обратима - т. Е. Вы не можете получить исходный объект из хэша. Внутренне она реализована (для java.lang.Object, получив некоторый адрес памяти в JVM.

2. Виртуальная машина Java адрес вещь несущественна деталь. Каждый класс может переопределить метод hashCode() со своим собственным алгоритмом. Modren Java Иды позволяют генерировать хорошие методы Hashcode .

3. Hashtable и HashMap те же, что они пары ключ-значение, где ключи перемешаны списки Хеш и hashsets делать не ценности магазина -... только ключи

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

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

Answer 4

Что мы подразумеваем под хешированием, как же она работает внутри?

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

Какой алгоритм следует?

В простых словах большинство алгоритмов хэширования работает по логике «индекс = е (ключ, arrayLength)»

Наконец, почему в большинстве интервью вопросов Hash и LinkedList являются спросил, является существует ли какая-то конкретная логика для от знания интервьюируемого интервьюируемого?

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

Answer 5

Я попытаюсь дать простые объяснения хэширования и его цели.

Сначала рассмотрим простой список. Каждая операция (вставить, найти, удалить) в таком списке будет иметь сложность O (n), что означает, что вам необходимо проанализировать весь список (или половину его в среднем) для выполнения такой операции.

Хешинг - это очень простой и эффективный способ ускорить его: учтите, что мы разделили весь список в наборе небольших списков. Элементы в одном таком небольшом списке будут иметь что-то общее, и это может быть выведено из ключа. Например, имея список имен, мы могли бы использовать первую букву как качество, которое будет выбирать, в каком маленьком списке искать. Таким образом, разбив данные на первую букву ключа, мы получили простой хеш, который сможет разбить весь список в ~ 30 меньших списков, так что каждая операция будет принимать O (n)/30 раз ,

Однако мы могли бы отметить, что результаты не настолько совершенны. Во-первых, их всего 30, и мы не можем их изменить. Во-вторых, некоторые буквы используются чаще, чем другие, так что набор с Y или Z будет намного меньше, чем набор с A. Для получения лучших результатов лучше найти способ разделения элементов в наборах примерно такого же размера. Как мы можем это решить? Здесь вы используете хэш-функции. Это такая функция, которая способна создавать произвольное количество разделов с примерно одинаковым количеством элементов в каждом. В нашем примере с именами, мы могли бы использовать что-то вроде

int hash(const char* str){ 
    int rez = 0; 
    for (int i = 0; i < strlen(str); i++) 
     rez = rez * 37 + str[i]; 
    return rez % NUMBER_OF_PARTITIONS; 
}; 

это обеспечило бы довольно равномерное распределение и настраиваемое количество наборов (называемых также ведер).

Answer 6

Рассмотрите проблему поиска массива для заданного значения. Если массив не отсортирован, поиск может потребовать проверки всех элементов массива. Если массив отсортирован, мы можем использовать двоичный поиск и, следовательно, уменьшить сложность выполнения в худшем случае до O (log n). Мы могли бы искать еще быстрее, если мы заранее знаем индекс, в котором это значение находится в массиве. Предположим, что у нас есть эта магическая функция, которая сообщит нам индекс для данного значения. С помощью этой магической функции наш поиск сводится только к одному зонду, что дает нам постоянное время выполнения O (1). Такая функция называется хэш-функцией. Хеш-функция - это функция, которая при задании ключа генерирует адрес в таблице.