منطق رمز القوة الجوافة يحتوي على

Question

كنت أتصفح كود مكتبة Guava، وكنت مهتمًا بفهم رمز المطابقة الاحتمالية لـ mayContain.هل يمكن لأي أحد أن يشرح ما يفعلونه في الكود خاصة مع عامل التشغيل الحكيم.هنا الكود....

public <T> boolean mightContain(T object, Funnel<? super T> funnel,
        int numHashFunctions, BitArray bits) {
      long hash64 = Hashing.murmur3_128().newHasher().putObject(object, funnel).hash().asLong();
      int hash1 = (int) hash64;
      int hash2 = (int) (hash64 >>> 32);
      for (int i = 1; i <= numHashFunctions; i++) {
        int nextHash = hash1 + i * hash2;
        if (nextHash < 0) {
          nextHash = ~nextHash;
        }
        // up to here, the code is identical with the previous method
        if (!bits.get(nextHash % bits.size())) {
          return false;
        }

Answer 1

بافتراض أن هذا رمز من Bloomfilter الطبقة، المنطق يذهب مثل هذا:

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

إذا تم العثور على جميع البتات التي تم ضبطها، فلا يمكننا إلا أن نقول أن المرشح قد تمت إضافة المفتاح.وذلك لأنه من الممكن أن يؤدي مفتاح مختلف (أو مجموعة من عدد من المفاتيح المختلفة) إلى تعيين كافة البتات المحددة.

لاحظ أن إضافة مفتاح إلى المرشح يؤدي نفس الوظيفة تقريبًا باستثناء أنه **يضبط** جميع البتات التي تم إنشاؤها.

أ مرشح بلوم الكائن يعمل على النحو التالي.

1. أ رقم يتم اختيار عدد من وظائف التجزئة، وسيقوم كل منها بحساب موقع البت في الفلتر.(يرى العدد الأمثل لوظائف التجزئة للمناقشة حول كم).
2. احتفظ بنمط البتات ذات الطول التعسفي - الطول غير مهم ولكن ينبغي أن يكون كذلك كبيرة بما يكفي (يرى احتمال ايجابيات كاذبة للمناقشة حول ماذا كبيرة بما يكفي وسائل).
3. في كل مرة تتم إضافة مفتاح إلى المرشح، يتم تنفيذ جميع وظائف التجزئة التي تم تكوينها على المفتاح مما يؤدي إلى تعيين عدد من البتات في النمط.
4. للتحقق مما إذا كان قد تمت إضافة مفتاح بالفعل، قم بتنفيذ جميع وظائف التجزئة وتحقق من البت الموجود هناك.إذا وجد أن أي منها صفر، فهذا المفتاح بالتأكيد لم تتم إضافته إلى عامل التصفية.
5. إذا تم العثور على جميع البتات التي تم ضبطها، فسيتم ذلك ربما أنه تمت إضافة هذا المفتاح.سوف تحتاج إلى إجراء المزيد من الفحوصات للتأكيد.

Answer 2

لا يوجد سوى عاملين اثنين فقط هنا: >>> و ~.

ال >>> هو عامل التشغيل "التحول الصحيح، لا تحمل بت الإشارة".في Java، بشكل افتراضي، إذا قمت بالتحويل:

1000 1100

الحق بمقدار 3 (باستخدام >>) سوف تحصل على:

1111 0001

استخدام >>> الذي لا يحمل علامة التوقيع سوف تحصل على:

0001 0001

الثاني (~) هو نفي البت، وهي طريقة بسيطة للحصول على رقم موجب من رقم سالب، ويبدو أنهم يريدون أرقامًا موجبة هنا (ربما فهرس مصفوفة متفرقة؟).تطبيق هذا العامل على:

1100 1010

وهو أمر سلبي byte في جافا سوف تسفر عن:

0011 0101

وهو أمر إيجابي.

في الأساس، ما يفعله هذا الرمز هو إنشاء تجزئة للكائن باستخدام وظيفة تجزئة سريعة، استخدمها للتداول عبر BitArray (ليس لدي أي فكرة عما هو - هيكل داخلي ل BloomFilter ربما)، وتأكد من عدم وجودها إذا لم تكن التجزئة موجودة في وقت ما BitArray.

أشك في BitArray يتم تحديثه في كل مرة تقوم فيها بإضافة إلى BloomFilter (استخدام .put(), ، أو .putAll()).