Начин за съхраняване на ключове в речник без съхраняване на ключа?

Например, ако пишете клас речник, колизиите са редки, но съществуват. В резултат на това трябва да съхраните ключа, за да сте сигурни, че когато намерите своя ключ в хеш-таблицата, той е правилният и не е сблъсък.

Понякога ключовете са дълги и обикновено са низове, така че всеки ключ може да бъде над 40 байта, в сравнение с това, ако беше просто хеш код. Ами ако съхраненият ключ е хеширан обект, но използвайки малко по-различен алгоритъм за хеширане, с различни прости числа? Тогава шансовете за сблъсък биха били (1/(2^32)) * (1/(2^32)).

Можете дори да имате друг алгоритъм за хеширане и вместо това да съхранявате този хеш, така че шансовете за сблъсък биха били (1/(2^32)) * (1/(2^32)) * (1/(2^32)). Очевидно все още може да се случи сблъсък, но шансовете са толкова ниски и спестявате толкова много памет, като трябва да съхранявате само 4 байта за ключ вместо над 32 байта.

Предполагам, че това все още не е приемливо, нали, защото все още има ШАНС, но също така има шанс нечия RAM случайно да се преобърне малко и да стане син екран, а това изглежда толкова малко вероятно, че е изкушаващо да не се приложи. Има ли алтернативи или малкият шанс все пак не си струва?


dictionary c# algorithm hash hashcode
person John Smith    schedule 03.03.2015    source източник
comment
Смисълът на ключ в dictionary е, че имате известен уникален индексатор и искате да намерите стойността, съхранена в този индекс. Ако имате някакъв нестандартен хеш, който можете да получите само от самия обект, вероятно нямате нужда от речник, а само от списък.   -  person ps2goat    schedule 03.03.2015
comment
Ако вашият хеш е 32 бита, вероятността за сблъсък ще бъде доста по-висока от 1/2^32. И ще ви трябват 4 байта за всяка такава хеш функция, така че 12 байта за 3 от тях. Изобщо не е изключено да се случи с такива малки хешове, така че ако трябва абсолютно да избягвате сблъсъци, предлагам да спестите 40-те байта.   -  person IVlad    schedule 03.03.2015
comment
Вие също приемате перфектна хеш функция с идеално разпределена вероятност за всяка стойност, което всъщност никога не е така в действителност.   -  person Servy    schedule 03.03.2015
comment
Дори и да сте съхранили 6 хеша, всеки изчислен с различни прости числа, това все още е по-малко използвана памет от хеш на низов ключ и вероятностите за сблъсък ще бъдат близки до 1 към 10^50. Знам, че все още има шанс и хеширането не е перфектно, но изглежда изкушаващо..   -  person John Smith    schedule 03.03.2015
comment
Не, няма да е в 1 на 10^50. Откъде ги взимате тези числа? Би било много по-вероятно от това на практика, в зависимост от действителните алгоритми, използвани за хешовете.   -  person IVlad    schedule 03.03.2015
comment
Ето как работи HashSet.   -  person JNYRanger    schedule 03.03.2015
comment
@IVlad: Получавам числото от хеш, който е 32-битов отговор и с шест различни алгоритъма за хеширане, използвани на един и същ ключ, и всеки съхранен хеш е около (1/(2^32)) * (1/(2^32)) * (1/(2^32)) * (1/(2^32)) * (1/(2^32)) * (1/(2^32)) или 1.59 × 10^-58 Очевидно хеширането не е идеално еднакво, така че аз взе много порядъци, за да компенсира.   -  person John Smith    schedule 03.03.2015

Отговори (2)


arrow_upward
1
arrow_downward

Зависи.

Трябва ли абсолютно да гарантирате разрешаване на сблъсъци? Ако е така: трябва да съхраните ключа или нещо еквивалентно на него. В някои случаи (напр. малко пространство на ключове, излишни данни и т.н.) можете да използвате компресиране или персонализирани хеш функции за обратимо картографиране на ключа към нещо по-малко.

Ако не: да, вашият подход ще работи. Обърнете внимание, че поради парадокса на рождения ден, вероятността за сблъсък е:

  • в зависимост от броя на елементите, които вече са в колекцията; и
  • по-високо, отколкото си мислите.

Има компромис: сега трябва да изчислите (и сравните) няколко хеша, за да намерите елементи.

Следвайки по-нататък по този път: защо имаме фиксиран брой хешове? Можете да изчислите един хеш и да изчислите следващия само ако има сблъсък; това води до внедряване, базирано на trie. (Разбира се, тогава имате нужда от надеждно разпределено семейство от хеш функции...)

Повечето от тези неща са пресилени за всички, освен за повечето приложения с висока производителност и/или ограничена памет - но от време на време е полезно да правите неща като това :)

person candu    schedule 03.03.2015
comment
Опитите са интересни. Може да имам идея въз основа на това. - person John Smith; 04.03.2015

arrow_upward
2
arrow_downward

Ако искате да сте 100% сигурни, че няма сблъсък, няма начин да проверите за ключа преди вмъкване. Като се има предвид това, имаме късмет тук, защото добре внедреният речник е точно това, от което се нуждаете, за да намерите бързо ключ.

Като се има предвид това, може да искате да разгледате описаната функция тук. Шансовете за сблъсък ще бъдат доста ниски

РЕДАКТИРАНЕ: Премахнах някои глупости, които написах за GUID...

person Renaud Gauthier    schedule 03.03.2015
comment
Съгласен: GUID е много по-добра идея от ръчното комбиниране на кой знае какви хеш функции. - person IVlad; 03.03.2015
comment
Как бихте разбрали обаче, че ключът сочи към GUID? Няма асоциация. - person John Smith; 03.03.2015
comment
Прав си, тази част от отговора ми беше глупава непоправима. Твърдя, че вашите ключове се съхраняват de facto и са лесни за проверка. Нека редактирам това... - person Renaud Gauthier; 03.03.2015