لماذا لا تسمح للواجهة الخارجية بتوفير رمز التجزئة/يساوي لـ HashMap؟

Question

مع TreeMap من التافه تقديم العرف Comparator, ، وبالتالي تجاوز الدلالات التي تقدمها Comparable الكائنات المضافة إلى الخريطة. HashMapولكن لا يمكن السيطرة عليها بهذه الطريقة؛لا يمكن تحميل الوظائف التي توفر قيم التجزئة وعمليات التحقق من المساواة "جانبيًا".

أظن أنه سيكون من السهل والمفيد تصميم واجهة وتحديثها HashMap (أو فئة جديدة)؟شيء من هذا القبيل، إلا مع أسماء أفضل:

  interface Hasharator<T> {
    int alternativeHashCode(T t);
    boolean alternativeEquals(T t1, T t2);
  }

  class HasharatorMap<K, V> {
    HasharatorMap(Hasharator<? super K> hasharator) { ... }
  }

  class HasharatorSet<T> {
    HasharatorSet(Hasharator<? super T> hasharator) { ... }
  }

ال حالة الأحرف Map المشكلة تحصل على حل تافه:

 new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY);

هل سيكون هذا ممكنًا، أو هل يمكنك رؤية أي مشاكل أساسية في هذا النهج؟

هل يتم استخدام هذا النهج في أي مكتبات موجودة (غير JRE)؟(حاولت جوجل، لم يحالفني الحظ.)

يحرر:حل بديل جميل قدمه hazzen، لكن أخشى أن هذا هو الحل البديل الذي أحاول تجنبه...;)

يحرر:تم تغيير العنوان بحيث لم يعد يذكر "المقارن"؛أظن أن هذا كان مربكًا بعض الشيء.

يحرر:الإجابة المقبولة فيما يتعلق بالأداء؛أحب إجابة أكثر تحديدا!

يحرر:هناك تنفيذ؛انظر الإجابة المقبولة أدناه.

يحرر:أعيد صياغة الجملة الأولى للإشارة بشكل أكثر وضوحًا إلى أن هذا هو التحميل الجانبي الذي أسعى إليه (وليس الطلب؛الطلب لا ينتمي إلى HashMap).

Answer 1

Trove4j لديه ميزة أنا بعد ويسمونه تجزئة الاستراتيجيات.

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

Answer 2

وA متأخرا بعض الشيء بالنسبة لك، ولكن للزوار في المستقبل، قد يكون من المفيد معرفة أن المشاعات-مجموعات لديها AbstractHashedMap (في <لأ href = "https://commons.apache.org/proper/commons-collections/javadocs /api-3.2.2/org/apache/commons/collections/map/AbstractHashedMap.html "يختلط =" نوفولو noreferrer "> 3.2.2 و مع الأدوية في <لأ href =" HTTPS: // العموم. apache.org/proper/commons-collections/javadocs/api-4.0/org/apache/commons/collections4/map/AbstractHashedMap.html "يختلط =" نوفولو noreferrer "> 4.0 ). يمكنك تجاوز هذه الأساليب المحمية لتحقيق السلوك المطلوب:

protected int hash(Object key) { ... }
protected boolean isEqualKey(Object key1, Object key2) { ... }
protected boolean isEqualValue(Object value1, Object value2) { ... }
protected HashEntry createEntry(
    HashEntry next, int hashCode, Object key, Object value) { ... }

مثال لتنفيذ مثل هذا HashedMap البديل هو IdentityMap المشاعات-مجموعات "الخاصة (فقط ما يصل الى <وأ href =" https://commons.apache.org/proper/commons-collections/javadocs/api-3.2.2 /org/apache/commons/collections/map/IdentityMap.html "يختلط =" نوفولو noreferrer "> 3.2.2 كما فعلت جافا <لأ href =" https://docs.oracle.com/javase/8 /docs/api/java/util/IdentityHashMap.html "يختلط =" نوفولو noreferrer "> تلقاء نفسها منذ 1.4).

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

Answer 3

و. NET لديه هذا عبر IEqualityComparer (لنوع والتي يمكن مقارنتها كائنين) وIEquatable (لنوع الذي يمكن أن تقارن نفسها إلى حالة أخرى).

في الواقع، وأعتقد أنه كان من الخطأ تحديد المساواة وhashcodes في java.lang.Object أو System.Object على الإطلاق. المساواة على وجه الخصوص من الصعب تحديد بطريقة المنطقي مع الميراث. وأظل معنى لبلوق عن هذا ...

ولكن نعم، في الأساس فكرة سليمة.

Answer 4

استراتيجية التجزئة هو المفهوم الذي تبحث عنه.إنها واجهة إستراتيجية تسمح لك بتحديد التطبيقات المخصصة للمساواة ورمز التجزئة.

public interface HashingStrategy<E>
{
    int computeHashCode(E object);
    boolean equals(E object1, E object2);
}

لا يمكنك استخدام أ HashingStrategy مع المدمج في HashSet أو HashMap. مجموعات جي إس يتضمن Java.util.Set يسمى UnifiedSetWithHashingStrategy وتم استدعاء java.util.Map UnifiedMapWithHashingStrategy.

لنلقي نظرة على مثال.

public class Data
{
    private final int id;

    public Data(int id)
    {
        this.id = id;
    }

    public int getId()
    {
        return id;
    }

    // No equals or hashcode
}

إليك كيفية إعداد ملف UnifiedSetWithHashingStrategy واستخدامها.

java.util.Set<Data> set =
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(Data::getId));
Assert.assertTrue(set.add(new Data(1)));

