1 Востаннє редагувалося leofun01 (11.03.2015 18:39:52)

Тема: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

Пишу клас натуральних чисел,

тут наведено частинку того чим він є і що він містить (C#):
public sealed class LargeInt : IEnumerable<byte>, IComparable<LargeInt>,
                            ICloneable<LargeInt>, IEquatable<LargeInt>
{
    // <= A.Length // Кількість елементів в масиві A
    public int Length { get; private set; }
    // >= Log(Length - 1) / Log(2) // Для нарізання масиву A
    public byte Log2 { get; private set; }
    // В цьому масиві зберігається саме число
    private byte[] A;

    public static LargeInt operator &(LargeInt l, LargeInt r) { return And(l, r); }
    public static LargeInt operator ^(LargeInt l, LargeInt r) { return Xor(l, r); }
    public static LargeInt operator |(LargeInt l, LargeInt r) { return Or(l, r); }
}

Але справа не в коді, а в тому як для такого класу перевизначити (override) метод GetHashCode(), тому пишу сюди.

Загальновідомо, що для функції GetHashCode мають виконуватися наступні умови:

  1. Два об'єкти X і Y, для яких X==Y або X.Equals(Y), мають генерувати хеші так, щоб X.GetHashCode()==Y.GetHashCode() (але загалом з рівності хешів не випливає рівність об'єктів);

  2. При заповненні об'єктів випадковими даними, хеші мають бути рівномірно розподілені по всій множині допустимих значень (для максимальної ефективності алгоритмів, які використовують хеші).

Іноді ще пишуть третє правило: 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).

Тепер питання:
Чи варто використовувати всі ці умови (&^|) ?
Які переваги можна отримати використовуючи всі умови ?
Які недоліки ?
І взагалі, мені цікава ваша думка по цій темі.

2 Востаннє редагувалося quez (11.03.2015 18:24:00)

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

Для виконання обох умов вистачить пере'xor'ити масив поелементно.

Ну а ваші додаткові умови... Хеші ж беруться не для цього.

Подякували: leofun011

3

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

А ще схоже що для такого метода ваші додаткові умови теж виконуються. Викладки покажу пізніше (або не покажу).

Подякували: leofun011

4

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

ось така штука добре працює (ну принаймні в java)

f^(f>>32)
Подякували: leofun011

5

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

Приблизно по такій схемі і робив. Брав по 4 байти і xor'ив весь масив.
Наприклад для масиву з 8 байт:
Hex: 97 5F A1 00 FF DF DC 48 => Hex: 975FA100 ^ FFDFDC48 => Hex: 68807D48 => Dec: 1753251144.
Але що це мені дало, або як це можна використати ?

6

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

leofun01 написав:

Приблизно по такій схемі і робив. Брав по 4 байти і xor'ив весь масив.
Наприклад для масиву з 8 байт:
Hex: 97 5F A1 00 FF DF DC 48 => Hex: 975FA100 ^ FFDFDC48 => Hex: 68807D48 => Dec: 1753251144.
Але що це мені дало, або як це можна використати ?

Ви точно знаєте, нащо потрібна ця функція?

7 Востаннє редагувалося leofun01 (14.03.2015 00:21:46)

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

Та про Hashtable і йому подібні я знаю, просто шукав нестандартне використання.

Ладно, цю тему можна відправити в смітник.

8

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

Якщо GetHashCode() завжди повертає 1, то ця вимога не виконується

(X ^ Y).GetHashCode() == X.GetHashCode() ^ Y.GetHashCode();
Подякували: leofun011

9

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

GetHashCode() не повинен завжди повертати одне значення, бо тоді не буде виконуватися умова 2 (... хеші мають бути рівномірно розподілені ...).

10

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

leofun01 написав:

GetHashCode() не повинен завжди повертати одне значення, бо тоді не буде виконуватися умова 2 (... хеші мають бути рівномірно розподілені ...).

ok, тоді нехай GetHashCode завжди повертає непарні числа.

11 Востаннє редагувалося Regen (15.03.2015 11:33:21)

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

Yola написав:
leofun01 написав:

