كيف يمكنك تنفيذ LRU في جافا ؟

Question

من فضلك لا أقول EHCache أو OSCache ، إلخ.نفترض لأغراض هذا السؤال الذي أريد أن تنفيذ بلدي فقط باستخدام SDK (التعلم بالممارسة).نظرا لأن ذاكرة التخزين المؤقت سيتم استخدامها في بيئة متعددة مؤشرات الترابط التي datastructures ؟ لقد نفذت بالفعل واحدة باستخدام LinkedHashMap و مجموعات#synchronizedMap, ولكن أنا الغريب إذا كان أي من الجديدة المتزامنة المجموعات سيكون أفضل المرشحين.

تحديث:كنت أقرأ من خلال Yegge أحدث عندما وجدت هذه الكتلة:

إذا كنت في حاجة مستمرة-الوصول في الوقت تريد الحفاظ على الإدراج أمر لا يمكنك أن تفعل أفضل من LinkedHashMap حقا رائعة بنية البيانات.الطريقة الوحيدة التي يمكن أن تكون أكثر من رائع لو كان هناك المتزامنة الإصدار.ولكن للأسف.

كنت أفكر بالضبط تقريبا نفس الشيء قبل ذهبت مع LinkedHashMap + Collections#synchronizedMap تنفيذ ذكرت أعلاه.من الجميل أن تعرف أنني لم يغفل شيئا.

استنادا إلى إجابات حتى الآن, يبدو أن أفضل رهان كبير المتزامنة LRU سيكون تمديد ConcurrentHashMap باستخدام بعض من نفس المنطق الذي LinkedHashMap الاستخدامات.

Answer 1

إذا كنت تفعل هذا مرة أخرى من الصفر اليوم, كنت استخدم الجوافة CacheBuilder.

Answer 2

أنا أحب الكثير من هذه الاقتراحات ، ولكن الآن أعتقد أنني سأبقى مع LinkedHashMap + Collections.synchronizedMap.إذا كنت تفعل إعادة النظر في هذا في المستقبل, ربما تعمل على توسيع ConcurrentHashMap في نفس الطريق LinkedHashMap يمتد HashMap.

تحديث:

حسب الطلب, وهنا جوهر الحالي التنفيذ.

private class LruCache<A, B> extends LinkedHashMap<A, B> {
    private final int maxEntries;

    public LruCache(final int maxEntries) {
        super(maxEntries + 1, 1.0f, true);
        this.maxEntries = maxEntries;
    }

    /**
     * Returns <tt>true</tt> if this <code>LruCache</code> has more entries than the maximum specified when it was
     * created.
     *
     * <p>
     * This method <em>does not</em> modify the underlying <code>Map</code>; it relies on the implementation of
     * <code>LinkedHashMap</code> to do that, but that behavior is documented in the JavaDoc for
     * <code>LinkedHashMap</code>.
     * </p>
     *
     * @param eldest
     *            the <code>Entry</code> in question; this implementation doesn't care what it is, since the
     *            implementation is only dependent on the size of the cache
     * @return <tt>true</tt> if the oldest
     * @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry)
     */
    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
        return super.size() > maxEntries;
    }
}

Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE));

Answer 3

أو استخدام هذا أباتشي العموم بنية البيانات:

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/map/LRUMap.html

Answer 4

هذه هي الجولة الثانية.

الجولة الأولى كانت ما خطرت ثم قراءة التعليقات مع المجال أكثر قليلا متأصلة في رأسي.

حتى هنا هو أبسط نسخة مع وحدة الاختبار الذي يظهر أنه يعمل على أساس بعض الإصدارات الأخرى.

الأولى غير المتزامنة الإصدار:

import java.util.LinkedHashMap;
import java.util.Map;

public class LruSimpleCache<K, V> implements LruCache <K, V>{

    Map<K, V> map = new LinkedHashMap (  );


    public LruSimpleCache (final int limit) {
           map = new LinkedHashMap <K, V> (16, 0.75f, true) {
               @Override
               protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
                   return super.size() > limit;
               }
           };
    }
    @Override
    public void put ( K key, V value ) {
        map.put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map.get(key);
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        V value =  map.get ( key );
        if (value!=null) {
            map.remove ( key );
            map.put(key, value);
        }
        return value;
    }

    @Override
    public void remove ( K key ) {
        map.remove ( key );
    }

    @Override
    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }


}

صحيح العلم سوف تتبع وصول يحصل ويضع.انظر JavaDocs.على removeEdelstEntry دون الحقيقية العلم إلى منشئ فقط تنفيذ FIFO ذاكرة التخزين المؤقت (انظر الملاحظات أدناه على FIFO و removeEldestEntry).

هنا هو اختبار يثبت أنه يعمل بوصفه LRU:

public class LruSimpleTest {

