मैं क्लोजर में एक ब्लूम फ़िल्टर बनाना चाहता हूं लेकिन मुझे सभी हैशिंग पुस्तकालयों का अधिक ज्ञान नहीं है जो JVM आधारित भाषाओं में उपलब्ध हो सकते हैं।क्लोजर में ब्लूम फ़िल्टर बनाने के दौरान उपयोग करने के लिए क्या हैशिंग तकनीकें?
क्लोजर में सबसे तेज़ (सबसे सटीक के विपरीत) ब्लूम मैप कार्यान्वयन के लिए मुझे क्या उपयोग करना चाहिए?
तो ब्लूम फ़िल्टर के बारे में मजेदार बात यह है कि प्रभावी ढंग से काम करने के लिए उन्हें कई हैश फ़ंक्शंस की आवश्यकता होती है।
जावा स्ट्रिंग्स में पहले से ही एक हैश फ़ंक्शन बनाया गया है जिसमें आप 32-बिट पूर्णांक हैश के साथ String.hashCode() का उपयोग कर सकते हैं। यह अधिकांश उद्देश्यों के लिए एक ठीक हैशकोड है, और यह संभव है कि यह पर्याप्त है: उदाहरण के लिए यदि आप इसे 2 अलग 16-बिट हैशकोड में विभाजित करते हैं तो यह आपके ब्लूम फ़िल्टर को काम करने के लिए पर्याप्त हो सकता है। आपको शायद कुछ टकराव मिलेगा लेकिन यह ठीक है - ब्लूम फिल्टर से कुछ टकराव होने की उम्मीद है।
यदि नहीं, तो आप शायद अपना खुद का रोल करना चाहेंगे, इस मामले में मैं कच्चे चार डेटा तक पहुंचने के लिए String.getChars() का उपयोग करने की सलाह दूंगा, फिर एकाधिक हैशकोड की गणना करने के लिए इसका उपयोग करें।
Clojure कोड आप आरंभ करने के लिए (सिर्फ चरित्र मूल्य जोड़कर):
(let [s "Hello"
n (count s)
cs (char-array n)]
(.getChars s 0 n cs 0)
(areduce cs i v 0 (+ v (int (aget cs i)))))
=> 500
नोट Clojure के जावा के उपयोग इंटरॉप getChars कॉल करने के लिए, और areduce के उपयोग आप एक बहुत तेजी से यात्रा से अधिक देने के लिए चरित्र सरणी
आप इस जावा ब्लूम फ़िल्टर कार्यान्वयन में रुचि भी ले सकते हैं जो मैंने गिथब पर पाया: https://github.com/MagnusS/Java-BloomFilter। हैशकोड कार्यान्वयन पहली नज़र में ठीक दिखता है लेकिन यह एक बाइट सरणी का उपयोग करता है जो मुझे लगता है कि चरित्र एन्कोडिंग ओवरहेड से निपटने की आवश्यकता के कारण वर्णों का उपयोग करने से थोड़ा कम कुशल है।
जावा में ब्लूम फ़िल्टर लिखने के बाद (प्रश्न JVM और हैशिंग एल्गोरिदम के बारे में था), कई हैश फ़ंक्शंस की आवश्यकता नहीं है। दरअसल (नीचे जवाब देखें), ब्लूम फ़िल्टर के लिए एक अच्छा मुमूर हैश क्योंकि उत्कृष्ट है क्योंकि वे बेहद तेज़ हैं और मामूली वृद्धि टकराव की घटनाओं में वृद्धि वास्तव में एक कारक नहीं है क्योंकि ब्लूम फ़िल्टरों के स्वाभाविक रूप से झूठी-सकारात्मक दर है।सेट में डेटा प्रकार भी प्रासंगिक नहीं है क्योंकि प्रदर्शन के लिए सर्वोत्तम अभ्यास और झूठी-सकारात्मक दर प्रबंधित करने के लिए इनपुट कुंजी को किसी भी तरह से सेट करके बिट-सेट वितरण को सुगम बनाना है। –
@ डेरेल - अच्छी तरह से आपको पर्याप्त स्वतंत्र रूप से गणना की गई * बिट्स * की आवश्यकता है कि आप परिणाम को कई हैश फ़ंक्शंस में विभाजित कर सकते हैं। नीचे दिया गया जवाब यही है - मैं इसे "कई हैश फ़ंक्शंस का उपयोग करके परिभाषित करता हूं" :-) – mikera
प्रश्न "हैशिंग पुस्तकालय जो जेवीएम आधारित भाषाओं के लिए उपलब्ध हो सकता है" के बारे में था, इसलिए टिप्पणी उन संख्याओं के संदर्भ में थी जो 'संख्या' बनाम थीं हैश बाल्टी 'का उपयोग/गणना की जाती है। मुझे लगता है कि वाक्यांश 'हैश फ़ंक्शन' का अर्थ एक फ़ंक्शन या विधि (कार्यान्वयन) है, जबकि नीचे दी गई टिप्पणियां 'हैंश की वांछित संख्या की गणना करती हैं'। किसी भी भ्रम के लिए खेद है लेकिन उम्मीद है कि यह नए उपयोगकर्ताओं के लिए स्पष्ट करता है क्योंकि यह एक बहुत भारी कंप्यूटर विज्ञान विषय है। –
Apache Cassandra में ब्लूम फ़िल्टर कार्यान्वयन पर नज़र डालें। यह बहुत तेज़ MurmurHash3 एल्गोरिदम का उपयोग करता है और हश की वांछित संख्या की गणना करने के विभिन्न तरीकों से दो हैंश (या उसी हैश के दो भाग, मुर्मूरशैश 2 के बजाय मुर्मूरशैश 3 में अपग्रेड करने के बाद) को जोड़ता है।
मिश्रित पीढ़ी दृष्टिकोण this paper
में वर्णित है और यहाँ कैसेंड्रा sourcecode से एक टुकड़ा है है:
long[] hash = MurmurHash.hash3_x64_128(b, b.position(), b.remaining(), 0L);
long hash1 = hash[0];
long hash2 = hash[1];
for (int i = 0; i < hashCount; ++i)
{
result[i] = Math.abs((hash1 + (long)i * hash2) % max);
}
भी देखें Bloomfilter and Cassandra = Why used and why hashed several times?
डेटा किस प्रकार अपनी चाबी कर रहे हैं? तार? बाइट सरणी? पूर्णांकों? UUIDs? – pmdj
मैं स्ट्रिंग्स – jdoig
के सेट के खिलाफ सदस्यता के लिए परीक्षण कर रहा हूं आप स्ट्रिंग पर 'हैश()' विधि द्वारा रिपोर्ट किए गए अंतर्निहित हैश मान में एक मिश्रण हैश फ़ंक्शन को बार-बार लागू करने का प्रयास कर सकते हैं, उदा। http://www.cris.com/~Ttwang/tech/inthash.htm जेनरेट किए गए मान बहुत दृढ़ता से सहसंबंधित हो सकते हैं, जो ब्लूम फ़िल्टर को अप्रभावी बना सकता है। एक दृष्टिकोण जिसे मैंने अतीत में उपयोग किया है, हैश फ़ंक्शन का उपयोग बहुत लंबे परिणाम के साथ करना है, जैसे कि SHA-256, और परिणाम को खंड में विभाजित करें। यह आपके उद्देश्यों के लिए बहुत धीमा हो सकता है। सबसे आसान हो सकता है कि 'स्ट्रिंग हैश फ़ंक्शन' के लिए Google खोज करें और इसके कुछ परिणाम लागू करें। – pmdj