Тема: Як реалізувати GetHashCode() для класу великих натуральних чисел ?
Пишу клас натуральних чисел,
Загальновідомо, що для функції GetHashCode мають виконуватися наступні умови:
Два об'єкти X і Y, для яких X==Y або X.Equals(Y), мають генерувати хеші так, щоб X.GetHashCode()==Y.GetHashCode() (але загалом з рівності хешів не випливає рівність об'єктів);
При заповненні об'єктів випадковими даними, хеші мають бути рівномірно розподілені по всій множині допустимих значень (для максимальної ефективності алгоритмів, які використовують хеші).
Іноді ще пишуть третє правило: X.GetHashCode має повертати однакове значення доки в об'єкті не відбулися зміни, які впливають на роботу X.Equals(Y). Але як на мене, це просто наслідок з п.1.
Керуючись лише цими правилами я зробив метод, який працює за час O(n), де n=Length.
Оператори &, ^, | для пари (X, Y) виконують відповідні операції над елементами їх масивів (X.A[ i ], Y.A[ i ]).
І я задумався, ¿ чи можна визначити GetHashCode так, щоб не порушувалися попередні умови і виконувалися наступні:
(X & Y).GetHashCode() == X.GetHashCode() & Y.GetHashCode(); // 1
(X ^ Y).GetHashCode() == X.GetHashCode() ^ Y.GetHashCode(); // 2
(X | Y).GetHashCode() == X.GetHashCode() | Y.GetHashCode(); // 3І як це вплине на час виконання методу ?
Виявилося що можна і час виконання залишиться O(n).
Тепер питання:
Чи варто використовувати всі ці умови (&^|) ?
Які переваги можна отримати використовуючи всі умови ?
Які недоліки ?
І взагалі, мені цікава ваша думка по цій темі.
)
, вирахуєте мене по ip