    @Test
    public void test () {
        LruCache <Integer, Integer> cache = new LruSimpleCache<> ( 4 );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();


        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();


        if ( !ok ) die ();

    }

الآن المتزامنة الإصدار...

حزمة org.نعمة.ذاكرة التخزين المؤقت ؛

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class LruSimpleConcurrentCache<K, V> implements LruCache<K, V> {

    final CacheMap<K, V>[] cacheRegions;


    private static class CacheMap<K, V> extends LinkedHashMap<K, V> {
        private final ReadWriteLock readWriteLock;
        private final int limit;

        CacheMap ( final int limit, boolean fair ) {
            super ( 16, 0.75f, true );
            this.limit = limit;
            readWriteLock = new ReentrantReadWriteLock ( fair );

        }

        protected boolean removeEldestEntry ( final Map.Entry<K, V> eldest ) {
            return super.size () > limit;
        }


        @Override
        public V put ( K key, V value ) {
            readWriteLock.writeLock ().lock ();

            V old;
            try {

                old = super.put ( key, value );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return old;

        }


        @Override
        public V get ( Object key ) {
            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.get ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;
        }

        @Override
        public V remove ( Object key ) {

            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.remove ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public V getSilent ( K key ) {
            readWriteLock.writeLock ().lock ();

            V value;

            try {

                value = this.get ( key );
                if ( value != null ) {
                    this.remove ( key );
                    this.put ( key, value );
                }
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public int size () {
            readWriteLock.readLock ().lock ();
            int size = -1;
            try {
                size = super.size ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return size;
        }

        public String toString () {
            readWriteLock.readLock ().lock ();
            String str;
            try {
                str = super.toString ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return str;
        }


    }

    public LruSimpleConcurrentCache ( final int limit, boolean fair ) {
        int cores = Runtime.getRuntime ().availableProcessors ();
        int stripeSize = cores < 2 ? 4 : cores * 2;
        cacheRegions = new CacheMap[ stripeSize ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    public LruSimpleConcurrentCache ( final int concurrency, final int limit, boolean fair ) {

        cacheRegions = new CacheMap[ concurrency ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    private int stripeIndex ( K key ) {
        int hashCode = key.hashCode () * 31;
        return hashCode % ( cacheRegions.length );
    }

    private CacheMap<K, V> map ( K key ) {
        return cacheRegions[ stripeIndex ( key ) ];
    }

    @Override
    public void put ( K key, V value ) {

        map ( key ).put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map ( key ).get ( key );
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        return map ( key ).getSilent ( key );

    }

    @Override
    public void remove ( K key ) {
        map ( key ).remove ( key );
    }

    @Override
    public int size () {
        int size = 0;
        for ( CacheMap<K, V> cache : cacheRegions ) {
            size += cache.size ();
        }
        return size;
    }

    public String toString () {

        StringBuilder builder = new StringBuilder ();
        for ( CacheMap<K, V> cache : cacheRegions ) {
            builder.append ( cache.toString () ).append ( '\n' );
        }

        return builder.toString ();
    }


}

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

هنا هو اختبار لإظهار أن المتزامنة النسخة ربما يعمل.:) (اختبار تحت النار سيكون الطريق الحقيقي).

public class SimpleConcurrentLRUCache {


    @Test
    public void test () {
        LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 1, 4, false );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );

        puts (cache);
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();


        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();

        cache.put ( 8, 8 );
        cache.put ( 9, 9 );

        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();


        puts (cache);


        if ( !ok ) die ();

    }


    @Test
    public void test2 () {
        LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 400, false );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        for (int index =0 ; index < 5_000; index++) {
            cache.get(0);
            cache.get ( 1 );
            cache.put ( 2, index  );
            cache.put ( 3, index );
            cache.put(index, index);
        }

        boolean ok = cache.getSilent ( 0 ) == 0 || die ();
        ok |= cache.getSilent ( 1 ) == 1 || die ();
        ok |= cache.getSilent ( 2 ) != null || die ();
        ok |= cache.getSilent ( 3 ) != null || die ();

        ok |= cache.size () < 600 || die();
        if ( !ok ) die ();



    }

}

هذا هو آخر وظيفة..المشاركة الأولى حذف كما كان LFU لا LRU.

فكرت في.كنت أحاول تحاول أن تصل مع أبسط نسخة من LRU باستخدام معيار JDK w/o كثيرا التنفيذ.

هنا هو ما جاء مع.أول محاولة لي كان قليلا من الكوارث كما نفذت LFU بدلا من LRU ثم أضفت FIFO ، LRU الدعم لها...ثم أدركت أنها أصبحت وحش.ثم بدأت أتحدث إلى صديقي جون الذي كان بالكاد المهتمين ، ثم وصفت في أعماق طول كيف نفذت LFU, LRU و FIFO و كيف يمكن التبديل مع بسيطة التعداد الأرجنتين ، ثم أدركت أن كل ما اردته كان بسيط LRU.لذلك تجاهل في وقت سابق بعد من لي واسمحوا لي أن أعرف إذا كنت تريد أن ترى LRU/LFU/FIFO ذاكرة التخزين المؤقت التي يتم للتحويل عن طريق التعداد...لا ؟ حسنا..هنا يذهب.

ممكن أبسط LRU فقط باستخدام JDK.أنا نفذت كل المتزامنة نسخة غير المتزامنة الإصدار.

أنا خلقت واجهة مشتركة (هو بساطتها لذلك على الأرجح في عداد المفقودين بعض الميزات التي ترغب لكنه يعمل على استخدام الحالات, ولكن دعونا إذا كنت تود أن ترى ميزة XYZ اسمحوا لي أن أعرف...أنا أعيش لكتابة التعليمات البرمجية.).

public interface LruCache<KEY, VALUE> {
    void put ( KEY key, VALUE value );

    VALUE get ( KEY key );

    VALUE getSilent ( KEY key );

    void remove ( KEY key );

    int size ();
}

قد كنت أتساءل ما getSilent هو.لقد استخدم هذا الاختبار.getSilent لا يغير LRU درجة من عنصر.

الأولى غير المتزامنة واحد....

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LruCacheNormal<KEY, VALUE> implements LruCache<KEY,VALUE> {

    Map<KEY, VALUE> map = new HashMap<> ();
    Deque<KEY> queue = new LinkedList<> ();
    final int limit;


    public LruCacheNormal ( int limit ) {
        this.limit = limit;
    }

    public void put ( KEY key, VALUE value ) {
        VALUE oldValue = map.put ( key, value );

        /*If there was already an object under this key,
         then remove it before adding to queue
         Frequently used keys will be at the top so the search could be fast.
         */
        if ( oldValue != null ) {
            queue.removeFirstOccurrence ( key );
        }
        queue.addFirst ( key );

        if ( map.size () > limit ) {
            final KEY removedKey = queue.removeLast ();
            map.remove ( removedKey );
        }

    }


    public VALUE get ( KEY key ) {

        /* Frequently used keys will be at the top so the search could be fast.*/
        queue.removeFirstOccurrence ( key );
        queue.addFirst ( key );
        return map.get ( key );
    }


    public VALUE getSilent ( KEY key ) {

        return map.get ( key );
    }

    public void remove ( KEY key ) {

        /* Frequently used keys will be at the top so the search could be fast.*/
        queue.removeFirstOccurrence ( key );
        map.remove ( key );
    }

    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }
}

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

عندما وضع ويسمى المفتاح يحصل تضاف إلى قائمة الانتظار.عندما الحصول على ويسمى المفتاح يحصل على إزالة وإعادة إضافتها إلى الجزء العلوي من قائمة الانتظار.

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

إذا كان لديك ذاكرة التخزين المؤقت أقل من 1000 البنود, هذا يجب أن تعمل على ما يرام.

هنا هو اختبار بسيط لإظهار عملياتها في العمل.

public class LruCacheTest {

    @Test
    public void test () {
        LruCache<Integer, Integer> cache = new LruCacheNormal<> ( 4 );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 0 ) == 0 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 0 ) == null || die ();
        ok |= cache.getSilent ( 1 ) == null || die ();
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();

        if ( !ok ) die ();

    }
}

آخر LRU كانت واحدة مترابطة, و رجاء لا التفاف عليه في مزامنة أي شيء....

هنا هو طعنة في المتزامنة الإصدار.

import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;

public class ConcurrentLruCache<KEY, VALUE> implements LruCache<KEY,VALUE> {

    private final ReentrantLock lock = new ReentrantLock ();


    private final Map<KEY, VALUE> map = new ConcurrentHashMap<> ();
    private final Deque<KEY> queue = new LinkedList<> ();
    private final int limit;


    public ConcurrentLruCache ( int limit ) {
        this.limit = limit;
    }

    @Override
    public void put ( KEY key, VALUE value ) {
        VALUE oldValue = map.put ( key, value );
        if ( oldValue != null ) {
            removeThenAddKey ( key );
        } else {
            addKey ( key );
        }
        if (map.size () > limit) {
            map.remove ( removeLast() );
        }
    }


    @Override
    public VALUE get ( KEY key ) {
        removeThenAddKey ( key );
        return map.get ( key );
    }


    private void addKey(KEY key) {
        lock.lock ();
        try {
            queue.addFirst ( key );
        } finally {
            lock.unlock ();
        }


    }

    private KEY removeLast( ) {
        lock.lock ();
        try {
            final KEY removedKey = queue.removeLast ();
            return removedKey;
        } finally {
            lock.unlock ();
        }
    }

    private void removeThenAddKey(KEY key) {
        lock.lock ();
        try {
            queue.removeFirstOccurrence ( key );
            queue.addFirst ( key );
        } finally {
            lock.unlock ();
        }

    }

    private void removeFirstOccurrence(KEY key) {
        lock.lock ();
        try {
            queue.removeFirstOccurrence ( key );
        } finally {
            lock.unlock ();
        }

    }


    @Override
    public VALUE getSilent ( KEY key ) {
        return map.get ( key );
    }

    @Override
    public void remove ( KEY key ) {
        removeFirstOccurrence ( key );
        map.remove ( key );
    }

    @Override
    public int size () {
        return map.size ();
    }

    public String toString () {
        return map.toString ();
    }
}

الاختلافات الرئيسية هي استخدام ConcurrentHashMap بدلا من HashMap ، واستخدام القفل (كنت قد حصلت بعيدا مع تزامن, ولكن...).

أنا لم تختبر تحت النار ، ولكن يبدو بسيط LRU قد عمل في 80% من حالات الاستخدام حيث كنت في حاجة بسيطة LRU الخريطة.

أرحب ردود الفعل ، باستثناء لماذا لا تستخدم المكتبة a, b, أو c.السبب في أنني لا دائما استخدام المكتبة لأنني لا يريدون دائما كل حرب ملف 80MB و أنا أكتب المكتبات لذا تميل إلى جعل النقابة المكونات قادرا جيدة بما فيه الكفاية حل في مكان و شخص يمكن أن المكونات في مخبأ آخر مزود إذا كانت مثل.:) لم تعرف عندما يقوم شخص ما قد تحتاج الجوافة أو ehcache أو أي شيء آخر أنا لا أريد أن تدرج لهم, ولكن إذا كنت تجعل التخزين المؤقت المكونات قادرة ، وسوف يستبعد لهم أيضا.

الحد من التبعيات الخاصة به الثواب.أحب أن الحصول على بعض ردود الفعل على كيفية جعل هذا أسهل أو أسرع أو كليهما.

أيضا إذا كان أي شخص يعرف من استعداد للذهاب....

حسنا..أنا أعرف ما كنت أفكر...لماذا لا يستعمل removeEldest دخول من LinkedHashMap ، وكذلك يجب ولكن....ولكن..ولكن..سيكون هذا FIFO لا LRU و كنا نحاول تنفيذ LRU.

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
            return this.size () > limit;
        }
    };

فشل هذا الاختبار على رمز أعلاه...

        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();

حتى هنا هو سريعة وقذرة FIFO ذاكرة التخزين المؤقت باستخدام removeEldestEntry.

import java.util.*;

public class FifoCache<KEY, VALUE> implements LruCache<KEY,VALUE> {

