ConcurrentHaspLRUHashMap实现初探

    上述看似非常优雅的方案，却隐藏几个严重的问题：

    1、 时间片的选择问题。

    这个方案中，时间片的选择是一个比较困难的问题。因为，如果系统在一个时间片之内爆掉内存的话，系统将直接崩溃。

    当然，这个问题，我们可以加外部限制得方式去控制

    2、 deadline 之前的数据，不能很快删除。导致deaddata滞留，浪费大量的内存

    假定 deadline之前的数据，约为总数据量的10%。因为删数据操作，只在put的时候。假定每个时间点的put操作，能覆盖20%的hash槽。这个10%*20%=2%，每个时间点，只能删除2%的过期数据。然后，随着时间的推移。这个过程必将趋于稳定。而这个趋于稳定后，内存消耗，至少是capacity的4-5倍。这样的消耗和浪费。是难以承受的。

    这个方案，从实际测试来看，情况非常糟糕。所以最终还是放弃了。

五、 ConcurrentLRUHashMap实现方式三:分段实现锁分离+每个段内维护一份退化链表

    【实现策略】：

    1、锁分离机制。内部分成了多个segement，每个segement是独立加锁，相互不干扰。

    2、每个segement内部维护一个双向链表(退化链表)。每次命中/添加，就把节点移动到退化链表头部。

    3、每次put操作，通过hash，散到每个segement中，判断segment的容量是否到达阈值。 如果到达阈值，则删除退化链表中最末尾的节点。

    【实现】

    1、重新定义HashEntry

static class HashEntry {
/**
* 键
*/
final K key;
/**
* hash值
*/
final int hash;
/**
* 值
*/
volatile V value;
/**
* hash链指针
*/
final HashEntry next;
/**
* 双向链表的下一个节点
*/
HashEntry linknext;
/**
* 双向链表的下一个节点
*/
HashEntry linkpref;
/**
* 死亡标记
*/
AtomicBoolean dead;

}

    2、定义segment

static final class Segment extends ReentrantLock implements

			Serializable {

		private static final long serialVersionUID = 1L;

		transient int threshold;

		transient volatile int count;

		transient int modCount;

		transient volatile HashEntry[] table;

		transient final HashEntry header;// 头节点

}

    3、 put操作

    代码太长了，见附件吧

    4、 get操作

		V get(Object key, int hash) {
			HashEntry e = getFirst(hash);
			// 遍历查找
			while (e != null) {
				if (e.hash == hash && key.equals(e.key)) {
					V v = e.value;
					// 把节点移动到头部。
					moveNodeToHeader(e);
					if (v != null)
						return v;
					// 在锁的情况读，必定能读到。
					// tab[index] = new HashEntry(key, hash, first, value)，
					// value赋值和tab[index]赋值可能会重新排序，重新排序之后，可能会读空值
					// 读到空值的话，在有锁的情况在再读一遍，一定能读！
					return readValueUnderLock(e); // recheck
				}
				e = e.next;
			}
			return null;

六、 ConcurrentLRUHashMap实现方式四:

    具体的做法是：

    1、 对concurrentHashMap 每个节点加时间戳，每次命中只修改该节点的时间戳。

    2、 集中式退化操作，每次命中并不进行退化操作。而是集中式进行退化操作(满的时候，或者时间到了)。

    代码：

private static class CountableKey implements Comparable> {

		public CountableKey(K key,V value) {

			if (value == null) {

				throw new NullPointerException("should not be null");

			}

			this.value = value;

			this.key = key;

			refreshTimeStamp();

		}

		

		public void refreshTimeStamp(){

			timestamp.set(System.currentTimeMillis());

		}

		final V value;

		final K key;

		AtomicLong timestamp = new AtomicLong();

		

		@Override

		public int compareTo(CountableKey o) {

			long thisval = this.timestamp.get();

			long anotherVal = o.timestamp.get();

			return (thisval < anotherVal?-1:(thisval == anotherVal?0:1));

		}

	}

    该方案的好处：

    1、 快速执行get操作。get操作的时间是“concurrentHashMap的get时间+更新时间戳”的时间。

    2、 put操作，一般的put操作的时间是“concurrentHashMap的put时间”，只要还未到达容量限制。而到达容量限制以后的，需要进行“退化，清理操作”+put的时间

    该方案的 可能存在的问题：

    1、 命中率，该算法的命中率同linkedHashMap

    2、 清除 策略:

    l 满了，执行清楚。缺点：1、会出现某个时刻，写操作卡死(如果正在等待清理的话)

    l 定时执行。缺点：1、性能耗费。2、读不一致仍然无法避免。

七、 ConcurrentLRUHashMap实现方式的比较

    本文只是抛砖引玉，希望能看到更多好多ConcurrentLRUHashMap的实现方式。由于能力有限。上文提到的第二种实现方式，在实际实现中并不能很好的退化，最终可能导致内存溢出。具体分析如下表

    总体来说，第三者性较好。

    比较方式一和方式三：