Хэш или хеш как пишется

Каталог Введение

• 1. Введение в роль хэша
  • 1.1 Определение хеша
  • 1.2 Характеристики хеш-функции
  • 1.3 Сценарии использования хэша
• 2. Как определить, что два объекта равны
  • 2.1 Определить две строки
  • 2.2 Определите два значения типа int
  • 2.3 Другие основные типы
• 3. Углубленный анализ HashCode
  • 3.0 Что такое HashCode
  • 3.1 Зачем переписывать HashCode
  • 3.2 Анализ исходного кода HashCode
  • 3.3 Вопросы, внесенные HashCode
  • 3.4 Роль HashCode
  • 3.5 HashCode в HashMap
  • 3.6 Вы можете напрямую использовать хеш-код, чтобы определить, равны ли два объекта
• 4. Что такое хеш-таблица
  • 4.1 Определение хеш-таблицы
  • 4.2 Краткое описание хеш-таблицы
• 5. Применение алгоритма в Hash
  • 5.1 Основной алгоритм
  • 5.2 Классический алгоритм [отрывок из сети]
  • 5.3 Хеш-коллизия [взято из сети]
• 6. Сценарии применения Hash в Java
  • 6.1 Следует обратить внимание на два аспекта: equals и hashCode
  • 6.2 Взяв HashSet в качестве примера для иллюстрации роли hashCode ()
  • 6.3 Возьмем HashMap в качестве примера, чтобы проиллюстрировать роль Hash
  • 6.4
• 7. Обновление версии
• 8. Другое введение

хорошие новости

• Большое резюме заметок в блоге [с 16 марта по настоящее время], включая основы Java и глубокие знания, блог о технологиях Android, заметки по изучению Python и т. Д., А также сводку ошибок, обнаруженных в обычной разработке, конечно же, я также собрал после работы Большое количество вопросов для интервью, долгосрочное обновление и обслуживание, постоянное улучшение … файлы с открытым исходным кодом в формате уценки! В то же время я также открыл свой блог, посвященный жизни. За 12 лет было собрано 47 статей [почти 200 000 слов]. Пожалуйста, укажите источник при перепечатке. Спасибо!
• адрес ссылки:https://github.com/yangchong211/YCBlogs
• Если вам хорошо, вы можете пометить это, спасибо! Конечно, предложения также приветствуются: все начинает исчезать, а количественные изменения вызывают качественные изменения!

1. Введение в роль хэша

1.1 Определение хеша

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

1.2 Характеристики хеш-функции

• h (k1) h (k2), затем k1 ≠ k2, то есть значение хеш-функции отличается, тогда входное значение отличается от предварительного отображения
  • Если k1 ≠ k2, h (k1) = h (k2), то происходит столкновение;
  • Если h (k1) = h (k2), k1 не обязательно равен k2;

1.3 Сценарии использования хэша

• Например, если мы загружаем файл, процесс загрузки файла будет проходить через множество сетевых серверов и маршрутизаторов. Как мы можем гарантировать, что этот файл — то, что нам нужно? Мы не можем проверять каждый байт этого файла один за другим, и при этом мы не можем просто использовать имя файла и размер файла, которые очень легко замаскировать. В настоящее время нам требуется отпечаток пальца, чтобы проверить надежность файла. Этот тип отпечатка пальца — это алгоритм Hash (также называемый алгоритмом хеширования), который мы используем сейчас.
• Алгоритм хеширования является своего рода признаком, который гарантирует уникальность файла с более короткой информацией. Этот вид знака связан с каждым байтом файла, и трудно найти обратный закон. Следовательно, при изменении исходного файла значение его флага также будет меняться, сообщая пользователю файла, что текущий файл не тот файл, который вам нужен.
• Каково значение этого знака? Предыдущий процесс загрузки файлов является хорошим примером: на самом деле, большинство инструментов сетевого развертывания и контроля версий теперь используют хэш-алгоритмы для обеспечения надежности файлов.

2. Как судить, что два объекта равны

2.1 Определить две строки

• Используйте метод equals, чтобы определить, равны ли две строки

String a = "yc1";
String b = "yc2";
boolean isEqual = a.equals(b);

