Основные понятия Хеширования

У меня есть очень простой вопрос. поверьте мне, я прочитал много книг, увидел видео, но не смог получить свой ответ. Предположим, у нас есть HashMap. У меня есть 3 (a, b, c) vales, которые сопоставляются с одним и тем же хэшем, a и b одинаковы, но c отличается. Если я добавлю только a и b в hastable, как hashMap знает, что это НЕ столкновение.Основные понятия Хеширования

Предположим, что у нас есть Hashmap .... Теперь я вызываю put (obj1, «Test»), а затем ставьте (obj2, «Test») obj1 и obj2 на тот же ключ ... Можете ли вы рассказать мне, какой хэш карта будет храниться для этих двух вызовов

Будет ли он хранить фактические объекты? Если нет, то как он примет решение о втором вызове, что он не является столкновением, если obj1 и obj2 одинаковы.

Благодаря

источник

2012-01-26 user973931

Потому что a и b одинаковы? –

Но, насколько я знаю, HashTable знает только о ключах, а не о действительных значениях ключей, то есть скажите a и b на карте k, я думаю, что hashtable знает только о k не a и b. Я ошибаюсь? – user973931

Если a и b идентичны, то это ** является ** столкновением. Вы хотели спросить, как это отличает a/b и * c *? В любом случае, ваш вопрос ** очень ** основной и был ответом раньше. – delnan

Большинство Hashtables требуют два бита поддержки со стороны ваших объектов хранения - GetHashCode() и Equals().

Если два объекта возвращают один и тот же GetHashCode(), но их сравнение с Equals() возвращает true, они представляют одни и те же данные и, таким образом, не являются столкновением, просто дублируют записи.

Если два объекта возвращают один и тот же GetHashCode(), а их сравнение возвращает false, то Hashtable знает, что объекты представляют разные вещи и, таким образом, рассматривает его как столкновение.

Именно поэтому во многих языках Oop, таких как C#, вам необходимо переопределить/реализовать GetHashCode() и Equals() в ваших объектах хранения. Если вы когда-либо реализуете эти методы, чтобы два объекта по сравнению с Equals() возвращали true, но возвращали разные значения из GetHashCode(), тогда у вас есть ошибка.

источник

2012-01-26 17:56:36 antiduh

Итак, вы говорите, что HashTable хранит фактические ключевые объекты ..... Я думал, что он сохраняет только значение. – user973931

@ user973931 Если он хранит только ключ, как бы он возвращал значение с учетом ключа? Конечно, это не могло. – delnan

@ delnan он вычислил бы хэш и вернул бы значение по индексу – user973931

Согласно Википедии:

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

Также Wiki сказал ассоциативный массив как «абстрактный тип данных, состоящий из набора пар (ключ, значение)».

Итак, хэш-стол действительно знает своих «арендаторов».

источник

2012-01-26 17:57:20

Итак, если я использую HashTable .. Сколько памяти ему нужно. Я думаю, что нужна память, это HashTable Size() * Целочисленный размер ... Если это правильно, где он хранит арендаторов – user973931

Основные понятия Хеширования

ответ

Смежные вопросы