    final int limit;

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
            return this.size () > limit;
        }
    };


    public LruCacheNormal ( int limit ) {
        this.limit = limit;
    }

    public void put ( KEY key, VALUE value ) {
         map.put ( key, value );


    }


    public VALUE get ( KEY key ) {

        return map.get ( key );
    }


    public VALUE getSilent ( KEY key ) {

        return map.get ( key );
    }

    public void remove ( KEY key ) {
        map.remove ( key );
    }

    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }
}

FIFOs سريع.لا البحث حولها.هل يمكن أن الجبهة FIFO أمام LRU و التي من شأنها أن التعامل مع معظم الساخنة إدخالات بشكل جيد جدا.أفضل LRU تسير في حاجة إلى أن عكس عنصر عقدة الميزة.

على أي حال...الآن بعد أن كتبت بعض التعليمات البرمجية ، اسمحوا لي أن تذهب من خلال إجابات أخرى ونرى ما فاتني...أول مرة مسحت لهم.

Answer 5

LinkedHashMap O(1) ، ولكن يتطلب المزامنة.لا تحتاج إلى إعادة اختراع العجلة هناك.

2 خيارات زيادة التزامن:

1.إنشاء عدة LinkedHashMap, و التجزئة في:على سبيل المثال: LinkedHashMap[4], index 0, 1, 2, 3.على المفتاح لا key%4 (أو binary OR على [key, 3]) أن تختار أي خريطة للقيام وضع/على/إزالة.

2.هل أنت 'تقريبا' LRU من خلال توسيع ConcurrentHashMap, و وجود صلة تجزئة الخريطة مثل هيكل في كل من المناطق داخل منه.قفل يمكن أن يحدث أكثر من granularly LinkedHashMap التي يتم مزامنتها.على put أو putIfAbsent فقط قفل على رأس و ذيل القائمة المطلوبة (في المنطقة).على إزالة أو الحصول على كامل المنطقة يجب أن يكون مؤمنا.أنا الغريب إذا الذرية القوائم المرتبطة من نوع ما قد يساعد هنا-ربما حتى على رأس القائمة.ربما أكثر.

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

1. سيكون من الأسهل لكتابة أسرع معتدلة التزامن.

2. سيكون من الصعب الكتابة ولكن مقياس أفضل بكثير في التزامن عالية جدا.سيكون أبطأ من أجل الوصول العادي (كما ConcurrentHashMap أبطأ من HashMap حيث لا يوجد التزامن)

Answer 6

هناك نوعان من تطبيقات مفتوحة المصدر.

أباتشي المؤسسة العامة لاستصلاح الأراضي قد ConcurrentLRUCache: https://lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html

هناك مشروع مفتوح المصدر من أجل ConcurrentLinkedHashMap:http://code.google.com/p/concurrentlinkedhashmap/

Answer 7

وأود أن تنظر في استخدام java.util.المتزامنة.PriorityBlockingQueue, مع إعطاء الأولوية التي يحددها "numberOfUses" العداد في كل عنصر.سأكون حذرا جدا جدا الحصول على جميع التزامن الصحيح ، "numberOfUses" العداد يعني أن العنصر لا يمكن أن تكون ثابتة.

كائن عنصر سيكون المجمع عن الكائنات في ذاكرة التخزين المؤقت:

class CacheElement {
    private final Object obj;
    private int numberOfUsers = 0;

    CacheElement(Object obj) {
        this.obj = obj;
    }

    ... etc.
}

Answer 8

ويساعد هذا الأمل .

import java.util.*;
public class Lru {

public static <K,V> Map<K,V> lruCache(final int maxSize) {
    return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) {

        private static final long serialVersionUID = -3588047435434569014L;

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    };
 }
 public static void main(String[] args ) {
    Map<Object, Object> lru = Lru.lruCache(2);      
    lru.put("1", "1");
    lru.put("2", "2");
    lru.put("3", "3");
    System.out.println(lru);
}
}

Answer 9

LRU يمكن تنفيذها باستخدام ConcurrentLinkedQueue و ConcurrentHashMap التي يمكن استخدامها في خاصية تعدد السيناريو.رئيس قائمة الانتظار هو ذلك العنصر الذي تم على قائمة الانتظار وقتا أطول.ذيل قائمة الانتظار هو ذلك العنصر الذي تم على قائمة الانتظار أقصر وقت.عندما عنصر موجود في الخريطة يمكننا إزالته من LinkedQueue وأدخله في الذيل.

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