GetHashCode() не повинен завжди повертати одне значення, бо тоді не буде виконуватися умова 2 (... хеші мають бути рівномірно розподілені ...).

ok, тоді нехай GetHashCode завжди повертає непарні числа.

лол, та почитайте статтю у Блоха, щоправда код жабівський, але принципи описані чітко
наприклад ось так обчислювати мож

result = 17;
result = result*31 + a; // a в цьому випадку поле int
return result;

якщо в тебе a 64 бітне то (точніше більше, ніж 32 бітне,
що значить, що діапазон значень більший, ніж від -2^31 до (2^31)-1)

result = result*31 + a^(a>>32);
Подякували: leofun011

12 Востаннє редагувалося Regen (15.03.2015 11:38:53)

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

leofun01 написав:

GetHashCode() не повинен завжди повертати одне значення, бо тоді не буде виконуватися умова 2 (... хеші мають бути рівномірно розподілені ...).

має бути мінімум колізій, бо це перетворить Hashtable в зв'язний список

Подякували: leofun011

13

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

Regen написав:
Yola написав:
leofun01 написав:

GetHashCode() не повинен завжди повертати одне значення, бо тоді не буде виконуватися умова 2 (... хеші мають бути рівномірно розподілені ...).

ok, тоді нехай GetHashCode завжди повертає непарні числа.

лол, та почитайте статтю у Блоха, щоправда код жабівський, але принципи описані чітко
наприклад ось так обчислювати мож

result = 17;
result = result*31 + a; // a в цьому випадку поле int
return result;

якщо в тебе a 64 бітне то (точніше більше, ніж 32 бітне,
що значить, що діапазон значень більший, ніж від -2^31 до (2^31)-1)

result = result*31 + a^(a>>32);

Я чекав, коли в цю тему принесуть Блоха. Навіть якось пізно.
Ви не подивились, про що тема, не подивились, до яких висновків ми тут дійшли, але готовий рецептик з книжки запостили.
В автора теми не 64-бітне число, а число будь-якої довжини. І хеш автор теми шукав так, як і ви Блох пропонує: ксорив восьмибітні частинки числа між собою.

Подякували: leofun011

14 Востаннє редагувалося Regen (15.03.2015 18:18:06)

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

quez написав:
Regen написав:
Yola написав:

ok, тоді нехай GetHashCode завжди повертає непарні числа.

лол, та почитайте статтю у Блоха, щоправда код жабівський, але принципи описані чітко
наприклад ось так обчислювати мож

result = 17;
result = result*31 + a; // a в цьому випадку поле int
return result;

якщо в тебе a 64 бітне то (точніше більше, ніж 32 бітне,
що значить, що діапазон значень більший, ніж від -2^31 до (2^31)-1)

result = result*31 + a^(a>>32);

Я чекав, коли в цю тему принесуть Блоха. Навіть якось пізно.
Ви не подивились, про що тема, не подивились, до яких висновків ми тут дійшли, але готовий рецептик з книжки запостили.
В автора теми не 64-бітне число, а число будь-якої довжини. І хеш автор теми шукав так, як і ви Блох пропонує: ксорив восьмибітні частинки числа між собою.

одразу я навів коротенький приклад для великих чисел, а другого разу весь, щось не правильно?
лол, я не знаю C# тому написав, як це робиться з великими числами у java та й у його коді я не розбирався через ту ж причину
по-вашому погано, що я "готовий рецептик" запостив? чи він по-вашому неправильний?
до того ж ви самі писали, чи знає leo нащо він(самі винні  :D )

15

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

quez написав:
Regen написав:
Yola написав:

ok, тоді нехай GetHashCode завжди повертає непарні числа.

лол, та почитайте статтю у Блоха, щоправда код жабівський, але принципи описані чітко
наприклад ось так обчислювати мож

result = 17;
result = result*31 + a; // a в цьому випадку поле int
return result;

якщо в тебе a 64 бітне то (точніше більше, ніж 32 бітне,
що значить, що діапазон значень більший, ніж від -2^31 до (2^31)-1)

result = result*31 + a^(a>>32);

