Java上的跳過列表擴展AbstractMap

Question

我需要在java中實現跳過列表。我知道skip list是如何工作的，但我需要擴展AbstractMap。因此類SkipList會是什麼樣子

public class SkipList<K extends Comparable<K>,V> extends AbstractMap<K,V> { 
public SkipList(int levels) { 
    // ... 
    } 
// ... 
} 

我不明白，我怎麼需要擴展AbstractMap

Answer 1

SkipList用於快速搜索，通常O(logn)時間複雜度。標準的JDK沒有實現它。雖然ConcurrentSkipListMap使用SkipList數據結構來實現，你可以參考它的源代碼：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/concurrent/ConcurrentSkipListMap.java#ConcurrentSkipListMap

這裏是另一個很好的例子：https://codereview.stackexchange.com/questions/71432/custom-skiplist-implementation-in-java