Java温故知新 - 集合类 - JAVA

p.put(new Item(5, "555"), 5);
System.out.println(lruMap);
}

}

public class LRUTest {

public static void main(String[] args) {
Map lruMap = new LinkedHashMap() {
private static final long serialVersionUID = 1L;

@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > 3;
}
};
lruMap.put(new Item(1, "111"), 1);
lruMap.put(new Item(2, "222"), 2);
lruMap.put(new Item(3, "333"), 3);

lruMap.put(new Item(4, "444"), 4);
System.out.println(lruMap);

lruMap.put(new Item(5, "555"), 5);
System.out.println(lruMap);
}

}

二、常用算法封装

1.排序算法

对集合类排序时，首先将其转成数组，然后通过Arrays.sort方法进行归并排序。
学过算法都知道快速排序是需要额外空间更少，执行更快，这里之所以选取归并
排序是因为它是稳定的，不会破坏相同元素之间的相对顺序。

源码如下：

2.查找算法

对于实现了RandomAccess的数据结构，也就是可以在O(1)时间内定位元素，
那么查找算法将采用直接下标定位的二分查找，在log(N)时间内找到要查找的元素。
否则将通过一个迭代器不断前后移动来定位二分后的位置，实现一种低效些的二分
查找。

源码如下：

indexedBinarySearch和iteratorBinarySearch就是查找算法的两种策略。两个方法的
唯一差别就是定位元素的位置。在indexedBinarySearch方法中，直接通过list.get获得，
而iteratorBinarySearch是通过list上的迭代器不断移动来获得的。

RandomAccess接口的继承层次：

所以对于ArrayList就可以直接通过下标来定位元素，实现二分查找查找。
而对于LinkedList链表，就只能通过iterator不断移动来定位了，显然我们
是没法在O(1)时间内定位链表中的任意元素。

另外注意对于size小于BINARYSEARCH_THRESHOLD(5000)的非RandomAccess数据结构，
也是会采用indexedBinarySearch策略。也就是说当长度小于5000，不通过迭代器而是每次
都从头向后定位到中间的元素的效率是可以接受的。

作者：dc_726

Java温故知新 - 集合类 (二)