HashCode. Как использовать его

Question

Хотя я очень хорошо понимаю, что такое HashCode и что делает хэш-таблица, я должен признать, что я не знаю, как его использовать (Помимо обычного словаря). Я хотел бы реализовать свой собственный Hash Table поэтому сначала я хочу знать самые основные о Hash:

• Я знаю, что я могу получить хэш-код с getHashCode()/hashCode() в Java и Scala. Как определяется это число. (Просто из любопытства)
• Если я знаю HashCode объекта, как я могу его получить? То есть, как я могу назвать это ведро памяти?
• Могу ли я изменить/установить переменные HashCode?

Теперь у меня есть очень большой (около 10^9) список Int. Я собираюсь получить доступ к некоторым из них (от всех к каждому), и мне нужно сделать это как можно быстрее. Является ли хэш-таблица ЛУЧШИМ способом сделать это?

PS: Я не хочу обсуждать это, я просто хочу знать, является ли HashTable знанием, чтобы быть наиболее эффективным. Если есть другие хорошие методы, возможно, вы можете указать мне их.

Спасибо,

Answer 1

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

Это означает, что возврат «0» для каждого вызова хеш-кода будет действительным, но самопровозглашенным. Дело в том, что они могут (и в большинстве случаев) дублироваться.

Если вы знаете хэш-код объекта, вы не можете получить к нему доступ. в моем примере выше, если все объекты возвратили «0», вы все равно не могли спросить, у какого объекта есть хеш-код 0. Однако вы можете запросить ВСЕ объекты с хэш-кодом 0 и просмотреть их (это то, что делает хэш-таблица, он уменьшает количество итераций, получая только те, у которых один и тот же хеш-код, а затем просматривает их).

Если вы хотите установить (изменить) HashCode, это не будет хеш-код, потому что значение, заданное для объекта с заданным «состоянием», не может измениться.

Что касается «Наилучшего пути» для этого, чем меньше уникальных объектов, возвращающих один и тот же хеш-код, тем лучше будут работать ваши хэш-таблицы. Если у вас длинный список «int», вы можете просто использовать это значение int как свой хеш-код, и у вас будет этот редкий идеальный хеш - каждый объект сопоставляется с одним хэш-кодом.

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

Проблема с вашим «списком Int» заключается в том, что если у вас есть номер 5, и вы хотите найти его в своей таблице, вы просто найдете там номер 5.

Теперь, если вы хотите узнать, существует ли номер 5 в вашей таблице или нет, это другое дело.

Для набора чисел с небольшим количеством отверстий вы можете создать простой булевой массив. Если существует [5] (истинно), то a находится в списке.Если ваш набор чисел очень разрежен (1, 5, 10002930304), тогда это не будет очень хорошим решением, так как вы будете хранить «False» в точках 2, 3, 4, а затем целую кучу из них до последнего число, но это прямой поиск, единственный шаг, который никогда не берет больше, независимо от того, сколько чисел вы добавляете - O (1).

Вы можете сделать этот тип хранения МНОГО плотнее, сделав его двоичным поиском в массив байтов, но если вы не очень хорошо разбираетесь в манипуляции с битами, пропустите его. Это будет включать в себя материал, который выглядит примерно так:

public boolean doesNumberExist(int number) { 
    return bytes[number/8] & (1 << number % 8); 
} 

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

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

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

Answer 2

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

Для вашей программы вам действительно нужно выяснить, как вам нужно получить доступ к элементам. Хеш предлагает супер быстрый доступ к конкретному пункту, но не (не) предлагает последовательный доступ

Если вы используете Java, проверить хэш-таблицу и посмотреть, если методы являются достаточными для применения:

http://java.sun.com/j2se/1.4.2/docs/api/java/util/Hashtable.html

Answer 3

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

В этом случае, java.util.HashTable не лучше, чем java.util.ArrayList. A HashTable будет потреблять по меньшей мере вдвое больше памяти, предлагая немного более медленный доступ.

Даже лучше, чем ArrayList, является простой int[], так как не нужно создавать и сохранять никакие экземпляры Integer. По моим оценкам, это уменьшит потребление памяти в 3 раза.

Однако сохранение 10^9 int в памяти остается сложным предложением, так как каждый int потребляет 4 байта памяти. Это 4 ГБ. Возможно, вы захотите сохранить хотя бы часть списка, хранящегося на диске, а не памяти, и использовать, например, RandomAccessFile для поиска индекса, который просматривается.