• Конечно, подклассы Object могут реализовать логику того, равны ли объекты подклассов, переписав метод equals; String является подклассом Object, проверьте его метод equals

// В классе Object
public boolean equals(Object obj) {
         // Прямое сравнение - адрес
    return (this == obj);
}

 // в классе String
public boolean equals(Object anObject) {
         // Прямое сравнение - адрес
    if (this == anObject) {
        return true;
    }
         // Тип зависания
    if (anObject instanceof String) {
        String anotherString = (String) anObject;
        int n = count;
        if (n == anotherString.count) {
            int i = 0;
                         // Цикл, чтобы определить, равен ли каждый символ
            while (n-- != 0) {
                if (charAt(i) != anotherString.charAt(i))
                        return false;
                i++;
            }
            return true;
        }
    }
    return false;
}

2.2 Определите два значения типа int

• Как реализуется метод equals класса Integer?

Integer a = Integer.valueOf("1");
Integer b = Integer.valueOf("2");
boolean ab = a.equals(b);


public boolean equals(Object obj) {
         // Сначала определяем, является ли это целочисленным типом
    if (obj instanceof Integer) {
                 // Сравнить после преобразования в значение int
        return value == ((Integer)obj).intValue();
    }
    return false;
}

2.3 Другие основные типы

// короткий тип
@Override
public int hashCode() {
    return Short.hashCode(value);
}
public static int hashCode(short value) {
    return (int)value;
}


 // Байт
@Override
public int hashCode() {
    return Byte.hashCode(value);
}
public static int hashCode(byte value) {
    return (int)value;
}

 // Длинный тип
@Override
public int hashCode() {
    return Long.hashCode(value);
}
public static int hashCode(long value) {
    return (int)(value ^ (value >>> 32));
}
 // Тип long слишком велик, как диапазон индекса, и его необходимо преобразовать в тип int. Простое получение младших 32 битов здесь может вызвать неравномерное хеширование, поскольку старшие биты не используются. Следовательно, здесь используется логический сдвиг вправо 32 бита, так что старшие 32 бита и младшие 32 бита являются XORed, в результате чего могут использоваться как старший, так и младший биты.

 // логический тип
@Override
public int hashCode() {
    return Boolean.hashCode(value);
}
public static int hashCode(boolean value) {
    return value ? 1231 : 1237;
}
 // Используем два простых числа в качестве индекса true или false. Эти два простых числа достаточно велики, чтобы их можно было использовать в качестве индекса, и вероятность столкновения мала.

3. HashCode углубленный анализ

3.0 Что такое HashCode

• HashCode — это метод Object. Метод hashCode возвращает значение хеш-кода, и этот метод предназначен для лучшей поддержки хеш-таблиц, таких как String, Set, HashTable, HashMap и т. Д .;

3.1 Зачем переписывать HashCode

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

3.2 Анализ исходного кода HashCode

• Исходный код HashCode в Object

public int hashCode() {
    int lockWord = shadow$_monitor_;
    final int lockWordStateMask = 0xC0000000; // Top 2 bits.
    final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash).
    final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits.
    if ((lockWord & lockWordStateMask) == lockWordStateHash) {
        return lockWord & lockWordHashMask;
    }
         // Возвращает адрес ссылки на объект
    return System.identityHashCode(this);
}

• Исходный код HashCode в String

public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        for (int i = 0; i < count; i++) {
            h = 31 * h + charAt(i);
        }
        hash = h;
    }
    return h;
}

• Исходный код HashCode в Integer

public int hashCode() {
         // значение int
    return value;
}

3.3 Вопросы, внесенные HashCode

• Почему перезапись равно предлагает переписать hashCode одновременно?
• Что такое хэш-код?
• Что делает hashCode?
• Что такое хэш-код (хэш-значение)?
• Что такое хеш-таблица?
• Метод hashCode хорош для хеш-таблиц?
• Метод hashCode хорош для хеширования?

3.4 Роль HashCode

• Сократить время поиска и повысить эффективность программы
  • Например, найдите, есть ли повторяющиеся значения
    • h (k1) ≠ h (k2), тогда k1 ≠ k2
    • Сначала проверьте выходное значение (адрес памяти) h (k2), чтобы увидеть, есть ли значение в адресе памяти;
    • Если нет, это означает, что для этого значения нет повторяющегося значения;
    • Если есть, выполняется сравнение значений. Если значение одинаковое, это означает, что значение уже существует в хэш-списке. Если оно не совпадает, то сравнение значений выполняется одно за другим, вместо сравнения значений один за другим в начале число поисков уменьшается.

