Хэш-код. Как это использовать

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 в качестве хеш-кода, и у вас будет тот редкий идеальный хеш-код, где каждый объект отображается точно на один хеш-код.

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

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

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

Для набора чисел с несколькими отверстиями вы можете создать простой логический массив. Если a [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

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

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

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

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

Answer 3

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

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

Если вы используете Java, проверьте hashtable и посмотрите, достаточно ли методов для вашего приложения:

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