Какой алгоритм хеширования использует .net? А как насчет Java?

Question

Относительно HashTable (и последующих производных от него) кто-нибудь знает, какой алгоритм хэширования .net и Java используют?

Являются ли List и Dictionary прямыми потомками Hashtable?

Answer 1

Хеш-функция не встроена в хеш-таблицу; хеш-таблица вызывает метод для ключевого объекта для вычисления хеша. Таким образом, хеш-функция варьируется в зависимости от типа ключевого объекта.

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

Answer 2

Я ничего не знаю о .NET, но попытаюсь говорить за Java.

В Java хеш-код в конечном итоге представляет собой комбинацию кода, возвращаемого функцией hashCode () данного объекта, и вторичной хеш-функцией внутри класса HashMap / ConcurrentHashMap (интересно, что оба используют разные функции). Обратите внимание, что Hashtable и Dictionary (предшественники HashMap и AbstractMap) являются устаревшими классами. И список на самом деле просто «что-то еще».

Например, класс String создает хеш-код, многократно умножая текущий код на 31 и добавляя следующий символ. См. Мою статью о , как работает хеш-функция String , для получения дополнительной информации. Числа обычно используют "себя" в качестве хэш-кода; другие классы, например Прямоугольник, имеющий комбинацию полей, часто использует комбинацию метода String - умножение на небольшое простое число и добавление, но добавление различных значений поля. (Выбор простого числа означает, что вы вряд ли получите «случайные взаимодействия» между определенными значениями и шириной хеш-кода, поскольку они не делятся ни на что.)

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

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

Answer 3

При поиске того же самого ответа я нашел это в справочном источнике .net @ http://referencesource.microsoft.com.

     /*
      Implementation Notes:
      The generic Dictionary was copied from Hashtable's source - any bug 
      fixes here probably need to be made to the generic Dictionary as well.
      This Hashtable uses double hashing.  There are hashsize buckets in the 
      table, and each bucket can contain 0 or 1 element.  We a bit to mark
      whether there's been a collision when we inserted multiple elements
      (ie, an inserted item was hashed at least a second time and we probed 
      this bucket, but it was already in use).  Using the collision bit, we
      can terminate lookups & removes for elements that aren't in the hash
      table more quickly.  We steal the most significant bit from the hash code
      to store the collision bit.

      Our hash function is of the following form:

      h(key, n) = h1(key) + n*h2(key)

      where n is the number of times we've hit a collided bucket and rehashed
      (on this particular lookup).  Here are our hash functions:

      h1(key) = GetHash(key);  // default implementation calls key.GetHashCode();
      h2(key) = 1 + (((h1(key) >> 5) + 1) % (hashsize - 1));

      The h1 can return any number.  h2 must return a number between 1 and
      hashsize - 1 that is relatively prime to hashsize (not a problem if 
      hashsize is prime).  (Knuth's Art of Computer Programming, Vol. 3, p. 528-9)
      If this is true, then we are guaranteed to visit every bucket in exactly
      hashsize probes, since the least common multiple of hashsize and h2(key)
      will be hashsize * h2(key).  (This is the first number where adding h2 to
      h1 mod hashsize will be 0 and we will search the same bucket twice).

      We previously used a different h2(key, n) that was not constant.  That is a 
      horrifically bad idea, unless you can prove that series will never produce
      any identical numbers that overlap when you mod them by hashsize, for all
      subranges from i to i+hashsize, for all i.  It's not worth investigating,
      since there was no clear benefit from using that hash function, and it was
      broken.

      For efficiency reasons, we've implemented this by storing h1 and h2 in a 
      temporary, and setting a variable called seed equal to h1.  We do a probe,
      and if we collided, we simply add h2 to seed each time through the loop.

      A good test for h2() is to subclass Hashtable, provide your own implementation
      of GetHash() that returns a constant, then add many items to the hash table.
      Make sure Count equals the number of items you inserted.

      Note that when we remove an item from the hash table, we set the key
      equal to buckets, if there was a collision in this bucket.  Otherwise
      we'd either wipe out the collision bit, or we'd still have an item in
      the hash table.

       -- 
    */

Answer 4

Алгоритм HASHING - это алгоритм, используемый для определения хеш-кода элемента в HashTable.

Алгоритм HASHTABLE (который, я думаю, задает этот человек) - это алгоритм, который HashTable использует для организации своих элементов с учетом их хэш-кода.

Java использует алгоритм цепочки хеш-таблиц .

Answer 5

.NET Dictionary<T> класс использует IEqualityComparer<T> для вычисления хеш-кодов для ключей и для сравнения ключей с целью поиска хеш-кодов. Если вы не предоставите IEqualityComparer<T> при создании экземпляра Dictionary<T> (это необязательный аргумент для конструктора), он создаст для вас экземпляр по умолчанию, который по умолчанию использует методы object.GetHashCode и object.Equals.

Что касается работы стандартной реализации GetHashCode, я не уверен, что она задокументирована. Для определенных типов вы можете прочитать исходный код метода в Reflector или попробовать проверить исходный код Rotor, чтобы увидеть, есть ли он там.

Answer 6

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

Answer 7

Все, что подразумевается как HashTable или что-то подобное в .NET, не реализует свой собственный алгоритм хеширования: они всегда вызывают метод GetHashCode() хеширования объекта.

Существует много путаницы относительно того, что этот метод делает или должен делать, особенно когда речь идет о пользовательских или других пользовательских классах, которые переопределяют реализацию базового объекта .