public class LRUCache<K,V> {
  private ConcurrentHashMap<K,V> map;
  private ConcurrentLinkedQueue<K> queue;
  private final int size; 

  public LRUCache(int size) {
    this.size = size;
    map = new ConcurrentHashMap<K,V>(size);
    queue = new ConcurrentLinkedQueue<K>();
  }

  public V get(K key) {
    //Recently accessed, hence move it to the tail
    queue.remove(key);
    queue.add(key);
    return map.get(key);
  }

  public void put(K key, V value) {
    //ConcurrentHashMap doesn't allow null key or values
    if(key == null || value == null) throw new NullPointerException();
    if(map.containsKey(key) {
      queue.remove(key);
    }
    if(queue.size() >= size) {
      K lruKey = queue.poll();
      if(lruKey != null) {
        map.remove(lruKey);
      }
    }
    queue.add(key);
    map.put(key,value);
  }

}

Answer 10

هنا هو بلدي تنفيذ LRU.لقد استخدمت PriorityQueue الذي يعمل في الأساس مثل FIFO و لا threadsafe.تستخدم المقارنة على أساس الوقت الصفحة الخلق على أساس ينفذ الطلب صفحات على الأقل في الآونة الأخيرة استخدام الوقت.

صفحات للنظر فيها :2, 1, 0, 2, 8, 2, 4

صفحة تضاف إلى ذاكرة التخزين المؤقت :2
صفحة تضاف إلى ذاكرة التخزين المؤقت :1
صفحة تضاف إلى ذاكرة التخزين المؤقت :0
الصفحة:2 بالفعل exisit في ذاكرة التخزين المؤقت.آخر زيارة للموقع في وقت تحديث
خطأ صفحة, صفحة:1 ، مع استبدال الصفحة:8
صفحة تضاف إلى ذاكرة التخزين المؤقت :8
الصفحة:2 بالفعل exisit في ذاكرة التخزين المؤقت.آخر زيارة للموقع في وقت تحديث
خطأ صفحة, صفحة:0 ، مع استبدال الصفحة:4
صفحة تضاف إلى ذاكرة التخزين المؤقت :4

الإخراج

LRUCache الصفحات
-------------
اسم الصفحة:8, PageCreationTime:1365957019974
اسم الصفحة:2, PageCreationTime:1365957020074
اسم الصفحة:4, PageCreationTime:1365957020174

أدخل رمز هنا

import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;


public class LRUForCache {
    private PriorityQueue<LRUPage> priorityQueue = new PriorityQueue<LRUPage>(3, new LRUPageComparator());
    public static void main(String[] args) throws InterruptedException {

        System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4");
        System.out.println("----------------------------------------------\n");

        LRUForCache cache = new LRUForCache();
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("1"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("0"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("8"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("4"));
        Thread.sleep(100);

        System.out.println("\nLRUCache Pages");
        System.out.println("-------------");
        cache.displayPriorityQueue();
    }


    public synchronized void  addPageToQueue(LRUPage page){
        boolean pageExists = false;
        if(priorityQueue.size() == 3){
            Iterator<LRUPage> iterator = priorityQueue.iterator();

            while(iterator.hasNext()){
                LRUPage next = iterator.next();
                if(next.getPageName().equals(page.getPageName())){
                    /* wanted to just change the time, so that no need to poll and add again.
                       but elements ordering does not happen, it happens only at the time of adding
                       to the queue

                       In case somebody finds it, plz let me know.
                     */
                    //next.setPageCreationTime(page.getPageCreationTime()); 

                    priorityQueue.remove(next);
                    System.out.println("Page: " + page.getPageName() + " already exisit in cache. Last accessed time updated");
                    pageExists = true;
                    break;
                }
            }
            if(!pageExists){
                // enable it for printing the queue elemnts
                //System.out.println(priorityQueue);
                LRUPage poll = priorityQueue.poll();
                System.out.println("Page Fault, PAGE: " + poll.getPageName()+", Replaced with PAGE: "+page.getPageName());

            }
        }
        if(!pageExists){
            System.out.println("Page added into cache is : " + page.getPageName());
        }
        priorityQueue.add(page);

    }

    public void displayPriorityQueue(){
        Iterator<LRUPage> iterator = priorityQueue.iterator();
        while(iterator.hasNext()){
            LRUPage next = iterator.next();
            System.out.println(next);
        }
    }
}

class LRUPage{
    private String pageName;
    private long pageCreationTime;
    public LRUPage(String pagename){
        this.pageName = pagename;
        this.pageCreationTime = System.currentTimeMillis();
    }

    public String getPageName() {
        return pageName;
    }

    public long getPageCreationTime() {
        return pageCreationTime;
    }

    public void setPageCreationTime(long pageCreationTime) {
        this.pageCreationTime = pageCreationTime;
    }

    @Override
    public boolean equals(Object obj) {
        LRUPage page = (LRUPage)obj; 
        if(pageCreationTime == page.pageCreationTime){
            return true;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return (int) (31 * pageCreationTime);
    }

    @Override
    public String toString() {
        return "PageName: " + pageName +", PageCreationTime: "+pageCreationTime;
    }
}


class LRUPageComparator implements Comparator<LRUPage>{

    @Override
    public int compare(LRUPage o1, LRUPage o2) {
        if(o1.getPageCreationTime() > o2.getPageCreationTime()){
            return 1;
        }
        if(o1.getPageCreationTime() < o2.getPageCreationTime()){
            return -1;
        }
        return 0;
    }
}

Answer 11

هنا هو بلدي اختبار أفضل أداء المتزامنة LRU التنفيذ دون أي متزامنة كتلة:

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

/**
 * @param key - may not be null!
 * @param value - may not be null!
 */
public void put(final Key key, final Value value) {
    if (map.containsKey(key)) {
        queue.remove(key); // remove the key from the FIFO queue
    }

    while (queue.size() >= maxSize) {
        Key oldestKey = queue.poll();
        if (null != oldestKey) {
            map.remove(oldestKey);
        }
    }
    queue.add(key);
    map.put(key, value);
}

/**
 * @param key - may not be null!
 * @return the value associated to the given key or null
 */
public Value get(final Key key) {
    return map.get(key);
}

}

Answer 12

هذا هو LRU تستخدم ، التي بتغليف LinkedHashMap ومقابض التزامن مع بسيطة مزامنة قفل حراسة العصير البقع.أنه "يمس" العناصر كما أنها تستخدم بحيث تصبح "الطازجة" العنصر مرة أخرى ، بحيث أنه هو في الواقع LRU.كما كان شرط من عناصر وجود عمر الحد الأدنى الذي يمكنك أيضا أن نفكر بأنه "أقصى وقت الخمول" المسموح بها ، ثم من أنت حتى الإخلاء.

ومع ذلك أنا أتفق مع هانك استنتاج الإجابة المقبولة -- إذا كنت ابتداء من هذا اليوم مرة أخرى ، كنت تحقق من الجوافة CacheBuilder.

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;


public class MaxIdleLRUCache<KK, VV> {

    final static private int IDEAL_MAX_CACHE_ENTRIES = 128;

    public interface DeadElementCallback<KK, VV> {
        public void notify(KK key, VV element);
    }

    private Object lock = new Object();
    private long minAge;
    private HashMap<KK, Item<VV>> cache;


    public MaxIdleLRUCache(long minAgeMilliseconds) {
        this(minAgeMilliseconds, IDEAL_MAX_CACHE_ENTRIES);
    }

    public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries) {
        this(minAgeMilliseconds, idealMaxCacheEntries, null);
    }

    public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries, final DeadElementCallback<KK, VV> callback) {
        this.minAge = minAgeMilliseconds;
        this.cache = new LinkedHashMap<KK, Item<VV>>(IDEAL_MAX_CACHE_ENTRIES + 1, .75F, true) {
            private static final long serialVersionUID = 1L;

            // This method is called just after a new entry has been added
            public boolean removeEldestEntry(Map.Entry<KK, Item<VV>> eldest) {
                // let's see if the oldest entry is old enough to be deleted. We don't actually care about the cache size.
                long age = System.currentTimeMillis() - eldest.getValue().birth;
                if (age > MaxIdleLRUCache.this.minAge) {
                    if ( callback != null ) {
                        callback.notify(eldest.getKey(), eldest.getValue().payload);
                    }
                    return true; // remove it
                }
                return false; // don't remove this element
            }
        };

    }

