网站建站什么目录,桂林网站建设内容,环球资源网站,北京网站优化什么价格ArrayList和RandomAccess接口RandomAccess 接口Collections.binarySearch()源码总结RandomAccess 接口
首先#xff0c;RandomAccess接口是什么#xff0c;以下代码可见#xff1a;
public interface RandomAccess {
}RandomAccess接口其实是一个标记接口#xff0c;它只…
ArrayList和RandomAccess接口RandomAccess 接口Collections.binarySearch()源码总结RandomAccess 接口
首先RandomAccess接口是什么以下代码可见
public interface RandomAccess {
}RandomAccess接口其实是一个标记接口它只负责声明实现该接口的List支持快速随机访问主要目的是使算法能够在随机和顺序访问的list中表现的更加高效。
Collections.binarySearch()源码
我们来看Collections下的binarySearch方法的源码 public static Tint binarySearch(List? extends Comparable? super T list, T key) {if (list instanceof RandomAccess || list.size()BINARYSEARCH_THRESHOLD)return Collections.indexedBinarySearch(list, key);elsereturn Collections.iteratorBinarySearch(list, key);}我们可以看到在进行二分查找的时候list会先判断是否是RandomAccess也即是否实现了RandomAccess接口接着再调用想用的二分查找算法来进行其中: BINARYSEARCH_THRESHOLD Collections的一个常量5000它是二分查找的阀值。如果实现了RandomAccess接口的List执行indexedBinarySearch方法否则执行 iteratorBinarySearch方法。
分别看下这两个方法的实现: private static Tint indexedBinarySearch(List? extends Comparable? super T list, T key) {int low 0;int high list.size()-1;while (low high) {int mid (low high) 1;Comparable? super T midVal list.get(mid);int cmp midVal.compareTo(key);if (cmp 0)low mid 1;else if (cmp 0)high mid - 1;elsereturn mid; // key found}return -(low 1); // key not found}indexedBinarySearch 方法是直接通过list.get()方法来访问元素
private static Tint iteratorBinarySearch(List? extends Comparable? super T list, T key){int low 0;int high list.size()-1;ListIterator? extends Comparable? super T i list.listIterator();while (low high) {int mid (low high) 1;Comparable? super T midVal get(i, mid);int cmp midVal.compareTo(key);if (cmp 0)low mid 1;else if (cmp 0)high mid - 1;elsereturn mid; // key found}return -(low 1); // key not found}iteratorBinarySearch中是list.listIterator()来查找相应的元素
人们认识到随机访问和顺序访问之间的区别通常是模糊的。例如一些List实现提供了渐近线性访问时间如果它们在实践中获得了巨大但恒定的访问时间。这样的List实现通常应实现此接口。根据经验如果对于类的典型实例以下循环 for (int i0, nlist.size(); i n; i)list.get(i);会比下面这个更快 for (Iterator ilist.iterator(); i.hasNext(); )i.next();总结
若是集合的for循环访问数据比使用iterator访问来的高效快速那么最好去实现RandomAccess这个标记接口这样在一些框架代码中就可以根据是否实现了RandomAccess接口做出更好的决策方式
是因为它这个集合用for循环更快所以才实现RandomAccess接口注意不要搞反了
如有错误还请多多指教 转载或者引用本文内容请注明来源及原作者橘足轻重