3.5 HashCode в HashMap

• То же самое относится и к Java. Основная функция метода hashCode заключается в совместной работе с коллекциями на основе хешей. К таким коллекциям хешей относятся HashSet, HashMap и HashTable.
• Почему ты это сказал? Рассмотрим ситуацию, когда при вставке объекта в коллекцию как определить, существует ли объект в коллекции?(Примечание: повторяющиеся элементы не допускаются в коллекции)
  • Возможно, большинство людей подумают о вызове метода equals для сравнения по одному, этот метод действительно выполним. Однако, если в сборе уже есть 10 000 или более данных, и если для сравнения используется метод равных, эффективность должна быть проблемой.
  • В это время отражается роль метода hashCode. Когда новый объект добавляется в коллекцию, сначала вызывается метод hashCode этого объекта для получения соответствующего значения хэш-кода. Фактически, в конкретной реализации HashMap будет использоваться таблица для его сохранения. Значение хеш-кода объекта, если в таблице нет значения хеш-кода, его можно сохранить напрямую без какого-либо сравнения, если значение хеш-кода существует, он вызывает метод equals для сравнения с новым элементом, если его нет Если он сохранен, другие адреса хэшируются, поэтому возникает проблема разрешения конфликтов. Таким образом, число случаев, когда метод equals фактически вызывается, значительно сокращается. Другими словами, метод hashCode в Java основан на определенных правилах. Информация, относящаяся к объекту (например, адрес хранения объекта, поле объекта и т. Д.) Отображается в числовое значение, которое называется значением хеш-функции. Следующий код представляет собой конкретную реализацию метода put в java.util.HashMap:
• Метод put используется для добавления нового элемента в HashMap. Из конкретной реализации метода put мы сначала вызовем метод hashCode для получения значения hashCode элемента, а затем проверим, существует ли значение hashCode в таблице. Определите, существует ли элемент, и, если он существует, обновите значение, в противном случае добавьте новый элемент в HashMap. Из этого видно, что существование метода hashCode заключается в уменьшении количества вызовов метода equals, что повышает эффективность программы.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

3.6 Вы можете напрямую использовать хеш-код, чтобы определить, равны ли два объекта

• Конечно, это невозможно, потому что разные объекты могут генерировать одно и то же значение хэш-кода. Хотя невозможно судить, равны ли два объекта по значению хеш-кода, вы можете напрямую судить о двух объектах по значению хэш-кода.Если значения хэш-кода двух объектов не равны, они должны быть двумя разными объектами. Если вы хотите оценить, действительно ли два объекта равны, вы должны пройти метод equals.
• То есть для двух объектов, если результат, полученный при вызове метода equals, равен true, значения хэш-кода двух объектов должны быть равны;
  • Если результат, полученный методом equals, равен false, значения хеш-кода двух объектов не обязательно различаются;
  • Если значения хеш-кода двух объектов не равны, результат, полученный методом equals, должен быть ложным;
  • Если значения хэш-кода двух объектов равны, результат, полученный методом equals, неизвестен.

4. Что такое хэш-таблица

4.1 Определение хеш-таблицы

• Структура данных, к которой осуществляется прямой доступ в соответствии со значением кода клавиши (KEY-VALUE), она обращается к записи путем сопоставления значения кода ключа (KEY-VALUE) с местоположением в таблице для ускорения поиска. Эта функция отображения называется хеш-функцией, а массив записей называется хеш-таблицей.

4.2 Краткое описание хеш-таблицы

• Используйте k в качестве входного значения и h (k) в качестве адреса памяти. Адрес памяти используется для хранения значения, и затем адрес, где хранится значение, может быть получен через k для получения информации о значении.

5. Применение алгоритма в Hash

5.1 Основной алгоритм

• Например, String.hashCode в Java использует умножение и сложение

public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        for (int i = 0; i < count; i++) {
                         // Умножение и сложение
            h = 31 * h + charAt(i);
        }
        hash = h;
    }
    return h;
}