    public void put(KK key, VV value) {
        synchronized ( lock ) {
//          System.out.println("put->"+key+","+value);
            cache.put(key, new Item<VV>(value));
        }
    }

    public VV get(KK key) {
        synchronized ( lock ) {
//          System.out.println("get->"+key);
            Item<VV> item = getItem(key);
            return item == null ? null : item.payload;
        }
    }

    public VV remove(String key) {
        synchronized ( lock ) {
//          System.out.println("remove->"+key);
            Item<VV> item =  cache.remove(key);
            if ( item != null ) {
                return item.payload;
            } else {
                return null;
            }
        }
    }

    public int size() {
        synchronized ( lock ) {
            return cache.size();
        }
    }

    private Item<VV> getItem(KK key) {
        Item<VV> item = cache.get(key);
        if (item == null) {
            return null;
        }
        item.touch(); // idle the item to reset the timeout threshold
        return item;
    }

    private static class Item<T> {
        long birth;
        T payload;

        Item(T payload) {
            this.birth = System.currentTimeMillis();
            this.payload = payload;
        }

        public void touch() {
            this.birth = System.currentTimeMillis();
        }
    }

}

Answer 13

حسنا بالنسبة ذاكرة التخزين المؤقت سوف تكون عموما يبحث عن بعض قطعة من البيانات عبر وكيل كائن (URL, سلسلة....) حتى واجهة الحكيم كنت تريد الخريطة.ولكن ركلة الأمور تريد طابور مثل هيكل.داخليا وأود أن الحفاظ على اثنين من هياكل البيانات ، أولوية في قائمة الانتظار و HashMap.هيريس التنفيذ التي يجب أن تكون قادرة على القيام بكل شيء في س(1) مرة.

وهنا فئة أضفت سريعة جدا:

import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V>
{
    int maxSize;
    int currentSize = 0;

    Map<K, ValueHolder<K, V>> map;
    LinkedList<K> queue;

    public LRUCache(int maxSize)
    {
        this.maxSize = maxSize;
        map = new HashMap<K, ValueHolder<K, V>>();
        queue = new LinkedList<K>();
    }

    private void freeSpace()
    {
        K k = queue.remove();
        map.remove(k);
        currentSize--;
    }

    public void put(K key, V val)
    {
        while(currentSize >= maxSize)
        {
            freeSpace();
        }
        if(map.containsKey(key))
        {//just heat up that item
            get(key);
            return;
        }
        ListNode<K> ln = queue.add(key);
        ValueHolder<K, V> rv = new ValueHolder<K, V>(val, ln);
        map.put(key, rv);       
        currentSize++;
    }

    public V get(K key)
    {
        ValueHolder<K, V> rv = map.get(key);
        if(rv == null) return null;
        queue.remove(rv.queueLocation);
        rv.queueLocation = queue.add(key);//this ensures that each item has only one copy of the key in the queue
        return rv.value;
    }
}

class ListNode<K>
{
    ListNode<K> prev;
    ListNode<K> next;
    K value;
    public ListNode(K v)
    {
        value = v;
        prev = null;
        next = null;
    }
}

class ValueHolder<K,V>
{
    V value;
    ListNode<K> queueLocation;
    public ValueHolder(V value, ListNode<K> ql)
    {
        this.value = value;
        this.queueLocation = ql;
    }
}

class LinkedList<K>
{
    ListNode<K> head = null;
    ListNode<K> tail = null;

