अंक के सेट के लिए हैशकोड की गणना करने का सबसे अच्छा तरीका क्या है?

Question

मैं द्वि-आयामी बिंदुओं के सेट के लिए हैशकोड की गणना करने का सबसे अच्छा तरीका ढूंढ रहा हूं (ताकि मैं पॉशगन्स को हैशटेबल में स्टोर कर सकूं)।

ऐसा करने के कुछ स्पष्ट तरीके हैं, जैसे स्ट्रिंग और उसके हैशकोड में सभी बिंदु निर्देशांक को संयोजित करना, लेकिन यह बहुत धीमा होगा।

गति/टकराव स्पेक्ट्रम के दूसरे छोर पर, उदाहरण के लिए मैं सभी निर्देशांकों को जोड़ सकता हूं, जिसके परिणामस्वरूप बहुत तेज़ कोड होगा, लेकिन कई टकराव भी होंगे।

अंक के सेट के लिए हैशकोड की गणना करने का सबसे अच्छा तरीका क्या है?

क्या निर्देशांक पूर्णांक हैं (वास्तविक निर्देशांक बनाम) इष्टतम समाधान अलग है?

संपादित करें: मैं .NET का उपयोग कर रहा हूं इसलिए हैशकोड 32 बिट लंबा होना चाहिए।

Answer 1

इस नौकरी के लिए कोई इष्टतम तरीका नहीं है। यह सब इस बात पर निर्भर करता है कि आप कितने बड़े हैंश कर सकते हैं। आपको गति और प्रसार के बीच व्यापार करना है। ध्यान रखें कि इष्टतम समाधान जैसी कोई चीज नहीं है (यदि आपको बिल्कुल पता नहीं है कि आप क्या है?) कुछ मामलों में xor पर्याप्त अच्छा हो सकता है। उदाहरण के लिए

लें इस कोड

unsigned int JSHash(char* str, unsigned int len) 
{ 
    unsigned int hash = 1315423911; 
    unsigned int i = 0; 

    for(i = 0; i < len; str++, i++) 
    { 
     hash ^= ((hash << 5) + (*str) + (hash >> 2)); 
    } 

    return hash; 
} 
/* End Of JS Hash Function */ 