Я чекав, коли в цю тему принесуть Блоха. Навіть якось пізно.
Ви не подивились, про що тема, не подивились, до яких висновків ми тут дійшли, але готовий рецептик з книжки запостили.
В автора теми не 64-бітне число, а число будь-якої довжини. І хеш автор теми шукав так, як і ви Блох пропонує: ксорив восьмибітні частинки числа між собою.

покажіть мені, де Блох пише про xor між восьмибітними частинами?

16

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

Regen написав:
quez написав:
Regen написав:

лол, та почитайте статтю у Блоха, щоправда код жабівський, але принципи описані чітко
наприклад ось так обчислювати мож

result = 17;
result = result*31 + a; // a в цьому випадку поле int
return result;

якщо в тебе a 64 бітне то (точніше більше, ніж 32 бітне,
що значить, що діапазон значень більший, ніж від -2^31 до (2^31)-1)

result = result*31 + a^(a>>32);

Я чекав, коли в цю тему принесуть Блоха. Навіть якось пізно.
Ви не подивились, про що тема, не подивились, до яких висновків ми тут дійшли, але готовий рецептик з книжки запостили.
В автора теми не 64-бітне число, а число будь-якої довжини. І хеш автор теми шукав так, як і ви Блох пропонує: ксорив восьмибітні частинки числа між собою.

покажіть мені, де Блох пише про xor між восьмибітними частинами?

В прикладі, який ви запостили, ви ксорите 32-бітні частини числа. Кількість біт непринципова, я думаю, ви це розумієте.

Прихований текст

А жалітись я буду вашій мамці.

17 Востаннє редагувалося Regen (15.03.2015 19:06:55)

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

quez написав:

В прикладі, який ви запостили, ви ксорите 32-бітні частини числа. Кількість біт непринципова, я думаю, ви це розумієте.

Прихований текст

А жалітись я буду вашій мамці.

та я навмання написав int, хоча його "ксорити" і не треба, це вже для типів більших, ніж int.
чому непринципово? час ж якийсь йде на xor і на зсув? на перфоманс ж впливає
може я щось неправильно пишу- то виправте мене

угу, звичайно ;), вирахуєте мене по ip

18

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

Regen написав:
quez написав:

В прикладі, який ви запостили, ви ксорите 32-бітні частини числа. Кількість біт непринципова, я думаю, ви це розумієте.

Прихований текст

А жалітись я буду вашій мамці.

та я навмання написав int, хоча його "ксорити" і не треба, це вже для типів більших, ніж int.
чому непринципово? час ж якийсь йде на xor і на зсув? на перфоманс ж впливає
може я щось неправильно пишу- то виправте мене

угу, звичайно ;), вирахуєте мене по ip

Я підозрюю, що 64-бітні числа в 64-бітних системах ксоряться так само швидко, як і будь-які менші.

Подякували: leofun011

19 Востаннє редагувалося Regen (15.03.2015 19:13:16)

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

quez написав:
Regen написав:
quez написав:

В прикладі, який ви запостили, ви ксорите 32-бітні частини числа. Кількість біт непринципова, я думаю, ви це розумієте.

Прихований текст

А жалітись я буду вашій мамці.

та я навмання написав int, хоча його "ксорити" і не треба, це вже для типів більших, ніж int.
чому непринципово? час ж якийсь йде на xor і на зсув? на перфоманс ж впливає
може я щось неправильно пишу- то виправте мене

угу, звичайно ;), вирахуєте мене по ip

Я підозрюю, що 64-бітні числа в 64-бітних системах ксоряться так само швидко, як і будь-які менші.

та, певно, правильно думаєте
а чи є потреба ксорити 32 бітні числа і менші?

20

Re: Як реалізувати GetHashCode() для класу великих натуральних чисел ?

Regen написав:

та, певно, правильно думаєте
а чи є потреба ксорити 32 бітні числа і менші?

Так в джаві (не знаю як в сішарпі) hashCode повертає int, що значить, що треба зробити 32-бітне число. А менші, мабуть, таки немає сенсу.

Подякували: leofun011