هل من الممكن دمج رموز التجزئة للأعضاء الخاصين لإنشاء رمز تجزئة جديد؟

Question

لدي كائن أرغب في إنشاء تجزئة فريدة له (تجاوز GetHashCode()) ولكني أريد تجنب التجاوزات أو أي شيء لا يمكن التنبؤ به.

يجب أن يكون الكود نتيجة لدمج رموز التجزئة لمجموعة صغيرة من السلاسل.

ستكون رموز التجزئة جزءًا من إنشاء مفتاح ذاكرة التخزين المؤقت، لذلك يجب أن تكون فريدة من نوعها بشكل مثالي ولكن عدد القيم المحتملة التي يتم تجزئتها صغير لذا أعتقد أن الاحتمالية في صالحي هنا.

هل سيكون شيء كهذا كافيًا وهل هناك طريقة أفضل للقيام بذلك؟

int hash = 0;
foreach(string item in collection){
    hash += (item.GetHashCode() / collection.Count)
}
return hash;

يحرر:شكرا على الإجابات حتى الآن.@ جون سكيت:لا، النظام ليس مهما

أعتقد أن هذا سؤال آخر تقريبًا ولكن بما أنني أستخدم النتيجة لإنشاء مفتاح ذاكرة تخزين مؤقت (سلسلة) فهل سيكون من المنطقي استخدام وظيفة تجزئة التشفير مثل MD5 أو مجرد استخدام تمثيل السلسلة لهذا int؟

Answer 1

وأساسيات أشار مارك وجون ليست سيئة لكنها بعيدة كل البعد عن المستوى الأمثل من حيث التوزيع المتساوي على توزيع النتائج. للأسف 'ضرب من قبل يعبي "نهج نسخها من قبل الكثير من الناس من كانوث هو href="http://www.codeproject.com/KB/recipes/hash_functions.aspx" يست هي الخيار الأفضل في كثير من الحالات توزيع أفضل يمكن أن يتحقق عن طريق أرخص لحساب وظائف (رغم أن هذا هو جدا طفيف على الأجهزة الحديثة). في الواقع رمي يعبي في جوانب كثيرة من التجزئة هو href="http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth" يست علاجا .

وإذا تم استخدام هذه البيانات للجداول التجزئة الحجم بشكل ملحوظ أوصي قراءة الدراسة بريت مولفي الممتازة والتفسير مختلف التقنيات الحديثة (ويست حديثة جدا) تجزئة القيام به بسهولة مع c #.

لاحظ أن السلوك مع سلاسل من مختلف المهام التجزئة منحازة بشكل كبير نحو wehther هي سلاسل قصيرة (تحدث تقريبا عدد الحروف وتجزئته قبل أن تبدأ بت إلى أكثر من التدفق) أو طويلة.

واحد من أبسط وأسهل وسيلة لتنفيذ هي أيضا واحدة من أفضل وجنكينز واحدة في تجزئة الوقت.

private static unsafe void Hash(byte* d, int len, ref uint h)
{
    for (int i = 0; i < len; i++)
    {
        h += d[i];
        h += (h << 10);
        h ^= (h >> 6);
    }
}

public unsafe static void Hash(ref uint h, string s)
{
    fixed (char* c = s)            
    {
        byte* b = (byte*)(void*)c;
        Hash(b, s.Length * 2, ref h);
    }
}

public unsafe static int Avalanche(uint h)
{
    h += (h<< 3);   
    h ^= (h>> 11);  
    h += (h<< 15);  
    return *((int*)(void*)&h);
}

ويمكنك بعد ذلك استخدام هذا مثل ذلك:

uint h = 0;
foreach(string item in collection) 
{
    Hash(ref h, item);
}
return Avalanche(h);

ويمكنك دمج عدة أنواع مختلفة مثل ذلك:

public unsafe static void Hash(ref uint h, int data)
{ 
    byte* d = (byte*)(void*)&data;
    AddToHash(d, sizeof(int), ref h);
}

public unsafe static void Hash(ref uint h, long data)
{ 
    byte* d= (byte*)(void*)&data;
    Hash(d, sizeof(long), ref h);
}

إذا كان لديك فقط الوصول إلى أرض الملعب كائن بدون معرفة الأجزاء الداخلية يمكنك ببساطة الاتصال GetHashCode () على كل واحد والجمع بين تلك القيمة مثل ذلك:

uint h = 0;
foreach(var item in collection) 
{
    Hash(ref h, item.GetHashCode());
}
return Avalanche(h);

للأسف لا يمكنك أن تفعل sizeof (T) لذلك يجب عليك أن تفعل كل بنية على حدة.

إذا كنت ترغب في استخدام انعكاس يمكنك بناء على أساس لكل نوع وظيفة التي لا هوية الهيكلية وتجزئة في كافة المجالات.

إذا كنت ترغب في تجنب كود غير آمن ثم يمكنك استخدام تقنيات قليلا اخفاء لسحب بت الفردية من [إينتس] (وحرف إذا التعامل مع السلاسل) مع عدم الكثير من المتاعب إضافية.

Answer 2

وتجزئات ليست <م> يعني لتكون فريدة من نوعها - انهم يعني فقط ليتم توزيعها بشكل جيد في معظم الحالات. انهم مجرد المفترض أن تكون متسقة. لاحظ أن تجاوزات لا ينبغي أن يكون مشكلة.

وفقط مضيفا ليس بشكل عام فكرة جيدة، وتقسيم بالتأكيد ليست كذلك. ها هي نهج وعادة ما تستخدم:

int result = 17;
foreach (string item in collection)
{
    result = result * 31 + item.GetHashCode();
}
return result;

إذا كنت على خلاف ذلك في سياق فحص، قد كنت تريد أن تجعل عمدا دون رادع.

لاحظ أن هذا يفترض أن النظام هو المهم، أي أن { "أ"، "ب"} يجب أن تكون مختلفة عن { "ب"، "أ"}. واسمحوا لنا أن نعرف إذا كان هذا ليس هو الحال.

Answer 3

لا حرج في هذا النهج طالما أن الأعضاء الذين تجمع رموز التجزئة الخاصة بهم يتبعون قواعد رموز التجزئة.باختصار ...

1. يجب ألا يتغير رمز التجزئة للأعضاء الخاصين طوال عمر الكائن
2. يجب ألا تقوم الحاوية بتغيير الكائن الذي يشير إليه الأعضاء الخاصون لئلا يقوم بدوره بتغيير رمز التجزئة الخاص بالحاوية

Answer 4

وإذا كان ترتيب العناصر ليست مهمة (أي { "أ"، "ب"} هي نفسها { "ب"، "أ"}) ثم يمكنك استخدام الحصري أو الجمع بين رموز التجزئة:

hash ^= item.GetHashCode();

[تحرير: وكما أشار الأقسام في تعليق على إجابة مختلفة، وهذا له عيب أيضا إعطاء مجموعات مثل { "أ"} و { "أ"، "ب"، "ب"} نفس رمز التجزئة .]

إذا كان النظام هو المهم، يمكنك مضاعفة بدلا من عدد الوزراء وإضافة:

hash *= 11;
hash += item.GetHashCode();

و(عندما كنت اضرب لك سوف تحصل أحيانا تجاوز أن يتم تجاهل، ولكن عن طريق ضرب مع عدد أولي تفقد الحد الأدنى من المعلومات. إذا كنت بدلا مضروبة بعدد مثل 16، سوف تخسر أربعة أجزاء من المعلومات في كل مرة ، وذلك بعد ثمانية بنود قانون التجزئة من البند الأول أن يكون قد انتهى تماما.)