Что происходит на самом деле (фактический процесс), когда мы хешируем определенную строку или слово

Question

Привет, я пытаюсь разработать фильтр подсчета Блума в Java. Я действительно искал большинство источников о фильтре Блума. Я понял, что когда мы хэшируем (делаем хэширование) конкретную строку или слово, результат хеширования возвращает одно значение, чтобы мы могли сохранить содержимое в этом результирующем значении. место. Но мой большой вопрос, как сделать хеширование (алгоритм). Что действительно происходит, когда мы хешируем определенную строку или слово. Можете ли вы объяснить мне, что на самом деле происходит, когда мы хешируем определенную строку или слово (например, как получается конкретное конечное значение, когда мы выполняем хеширование для определенной строки или слова). Я также читал, что есть также вероятность столкновения. Можете ли вы также указать, почему результирующее хеш-значение не является уникальным (почему его иногда возвращает одно и то же хеш-значение для разных входных данных). И действительно ли мне нужно написать код для хеширования или в java есть встроенные функции для хеширования.

Answer 1

«Хеширование» - это функция

H: I -> O

Где обычно набор I гораздо больше или сложнее, чем O. В хеш-таблице I - это класс ваших элементов, а O - это набор натуральных чисел. В частности, в фильтре Блума у ​​вас есть n различных функций. Для разработки хеш-функции вам нужно извлечь различные характеристики похожих объектов. Например, для строк символов вы можете иметь:

• длина
• первый символ
• количество вхождений конкретного символа
• строка, оцененная как полином h(S) = sum (s(i)*31^i) mod d

При использовании множественного хэширования следует избегать коллизий характеристик, например, использование number of voyels и number of non-voyels не очень полезно. У хэш-функции есть некоторые характеристики, посмотрите на запись в википедии

Answer 2

Вы можете просто получить хеш-код, вызвав hashCode() для любого объекта. В частности для класса String из javadoc :

public int hashCode ()

Возвращает хеш-код для этой строки. Хеш-код для объекта String вычисляется как

s [0] * 31 ^ (n-1) + s [1] * 31 ^ (n-2) + ... + s [n-1]

с использованием int арифметики, где s [i] - i-й символ строки, n длина строки, а ^ обозначает возведение в степень. (Хеш значение пустой строки равно нулю.)

Answer 3

Java позволяет вам переопределить метод hashCode () для ваших Классов, чтобы использовать алгоритм хеширования

public class Employee {


   // Default implementation might want to use "name" for as part of hashCode
   private String name; 

   @Override
   public int hashCode() {
     // We know that ID is always unique, so don't use name in calculating 
     // the hash code. & hashCode() is an int
     return id;
   }
}

* (если вы собираетесь переопределить hashCode, вам также следует переопределить equals.)

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

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

Answer 4

Код, выполненный для String, такой:

public int hashCode() {
int h = hash;
    int len = count;
if (h == 0 && len > 0) {
    int off = offset;
    char val[] = value;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

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