आपने कहा था कि अंक एक साथ agregating धीमा करने के लिए है। यदि आप ऊपरी कोड को ठीक करते हैं तो उसे किसी भी प्रकार की एजग्रेशन की आवश्यकता नहीं होती है, केवल ट्रॉट पास नहीं होती है (यदि आप पूर्णांक और फ्लोट्स का उपयोग नहीं कर रहे हैं तो आप शायद बदलावों को ठीक कर देंगे (< < और >> शिफ्ट ऑपरेशंस हैं जो एक साथ बिटवाई की तरह काम करता है घूर्णन) अपने डेटा प्रकार फिट करने के लिए। अन्य हैश फंक्शन यहाँ

की जांच: http://www.partow.net/programming/hashfunctions/

Answer 2

इष्टतम हैश गणना से आपकी आवश्यकताओं पर निर्भर है।

प्रदर्शन अधिक हैश टकराव की लागत पर आएगा।

क्या आपके पास किसी पर भी कठोर बाध्यता है? यह गणितीय विश्लेषण के लिए नीचे आ जाएगा कि प्रदर्शन के संदर्भ में हैश टकरावों का प्रत्येक प्रतिशत आपको कितना खर्च करेगा।

Answer 3

अपने डेटा सेट कोई मौका बहुभुज आम किनारों है सकते हैं, लेकिन नहीं अन्यथा ओवरलैप, आप केवल करने के लिए प्रत्येक बहुभुज में तीन अंक पर हैश करने के लिए की जरूरत में से एक ने तो टकराव से बचें।

संपादित करें: इसे पुनर्विचार करना, अवतल/उत्तल सीमाओं के साथ संभावित टकराव को चित्रित करना, यह आपके बहुभुज ओवरलैप भी है। - Sigh

अलास: जब उत्तल और अवतल मिलते हैं, तो यह हमेशा मुझे परेशानी में डाल देता है। :-P

Answer 4

इस पत्र

Lamdan and Wolfson. Geometric hashing: A general and efficient model-based recognition scheme. Computer Vision. (1988)

Answer 5

वैकल्पिक रूप से बाहर की जाँच करें, तो आप सिर्फ व्यक्तिगत अंक की हैश XOR कर सकते हैं।

return p1.GetHashCode()^p2.GetHashCode() 

वैसे भी मूल्य क्या होने जा रहे हैं इसके आधार पर। शायद उन्हें जोड़ सकते हैं।

Answer 6

यदि आप बहुभुज चाहते हैं जो घड़ी की दिशा और anticlockwise परिभाषित हैं, लेकिन अन्यथा बराबर, बराबर होना है, तो आपको एक canonicalization समारोह बनाना होगा। एक ऐसा फ़ंक्शन जो किसी भी बिंदु से और किसी भी क्रम में से शुरू होने वाले बहुभुज बिंदुओं को बराबर क्रम में अंक वापस कर देगा।

एक एल्गोरिथ्म है कि मैं के बारे में सोच सकते हैं अंक के सभी संभव दृश्यों की न्यूनतम मिल रहा है: (न्यूनतम y के साथ अंक के न्यूनतम एक्स के साथ अंक)

1. शीर्ष वाम-पंथी अंक के सेट का पता लगाएं, ये शुरुआती बिंदु हैं।
2. प्रत्येक प्रारंभिक बिंदु और प्रत्येक दिशा के लिए, क्रमशः दिए गए दिशा में जुड़े बिंदु जोड़ें और वर्तमान पुनरावृत्ति में शीर्ष-बाएं सबसे ऊपर वाले सभी को खत्म करें। रोकें जब केवल एक प्रारंभिक बिंदु, दिशा जोड़ी छोड़ी जाती है या जब एन -1 पुनरावृत्तियों को पूरा किया जाता है। यदि एक से अधिक शुरुआती बिंदु और दिशा शेष है, तो कोई भी चुनें - वे सभी आइसोमोर्फिक हैं।
3. मिली दिशा में मिले बिंदु से शुरू होने वाले बिंदुओं को पुन: क्रमबद्ध करें।

यह O (n^2) पूरी तरह से पतित बहुभुज के लिए बुरी से बुरी हालत है, लेकिन अपने बहुभुज अतिव्यापी अंक नहीं है, यह हे (एन), एक सुंदर छोटे निरंतर कारक के साथ।

कैनोलिकलाइज्ड ऑर्डर के साथ आप आसानी से समानता के लिए दो बहुभुजों की तुलना कर सकते हैं, केवल समानता के लिए अंक की तुलना करें। हैशकोड गणना भी तुच्छ है, किसी भी उचित मजबूत हैश संयोजन विधि का उपयोग करें।

int result = 0; 
foreach (var point in this.points) { 
    result = (result * 31 + point.X.GetHashCode()) * 31 + point.Y.GetHashCode(); 
} 

Answer 7

एक बहुत जल्दी (गणना करने के लिए) दक्षिणावर्त/काउंटर दक्षिणावर्त स्वतंत्रता पर वांछित गुण आप अंक की एक अच्छी तरह से परिभाषित आदेश खोजने पर निर्भर होना नहीं चाहते हैं के साथ हैश के लिए: उदाहरण के लिए।

यह आपके हैश को संचालन के लिए संचालन के लिए सीमित करता है। इसलिए हम संयोजन संचालन के दौरान अलग-अलग अभिविन्यास से स्वतंत्र किसी भी और सभी डेटा को रखना चाहते हैं।

यहाँ एक सरल उपाय है:

एक गठबंधन समारोह पूर्णांक मान लिया जाये -> पूर्णांक -> पूर्णांक जो साहचर्य निम्न में से कोई शुरू करने के लिए के साथ क्या होगा:

public static int combine(int h, int x) 
{ 
    return h * 31 + x; 
} 

public static int combine(int h, int x) 
{ 
    return h^x; 
} 

तो हम क्या कर सकते हैं निम्नलिखित:

public override int GetHashCode() 
{ 
    int x = 0; 
    int y = 0; 
    uint h = 0;  
    foreach (var point p in polgon) 
    { 
     x = combine(x, p.X); 
     y = combine(y, p.Y); 
     h++; 
    } 
    // simplified, unrolled Murmur2 hash for end stage 
    const uint m = 0x5bd1e995; 
    const int r = 24; 
    uint h = count; 
    uint k = ReinterpretInt32ToUInt32(x); 
    k *= m; 
    k ^= k >> r; 
    k *= m; 
    h *= m; 
    h ^= k; 
    k = ReinterpretInt32ToUInt32(y); 
    k *= m; 
    k ^= k >> r; 
    k *= m; 
    h *= m; 
    h ^= k; 
    // avalanche 
    h ^= h >> 13; 
    h *= m; 
    h ^= h >> 15; 
    return ReinterpretUInt32ToInt32(h); 
} 

इस पर निर्भर ऊपर आसान

कोड बनाने के लिए

public unsafe uint ReinterpretInt32ToUInt32(int i) 
{ 
    return *((uint*) (void*) &i); 
} 

public unsafe int ReinterpretUInt32ToInt32(uint u) 
{ 
    return *((int*) (void*) &u); 
} 

टक्कर से बचने के मामले में यह सबसे अच्छा हैश नहीं होगा लेकिन गणना करने के लिए बहुत तेज़ होना चाहिए और आपको अपनी आवश्यकताओं के लिए पर्याप्त मिल सकता है।