    public ListNode<K> add(K v)
    {
        if(head == null)
        {
            assert(tail == null);
            head = tail = new ListNode<K>(v);
        }
        else
        {
            tail.next = new ListNode<K>(v);
            tail.next.prev = tail;
            tail = tail.next;
            if(tail.prev == null)
            {
                tail.prev = head;
                head.next = tail;
            }
        }
        return tail;
    }

    public K remove()
    {
        if(head == null)
            return null;
        K val = head.value;
        if(head.next == null)
        {
            head = null;
            tail = null;
        }
        else
        {
            head = head.next;
            head.prev = null;
        }
        return val;
    }

    public void remove(ListNode<K> ln)
    {
        ListNode<K> prev = ln.prev;
        ListNode<K> next = ln.next;
        if(prev == null)
        {
            head = next;
        }
        else
        {
            prev.next = next;
        }
        if(next == null)
        {
            tail = prev;
        }
        else
        {
            next.prev = prev;
        }       
    }
}

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

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

Answer 14

إلقاء نظرة على ConcurrentSkipListMap.هذا يجب أن تعطيك log(n) الوقت لاختبار وإزالة عنصر إذا كان موجود بالفعل في ذاكرة التخزين المؤقت, و وقت ثابت إعادة إضافته.

كنت فقط بحاجة الى بعض مضادة الخ و المجمع عنصر القوة ترتيب LRU النظام وضمان الأخيرة الأشياء المهملة عند امتلاء ذاكرة التخزين المؤقت.

Answer 15

هنا هو بلدي قصيرة التنفيذ ، يرجى انتقاد أو تحسين ذلك!

package util.collection;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * Limited size concurrent cache map implementation.<br/>
 * LRU: Least Recently Used.<br/>
 * If you add a new key-value pair to this cache after the maximum size has been exceeded,
 * the oldest key-value pair will be removed before adding.
 */

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;
private int currentSize = 0;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

private synchronized void freeSpace() {
    Key key = queue.poll();
    if (null != key) {
        map.remove(key);
        currentSize = map.size();
    }
}

public void put(Key key, Value val) {
    if (map.containsKey(key)) {// just heat up that item
        put(key, val);
        return;
    }
    while (currentSize >= maxSize) {
        freeSpace();
    }
    synchronized(this) {
        queue.add(key);
        map.put(key, val);
        currentSize++;
    }
}

public Value get(Key key) {
    return map.get(key);
}
}

Answer 16

هنا هو بلدي تنفيذ هذه المشكلة

simplelrucache يوفر threadsafe, بسيط جدا, غير الموزعة LRU التخزين المؤقت مع TTL الدعم.فإنه يوفر اثنين من تطبيقات:

• المتزامنة على أساس ConcurrentLinkedHashMap
• متزامنة على أساس LinkedHashMap

يمكنك العثور عليها هنا: http://code.google.com/p/simplelrucache/

Answer 17

انا ابحث عن أفضل LRU باستخدام كود جافا.هل من الممكن بالنسبة لك لتبادل جافا LRU التعليمات البرمجية باستخدام LinkedHashMap و Collections#synchronizedMap?حاليا أنا باستخدام LRUMap implements Map و الكود يعمل بشكل جيد, ولكن أنا الحصول على ArrayIndexOutofBoundException على اختبار الحمل باستخدام 500 المستخدمين على الأسلوب التالي.طريقة التحركات الأخيرة كائن إلى مقدمة الطابور.

private void moveToFront(int index) {
        if (listHead != index) {
            int thisNext = nextElement[index];
            int thisPrev = prevElement[index];
            nextElement[thisPrev] = thisNext;
            if (thisNext >= 0) {
                prevElement[thisNext] = thisPrev;
            } else {
                listTail = thisPrev;
            }
            //old listHead and new listHead say new is 1 and old was 0 then prev[1]= 1 is the head now so no previ so -1
            // prev[0 old head] = new head right ; next[new head] = old head
            prevElement[index] = -1;
            nextElement[index] = listHead;
            prevElement[listHead] = index;
            listHead = index;
        }
    }

get(Object key) و put(Object key, Object value) طريقة المكالمات الواردة أعلاه moveToFront الأسلوب.

Answer 18

أريد أن أضيف تعليق على الجواب المعطى من قبل هانك ولكن بعض كيف أنا لست قادرا على - يرجى التعامل معها على أنها التعليق