// contains returns true even without hashcode and equals
Assert.assertTrue(set.contains(new Data(1)));

// Second call to add() doesn't do anything and returns false
Assert.assertFalse(set.add(new Data(1)));

لماذا لا تستخدم فقط أ Map? UnifiedSetWithHashingStrategy يستخدم نصف ذاكرة أ UnifiedMap, ، وربع ذكرى أ HashMap.وفي بعض الأحيان لا يكون لديك مفتاح مناسب ويتعين عليك إنشاء مفتاح اصطناعي، مثل الصف.يمكن أن يؤدي ذلك إلى إضاعة المزيد من الذاكرة.

كيف نقوم بعمليات البحث؟تذكر أن مجموعات لديها contains(), ، لكن لا get(). UnifiedSetWithHashingStrategy ينفذ Pool بالإضافة إلى Set, ، لذلك فهو ينفذ أيضًا شكلاً من أشكال get().

فيما يلي طريقة بسيطة للتعامل مع السلاسل غير الحساسة لحالة الأحرف.

UnifiedSetWithHashingStrategy<String> set = 
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(String::toLowerCase));
set.add("ABC");
Assert.assertTrue(set.contains("ABC"));
Assert.assertTrue(set.contains("abc"));
Assert.assertFalse(set.contains("def"));
Assert.assertEquals("ABC", set.get("aBc"));

يُظهر هذا واجهة برمجة التطبيقات (API)، ولكنه غير مناسب للإنتاج.المشكلة هي أن HashingStrategy تقوم بتفويضها باستمرار String.toLowerCase() مما يخلق مجموعة من سلاسل القمامة.إليك كيفية إنشاء إستراتيجية تجزئة فعالة للسلاسل غير الحساسة لحالة الأحرف.

public static final HashingStrategy<String> CASE_INSENSITIVE =
  new HashingStrategy<String>()
  {
    @Override
    public int computeHashCode(String string)
    {
      int hashCode = 0;
      for (int i = 0; i < string.length(); i++)
      {
        hashCode = 31 * hashCode + Character.toLowerCase(string.charAt(i));
      }
      return hashCode;
    }

    @Override
    public boolean equals(String string1, String string2)
    {
      return string1.equalsIgnoreCase(string2);
    }
  };

ملحوظة: أنا مطور في مجموعات GS.

Answer 5

ملحوظة: كما لوحظ في جميع إجابات أخرى، HashMaps لم يكن لديك طلب صريح. أنها تعترف فقط "المساواة". الحصول على أمر من بنية بيانات القائم على التجزئة لا معنى له، كما تم تشغيل كل كائن في تجزئة - أساسا على رقم عشوائي

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

مع كل ما يقال، إذا كنت ترغب فقط التجزئة لتجاهل حالة String، يمكنك كتابة فئة التفاف حول String لهذا الغرض وإدراج تلك الموجودة في بنية البيانات الخاصة بك بدلا من ذلك.

ووتنفيذ بسيط:

public class LowerStringWrapper {
    public LowerStringWrapper(String s) {
        this.s = s;
        this.lowerString = s.toLowerString();
    }

    // getter methods omitted

    // Rely on the hashing of String, as we know it to be good.
    public int hashCode() { return lowerString.hashCode(); }

    // We overrode hashCode, so we MUST also override equals. It is required
    // that if a.equals(b), then a.hashCode() == b.hashCode(), so we must
    // restore that invariant.
    public boolean equals(Object obj) {
        if (obj instanceof LowerStringWrapper) {
            return lowerString.equals(((LowerStringWrapper)obj).lowerString;
        } else {
            return lowerString.equals(obj);
        }
    }

    private String s;
    private String lowerString;
}

Answer 6

والسؤال جيدا اسأل جوش بلوك. أنا قدمت هذا المفهوم باعتباره RFE في جافا 7، ولكن تم إسقاطه، واعتقد ان السبب أداء شيء ذات الصلة. توافق، على الرغم من أن تم القيام به ط.

Answer 7

وأظن أن هذا لم يحدث لأنه من شأنه أن يمنع شفرة التجزئة التخزين المؤقت؟

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

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

Answer 8

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

وهذا يتناقض مع شجرة متوازنة الثنائية البحث (TreeMap) التي يجب أن تبدأ في جذور والعمل طريقها وصولا الى عقدة المطلوب في كل مرة لا بد من البحث. ويكيبيديا لديها بعض أكثر تعمقا تحليل . وباختصار، فإن كفاءة خريطة شجرة تعتمد بناء على طلب ثابت، وبالتالي فإن ترتيب العناصر يمكن التنبؤ بها وعاقل. ومع ذلك، ونظرا للضرب الأداء التي تفرضها نهج "تعبر إلى وجهتك"، بستس قادرون على توفير فقط <م> O (سجل (ن)) الأداء. لخرائط كبيرة، وهذا يمكن أن يحقق نجاحا كبيرا الأداء الهامة.

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

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

Answer 9

وهناك مثل هذه الميزة في com.google.common.collect.CustomConcurrentHashMap، للأسف، لا يوجد حاليا أي الطريق العام كيفية تعيين Equivalence (Hasharator بهم). ربما انهم لم تفعل حتى الآن مع ذلك، وربما أنها لا تعتبر ميزة أن تكون مفيدة بما فيه الكفاية. اسأل في الجوافة القائمة البريدية .

وأنا أتساءل لماذا لم يحدث حتى الآن، كما جاء في هذا الكلام أكثر من عامين.