Рубрики
Без рубрики

Демистификация хэшей, карт и хеширования

первоначально опубликовано по адресу computingtogether.org Когда вы погружаетесь в изучение нового языка программирования, т… С тегами javascript, ruby, java, codenewbie.

первоначально опубликовано по адресу первоначально опубликовано по адресу

Когда вы погружаетесь в изучение нового языка программирования, есть несколько стандартных концепций, которые, как правило, очень полезны. Одним из них является структура данных, представляющая список пар ключ-значение, где каждый ключ соответствует одному и только одному значению. Однако само значение может быть другой структурой данных, содержащей много значений. В этом сообщении в блоге будет рассказано о картах в Ruby и Javascript и о том, как их использовать в каждом из них.

Объявление и инициализация хэшей Ruby

hash_identifier =  { key1 => value1, key2 => value2 }

Вот пример объявления и инициализации Ruby с использованием строк в качестве ключей.

attendance = {"Sarah" => 4, "Chris" => 6, "Alex" => 1}

puts attendance
# {:sarah=>4, :chris=>6, :alex=>1}

Это что-то вроде сокращения для:

attendance = {:sarah => 4, :chris => 6, :alex => 1}

и, кстати, людям нравится называть => “хэш-ракетой”.

В Ruby, если ключи являются символами (что быстрее, чем использование строк в качестве ключей), вы можете использовать этот формат в стиле JSON.

attendance = {sarah: 4, chris: 6, alex: 1}

Доступ к хэшам Ruby

Допустим, Алекс посещает другую встречу, и вы хотите увеличить значение Алекса в хэше.

attendance[:alex] += 1

puts attendance
# {:sarah=>4, :chris=>6, :alex=>2}

Зацикливание На Хэшах Ruby

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

attendance.each { |key,value| attendance[key] += 1 }

Для этой цели нам нужен только ключ, поэтому вместо этого мы можем использовать метод each_key для хэша и выполнить следующее.

attendance.each_key { |key| attendance[key] += 1 }

puts attendance
# {:sarah=>5, :chris=>7, :alex=>3}

Хэш Ruby – это не то же самое, что хэширование или использование хэш-функции. Большинство языков программирования называют упорядоченную структуру данных пары ключ-значение “картой”, потому что она сопоставляет ключ со значением.

С другой стороны, хеширование – это концепция использования функции для получения целого числа из объекта. Вот как Java oracle обрабатывает хэширование:

Всякий раз, когда он вызывается для одного и того же объекта более одного раза во время выполнения приложения Java, метод hashCode должен последовательно возвращать одно и то же целое число.

Если два объекта равны в соответствии с методом equals(Object), то вызов метода hashCode для каждого из двух объектов должен привести к одному и тому же целочисленному результату.

Не требуется, чтобы, если два объекта неравны в соответствии с равенствами (java.lang. Object) метод, затем вызов метода hashCode для каждого из двух объектов должен приводить к различным целочисленным результатам. Однако программист должен знать, что получение различных целочисленных результатов для неодинаковых объектов может повысить производительность хэш-таблиц.

Это полезно, потому что вы можете создать так называемую “хэш-таблицу” для хранения данных. Если вы напишете достаточно хорошую функцию хеширования для набора данных, который вы хотите сохранить, то каждый объект будет хэширован в свое собственное “ведро”. Ваша хэш-таблица начнется с множества пустых мест в ней (null), и после ее заполнения все равно будет много нулей, но поскольку хэш-таблица по сути представляет собой массив, где каждый индекс представляет собой хэш-код (целое число, возвращаемое хэш-функцией), а элемент в каждом индексе – это элемент данных, то это означает, что вы можете получить доступ к данным во время выполнения массива, т.Е. постоянное время выполнения, в отличие от времени выполнения logN для двоичных деревьев поиска.

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

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

Юкихиро Мацумото, создатель Ruby, сказал, что название было унаследовано от Perl.

Ruby также имеет хэш-метод в классе Object. Это необходимо для переопределения, если вы переопределяете eql? метод при определении класса.

Важно, чтобы ключи карты образовывали набор. В Java вы действительно можете вызвать метод keySet() на карте, и он возвращает набор всех ключей. В ruby вы можете просто вызвать метод keys для хэша, и он вернет массив ключей. Важным фактом набора является то, что он не содержит дубликатов, и как идентифицируются дубликаты? Вы бы подумали, если бы eql? метод возвращает то же самое, тогда объекты равны, поэтому Ruby не будет добавлять объекты. Но посмотри на это…

class User
  attr_accessor :user_name

  def eql?(other)
    self.class == other.class && 
    self.user_name== other.user_name
  end

  alias :== eql?
end

u1 = User.new
u2 = User.new

u1.user_name = "rubyrocks"
u2.user_name = "rubyrocks"

user_map = {u1 => "premium", u2 => "premium"}

puts u1.hash
puts u2.hash
puts u1 == u2
puts user_map

# 3821538715194388951
# 2153368322350425775
# true
# {#=>"premium", #=>"premium"}

Это плохо, что у нас есть 2 “одинаковых” объекта на нашей карте.

Из docs.ruby-lang.org ,

Два объекта ссылаются на один и тот же хэш-ключ, когда их хэш-значение идентично и два объекта равны? друг к другу.

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

Типичная реализация hash основана на данных объекта, в то время как eql? обычно присваивается псевдоним переопределенному:

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

class User
  attr_accessor :user_name

  def eql?(other)
    self.class == other.class && 
    self.user_name== other.user_name
  end

  def hash
    user_name.hash
  end

  alias :== eql?
end

u1 = User.new
u2 = User.new

u1.user_name = "rubyrocks"
u2.user_name = "rubyrocks"

user_map = {u1 => "premium", u2 => "premium"}

puts u1.hash
puts u2.hash
puts u1 == u2
puts user_map

# -4215281874242322283
# -4215281874242322283
# true
# {#=>"premium"}

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

В JavaScript самая близкая вещь к хэшу Ruby называется “map”. Объекты в js в некотором роде похожи но поскольку их нелегко перебирать, и вы не можете вызывать всевозможные полезные вещи для таких объектов, как “размер”, я не думаю, что они являются претендентами. В Java также есть карты, но вы можете выбрать использование Hashmap или Treemap прямо из коробки.

Теперь давайте посмотрим, как мы сделали все эти хеш-функции Ruby выше, но в мире JavaScript

Создайте и инициализируйте карту в JavaScript

Согласно Mozilla использование оператора присваивания с картой не взаимодействует со структурой данных карты. Таким образом, нам нужно использовать картографические методы.

map_identifier =  new Map();

attendance =  new Map();

attendance.set("Sarah", 4);
attendance.set("Chris", 6);
attendance.set("Alex", 1);

console.log(attendance);
// {"Sarah" => 4, "Chris" => 6, "Alex" => 1}

Для короткого пути вы могли бы сделать:

let attendance = new Map([ ['Sarah', 4],['Chris', 6],['Alex', 1]]);

Зацикливание на карте в JavaScript

Давайте на этот раз увеличим посещаемость каждого на 2!

attendance.forEach((value, key, map) => {map.set(key , value + 2 )});
console.log(attendance);
// {"Sarah" => 6, "Chris" => 8, "Alex" => 3}

Посетите официальный сайт Mozilla, чтобы узнать больше о картах для каждого метода.

Оставьте комментарий, если вы хотите продемонстрировать эту функциональность на Python или любом другом языке, который вам нравится!

Счастливого кодирования!

Оригинал: “https://dev.to/computingtogether/demystifying-hashes-maps-and-hashing-8g”

Читайте ещё по теме: