JAva実装ホップテーブル
60534 ワード
前言
最近、ネットでredisがなぜバランスツリーではなくジャンプメーターを使っているのかを見て、好奇心を持って見ました.ジャンプテーブルのコンセプトはネット上にありますが、ここでは後述しません.総じて、ホップテーブルは、バランスツリーよりも簡単であり、範囲検索の効率は少なくともバランスツリーと同じである.同時にskiplistはハッシュテーブル、バランスツリーの2つの検索に使用される一般的で効率的なデータ構造に分類できません.だから1つを実現しました(主に実現の簡単さを見ました).
コード#コード#
ネット上ではホップテーブルを実現する例が多く見られたが,いずれもdownで下層を表すため,多くのインスタンスノードが同じデータを表す必要があり,より大きな空間浪費をもたらしたため,自分で配列で層を実現し,redisソースコードにはspan属性があるが,スパンをどのように実現するかは考えられなかったため,しばらくこの属性は用いられなかった.そして挿入は最適化できるが、書くのがおっくうだ...
テスト
仮想マシンの3つのパラメータはそれぞれ -XX:AutoBoxCacheMax=1000000 -Xmx1g -Xms1g
最初のパラメータはInteger自動箱詰めキャッシュの最大値であり、テスト時にIntegerを繰り返し作成しないために、開始前にIntegerを作成してキャッシュします.2番目と3番目のパラメータはjavaスタックのサイズを指定し、発見空間申請が何回も失敗したことを指定しなかった後、fullGCを実行するとLinkedListの作成がSkipListよりも遅くなるため、スタックのサイズを調整した.
SkipListの挿入はLinkedListよりも時間がかかることがわかりますが、検索が少しでも速くなり、挿入にかかる時間は完全に受け入れられます.
最近、ネットでredisがなぜバランスツリーではなくジャンプメーターを使っているのかを見て、好奇心を持って見ました.ジャンプテーブルのコンセプトはネット上にありますが、ここでは後述しません.総じて、ホップテーブルは、バランスツリーよりも簡単であり、範囲検索の効率は少なくともバランスツリーと同じである.同時にskiplistはハッシュテーブル、バランスツリーの2つの検索に使用される一般的で効率的なデータ構造に分類できません.だから1つを実現しました(主に実現の簡単さを見ました).
コード#コード#
/**
* O(logn)
*
* @author FenG
* @date 2019-10-25 19:36:28
*/
public class SkipList<T> {
// ， 32， 2^32-1
private static final int MAX_LEVEL = 32;
private final SkipNode HEAD;
private final Random random = new Random();
private int level = 0;
private int size = 0;
public SkipList() {
this(4);
}
public SkipList(int level) {
this.HEAD = new SkipNode<T>(level);
this.level = level;
}
/**
* score
*
* @param score
* @return
*/
public T get(double score) {
SkipNode<T> node = doGet(score);
return node == null ? null : node.value;
}
/**
* score start end
*
* @param start
* @param end
* @return score start end
*/
public SubList<T> range(int start, int end) {
if (end < start) {
throw new IllegalArgumentException("End should bigger than start");
}
SkipNode<T> p = HEAD;
int lev = level - 1;
boolean found = false;
while (lev >= 0 && p != null) {
if (p.level[lev].forward == null) {
lev--;
continue;
}
if (p.level[lev].forward.score < start) {
p = p.level[lev].forward;
} else {
p = p.level[lev].forward;
found = true;
break;
}
}
if (!found) {
return SubList.EMPTY_LIST;
}
int len = 0;
LinkedList<T> list = new LinkedList<T>();
while (p != null) {
if (p.score > end) {
break;
}
list.add(p.value);
p = p.level[0].forward;
}
return new SubList<T>((T[]) list.toArray());
}
/**
* score value
*
* @param score
* @param value
*/
public void put(double score, T value) {
//
SkipNode<T> node = null;
node = doGet(score);
if (node != null) {
// ， ， value
node.value = value;
} else {
// ， ， doGet(double)
// ： ， Level ，
// Level forward
// ， doGet(double) ，
int lev = randomLevel();
SkipNode<T> newNode = new SkipNode<T>(score, value, lev);
if (lev > level) {
//
Level[] src = HEAD.level;
Level[] dest = new Level[lev];
System.arraycopy(src, 0, dest, 0, level);
while (level < lev) {
dest[level] = new Level();
dest[level].forward = newNode;
level++;
}
HEAD.level = dest;
}
SkipNode<T> p = HEAD;
lev = level - 1;
int h = newNode.level.length - 1;
while (lev >= 0) {
if (p.level[lev].forward != null && p.level[lev].forward.score < score) {
p = p.level[lev].forward;
} else {
if (lev > h) {
lev--;
continue;
}
if (p.level[lev].forward == newNode) {
// forward
// forward newNode（while (level < lev) ）,
// newNode.level[lev].forward ，
// p.level[lev].forward newNode
lev--;
continue;
}
newNode.level[lev].forward = p.level[lev].forward;
p.level[lev].forward = newNode;
lev--;
}
}
size++;
}
}
/**
* score
*
* @param score
*/
public void delete(double score) {
SkipNode p = HEAD;
int lev = level - 1;
boolean deleted = false;
while (lev >= 0 && p != null) {
if (p.level[lev].forward == null) {
lev--;
continue;
}
if (p.level[lev].forward.score == score) {
deleted = true;
// ， ，
p.level[lev].forward = p.level[lev].forward.level[lev].forward;
lev--;
} else if (p.level[lev].forward.score < score) {
p = p.level[lev].forward;
} else {
lev--;
}
}
if (deleted) {
size--;
}
}
public int size() {
return size;
}
@Override
public String toString() {
if (size <= 0) {
return "SkipList{}";
}
StringBuilder sb = new StringBuilder("SkipList{
");
SkipNode p = HEAD;
int lev = level - 1;
while (lev >= 0) {
while (p != null) {
sb.append(p.value);
sb.append(" ");
p = p.level[lev].forward;
}
sb.append("
");
lev--;
p = HEAD;
}
sb.append("}");
return sb.toString();
}
private int randomLevel() {
int lev = 1;
while ((random.nextInt() & 1) == 0 && lev < MAX_LEVEL) {
lev++;
}
// 1
return lev;
}
private SkipNode<T> doGet(double score) {
SkipNode<T> p = HEAD;
int lev = level - 1;
while (lev >= 0 && p != null) {
if (p.score == score) {
return p;
}
if (p.level[lev].forward == null) {
// ，
lev--;
continue;
}
if (p.level[lev].forward.score > score) {
// ，
lev--;
} else {
p = p.level[lev].forward;
}
}
return null;
}
private static class SubList<E> extends AbstractList<E> {
private static final SubList EMPTY_LIST = new SubList();
E[] element;
int size;
public SubList() {
}
public SubList(E[] element) {
this.element = element;
this.size = this.element.length;
}
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalStateException("Array index is out of range: " + index);
}
return element[index];
}
@Override
public int size() {
return size;
}
@Override
public String toString() {
if (size <= 0) {
return "SubList{}";
}
StringBuilder sb = new StringBuilder("SubList{");
for (E e : element) {
sb.append(e);
sb.append(", ");
}
sb.delete(sb.length() - 2, sb.length());
sb.append("}");
return sb.toString();
}
}
private class SkipNode<E> {
Level[] level;
double score;
E value;
SkipNode<E> backward;
SkipNode(int lev) {
initLevel(lev);
this.score = Double.MIN_VALUE;
}
SkipNode(double score, E value, int lev) {
initLevel(lev);
this.value = value;
this.score = score;
}
private void initLevel(int lev) {
level = new Level[lev];
for (int i = 0; i < lev; i++) {
level[i] = new Level();
}
}
}
private class Level<E> {
SkipNode<E> forward;
//
// int span;
}
}
ネット上ではホップテーブルを実現する例が多く見られたが,いずれもdownで下層を表すため,多くのインスタンスノードが同じデータを表す必要があり,より大きな空間浪費をもたらしたため,自分で配列で層を実現し,redisソースコードにはspan属性があるが,スパンをどのように実現するかは考えられなかったため,しばらくこの属性は用いられなかった.そして挿入は最適化できるが、書くのがおっくうだ...
テスト
/**
* ：
* -XX:AutoBoxCacheMax=1000000 -Xmx1g -Xms1g
* Integer
*/
@Test
public void skipListCompareToLinkedList() {
Random random = new Random();
SkipList<Integer> skipList = new SkipList<Integer>();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
// IntegerCache ，
Integer.valueOf(1);
System.out.println("------------- -------------");
long start = System.currentTimeMillis();
for(int i = 0; i < 1000000; i++) {
skipList.put(i, i);
}
long end = System.currentTimeMillis();
System.out.println(" skipList : " + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
linkedList.add(i);
}
end = System.currentTimeMillis();
System.out.println(" linkedList : " + (end - start));
System.out.println("------------- -------------");
start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
skipList.get(random.nextInt(1000000));
}
end = System.currentTimeMillis();
System.out.println("skipList: " + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
linkedList.get(random.nextInt(1000000));
}
end = System.currentTimeMillis();
System.out.println("linkedList: " + (end - start));
}
仮想マシンの3つのパラメータはそれぞれ
最初のパラメータはInteger自動箱詰めキャッシュの最大値であり、テスト時にIntegerを繰り返し作成しないために、開始前にIntegerを作成してキャッシュします.2番目と3番目のパラメータはjavaスタックのサイズを指定し、発見空間申請が何回も失敗したことを指定しなかった後、fullGCを実行するとLinkedListの作成がSkipListよりも遅くなるため、スタックのサイズを調整した.
------------- -------------
skipList : 545
linkedList : 25
------------- -------------
skipList: 19
linkedList: 7175
SkipListの挿入はLinkedListよりも時間がかかることがわかりますが、検索が少しでも速くなり、挿入にかかる時間は完全に受け入れられます.