LinkedHashMap يحافظ على الوصول إلى النظام استنادا على المعلمة مرت في منشئ يبقى مضاعف اصطف قائمة للحفاظ على النظام (انظر LinkedHashMap.دخول)

@Pacerier فمن الصحيح أن LinkedHashMap يحتفظ بنفس الترتيب في حين التكرار إذا كان عنصر يضاف مرة أخرى ولكن هذا فقط في حالة إدخال وضع النظام.

هذا هو ما وجدته في مستندات جافا من LinkedHashMap.دخول وجوه

    /**
     * This method is invoked by the superclass whenever the value
     * of a pre-existing entry is read by Map.get or modified by Map.set.
     * If the enclosing Map is access-ordered, it moves the entry
     * to the end of the list; otherwise, it does nothing.
     */
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }

هذه الطريقة تأخذ الرعاية من الانتقال الوصول إليها مؤخرا عنصر إلى نهاية القائمة.كل ذلك في جميع LinkedHashMap هو أفضل بنية البيانات لتنفيذ LRUCache.

Answer 19

فكرة أخرى وحتى تنفيذ بسيط باستخدام LinkedHashMap مجموعة من جافا.

LinkedHashMap توفير طريقة removeEldestEntry و التي يمكن تجاوزها في الطريق المذكورة في المثال.بشكل افتراضي تنفيذ هذه المجموعة هيكل كاذبة.إذا كان صحيحا و حجم هذا الهيكل يتجاوز القدرات الأولية من البكر أو أكثر العناصر التي سيتم إزالتها.

ونحن يمكن أن يكون pageno و محتوى الصفحة في حالتي pageno هو عدد صحيح pagecontent لقد حفظت الصفحة عدد قيم السلسلة.

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author Deepak Singhvi
 *
 */
public class LRUCacheUsingLinkedHashMap {


     private static int CACHE_SIZE = 3;
     public static void main(String[] args) {
        System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99");
        System.out.println("----------------------------------------------\n");


// accessOrder is true, so whenever any page gets changed or accessed,    // its order will change in the map, 
              LinkedHashMap<Integer,String> lruCache = new              
                 LinkedHashMap<Integer,String>(CACHE_SIZE, .75F, true) {

           private static final long serialVersionUID = 1L;

           protected boolean removeEldestEntry(Map.Entry<Integer,String>                           

                     eldest) {
                          return size() > CACHE_SIZE;
                     }

                };

  lruCache.put(2, "2");
  lruCache.put(1, "1");
  lruCache.put(0, "0");
  System.out.println(lruCache + "  , After first 3 pages in cache");
  lruCache.put(2, "2");
  System.out.println(lruCache + "  , Page 2 became the latest page in the cache");
  lruCache.put(8, "8");
  System.out.println(lruCache + "  , Adding page 8, which removes eldest element 2 ");
  lruCache.put(2, "2");
  System.out.println(lruCache+ "  , Page 2 became the latest page in the cache");
  lruCache.put(4, "4");
  System.out.println(lruCache+ "  , Adding page 4, which removes eldest element 1 ");
  lruCache.put(99, "99");
  System.out.println(lruCache + " , Adding page 99, which removes eldest element 8 ");

     }

}

نتيجة أعلاه بتنفيذ التعليمات البرمجية كما يلي:

 Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99
--------------------------------------------------
    {2=2, 1=1, 0=0}  , After first 3 pages in cache
    {2=2, 1=1, 0=0}  , Page 2 became the latest page in the cache
    {1=1, 0=0, 8=8}  , Adding page 8, which removes eldest element 2 
    {0=0, 8=8, 2=2}  , Page 2 became the latest page in the cache
    {8=8, 2=2, 4=4}  , Adding page 4, which removes eldest element 1 
    {2=2, 4=4, 99=99} , Adding page 99, which removes eldest element 8 

Answer 20

عقب @sanjanab مفهوم (ولكن بعد إصلاحات) جعلت لي نسخة من LRUCache توفير أيضا المستهلك الذي يسمح أن تفعل شيئا مع العناصر التي تمت إزالتها إذا لزم الأمر.

public class LRUCache<K, V> {

    private ConcurrentHashMap<K, V> map;
    private final Consumer<V> onRemove;
    private ConcurrentLinkedQueue<K> queue;
    private final int size;

    public LRUCache(int size, Consumer<V> onRemove) {
        this.size = size;
        this.onRemove = onRemove;
        this.map = new ConcurrentHashMap<>(size);
        this.queue = new ConcurrentLinkedQueue<>();
    }

    public V get(K key) {
        //Recently accessed, hence move it to the tail
        if (queue.remove(key)) {
            queue.add(key);
            return map.get(key);
        }
        return null;
    }

    public void put(K key, V value) {
        //ConcurrentHashMap doesn't allow null key or values
        if (key == null || value == null) throw new IllegalArgumentException("key and value cannot be null!");

        V existing = map.get(key);
        if (existing != null) {
            queue.remove(key);
            onRemove.accept(existing);
        }

        if (map.size() >= size) {
            K lruKey = queue.poll();
            if (lruKey != null) {
                V removed = map.remove(lruKey);
                onRemove.accept(removed);
            }
        }
        queue.add(key);
        map.put(key, value);
    }
}

Answer 21

الروبوت يوفر تنفيذ LRU.على رمز نظيفة وواضحة.