5.2 Классический алгоритм [отрывок из сети]

• MD4, MD5, SHA-1 или SHA-2 и т. Д.

5.3 Хеш-коллизия [взято из сети]

• Хеш — столкновение, если k1 ≠ k2, h (k1) = h (k2), то столкновение происходит;

6. Сценарии хэширования приложений в Java

6.1 Следует обратить внимание на два аспекта: equals и hashCode

• Если одинаковые значения равны, hashCode одинаковы, а если одинаковый hashCode, равные значения не обязательно совпадают
  • Если равенства одинаковы, а хэш-код не совпадает, это может привести к появлению вышеуказанных дублирующих значений и других ситуаций, что недопустимо;
  • HasCode — то же самое, но равенства не обязательно одинаковы. Возможно, что столкновение может произойти из-за столкновения.

6.2 Взяв HashSet в качестве примера для иллюстрации роли hashCode ()

• Предположим, что в HashSet уже есть 1000 элементов. Что делать при вставке 1001-го элемента?
  • Поскольку HashSet является коллекцией Set, он допускает дублирование элементов. «Сравнить 1001-й элемент с предыдущими 1000 элементами один за другим»?
  • Очевидно, что эта эффективность одинаково низка. Хеш-таблица очень хорошо решает эту проблему: она вычисляет положение элемента в хеш-таблице в соответствии с хеш-кодом элемента, а затем вставляет элемент в эту позицию. Для одного и того же элемента, естественно, сохраняется только один.
  • Можно видеть, что если два элемента равны, их хэш-коды должны быть равны, но обратное не обязательно имеет место. В хеш-таблице
    • 1. Если два объекта равны, их значение hashCode () должно быть одинаковым;
    • 2. Если два объекта hashCode () равны, они не обязательно равны.
    • Примечание. Это случай хеш-таблиц. Это должно быть верно для нехеш-таблиц!

6.3 Возьмем HashMap в качестве примера, чтобы проиллюстрировать роль Hash

• Алгоритм хеширования используется во многих местах в HashMap

// метод put
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

 // удалить метод
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

 // получить метод
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

 // Все вышеперечисленные методы используют этот метод
static final int hash(Object key) {
    int h;
         // Вычисляем hashCode, ни один символ не перемещается в младший бит
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 Например: h = 363771819 ^ (363771819 >>> 16)
0001 0101 1010 1110 1011 0111 1010 1011(363771819)
0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR
--------------------------------------- =
0001 0101 1010 1110 1010 0010 0000 0101(363766277)
 Таким образом, высокий статус может быть смешан более равномерно

Ссылочный блог

• Механизм хранения Java Hash:http://blog.chinaunix.net/uid-26981819-id-4462638.html
• Хеш-таблица структуры данных:https://www.cnblogs.com/s-b-b/p/6208565.html
• Java hashCode () и equals () отвечает на несколько вопросов:https://www.cnblogs.com/skywang12345/p/3324958.html
• Краткое описание алгоритма хеширования:https://blog.csdn.net/asdzheng/article/details/70226007
• Говоря о методе хеширования в Java:http://www.cnblogs.com/dolphin0520/p/3681042.html

О другом представлении контента

01. Об краткой ссылке на блог

• 1.Техническое резюме блога
• 2.Краткое описание проекта с открытым исходным кодом
• 3.Жизнь Блог Резюме
• 4.Гималайский аудио резюме
• 5.Другое резюме

02. О моем блоге

• Мой личный сайт:www.yczbj.org，www.ycbjie.cn
• github：https://github.com/yangchong211
• Почти знаю:https://www.zhihu.com/people/yang-chong-69-24/pins/posts
• Краткая книга:http://www.jianshu.com/u/b7b2c6ed9284
• csdn：http://my.csdn.net/m0_37700275
• Гималайское слушание:http://www.ximalaya.com/zhubo/71989305/
• Открытый исходный код Китая:https://my.oschina.net/zbj1618/blog
• Дни в интернете:http://www.jcodecraeer.com/member/content_list.php?channelid=1
• Электронная почта: [email protected]
• Облачный блог Alibaba:https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
• Сегментфоал заголовки:https://segmentfault.com/u/xiangjianyu/articles