건너뛰기 목록의 Java 구현 공유 예
- 黄舟원래의
- 2017-09-19 11:44:201428검색
이 글은 주로 Java 프로그래밍에서 점프 테이블의 개념과 구현 원리를 소개하고, 그 구조에 대해 간략하게 설명하며, 도움이 필요한 친구들이 배울 수 있습니다.
스킵 연결 목록은 병렬 연결 목록을 기반으로 한 무작위 데이터 구조입니다. 효율성은 이진 검색 트리(대부분의 작업에 O(log n) 평균 시간 필요)와 비슷하며 동시 알고리즘에 적합합니다.
기본적으로 점프 목록은 순서가 지정된 연결 목록에 추가 정방향 링크를 추가합니다. 추가는 무작위 방식으로 수행되므로 목록에서 검색하면 목록의 일부(따라서 이름)를 빠르게 건너뛸 수 있습니다. 모든 작업은 로그 무작위 시간으로 수행되었습니다.
구현 원리:
점프 테이블의 구조는 다음과 같습니다. 하위 레이어에 10개의 노드가 있는 경우 하위 레이어의 상위 레이어에는 이론적으로 5개의 노드가 있고 상위 레이어에는 2개 또는 3개의 노드가 있습니다. 이론상 다음 상위 레벨에는 이론적으로 1개의 노드가 있습니다. 따라서 여기에서 각 레이어의 노드 수가 다음 레이어 요소의 1/2이라는 것을 알 수 있습니다. 여기에서 삽입 시 상위 레이어의 요소 수가 다음 레이어 요소 수의 1/2이 되도록 보장하면 점프 목록이 이상적인 점프 목록이 될 수 있음을 알 수 있습니다. 그러면 삽입할 때 상위 요소 수가 하위 요소 수의 1/2이 되도록 어떻게 보장할 수 있습니까? 동전을 던지는 것으로 간단하게 해결할 수 있습니다. 확률이 1/2이면 다음으로 낮은 레벨에 들어갈 것이므로 동전을 던지면 두 번째에 비해 앞면이 삽입됩니다. 가장 낮은 레벨에서도 여전히 1/2의 삽입 확률이 있으므로 동전을 계속 던집니다. 비유하자면 소수 X가 n번째 레이어에 삽입될 확률은 (1/2)n번입니다. 이런 방식으로 점프 목록에 요소를 삽입할 수 있습니다.
제가 스킵 테이블의 데이터 구조를 처음 알게 된 것은 약 1년 전이었지만(이 말을 하면 수많은 동포들에게 멸시를 받았을 것입니다), 어떻게 구현해야 할지 몰랐습니다. 그 당시 나에게 가장 인상 깊었던 것은 Skip List - Implement(Java)에 대한 기사였습니다. 왜냐하면 이 기사에서 Skip List의 구현이 가장 이해하기 쉽기 때문입니다. 건너뛰기 목록에 대해 처음으로 알게 된 것은 바로 이 기사였습니다. 그래서 여기 이 글의 소유자에게 정말 감사하다는 말씀을 전하고 싶습니다. 1년 후, 시계 점핑에 대한 나의 이해가 다시 모호하다는 것을 알게 되었고, 그래서 이 글이 가장 먼저 떠올랐습니다. 오늘 이 글을 다시 읽어보고 거기에 나와있지 않은 삭제방법을 구현해봤습니다. 그리고 제네릭이 추가되었지만 제네릭은 값에 제네릭만 사용하고 키에 대한 원본 텍스트에서는 여전히 문자열 유형을 사용합니다. 따라서 여전히 상대적으로 단순하고 제한적입니다. 제가 글을 올리는 이유는 Skip List에 대한 이해를 높이고 알림을 제공하기 위함입니다. 원문 링크는 아까 말씀드린 대로 사실 원글 작성자가 누군지 모르기 때문에 조용히 감사 인사를 전하고 싶습니다. 물론, 원저작자가 제가 불쾌하거나 침해적인 행위를 했다고 판단할 경우 해당 게시물을 즉시 삭제하겠습니다.
스킵 테이블의 정의와 소개는 원문을 참조하세요. 원본 코드는 여기에 직접 제공됩니다. 여기에 원본 코드와 원문의 유일한 차이점은 원문에 나와 있지 않은 삭제 방법을 여기에 제공했다는 것입니다(원문은 실제로 영어 기사를 참조한 것이며, 영문 기사에서는 삭제 방법을 나중에 발견했는데, 영문 기사와 비교하면 코드가 약간 중복되어 있습니다. 여기에 게시된 삭제 방법은 제가 직접 구현한 삭제 방법입니다. 구현이 미흡할 수 있으니 여러분의 비판과 수정도 부탁드립니다! ! !
1 건너뛰기 목록의 각 요소(키-값 쌍)에 대한 캡슐화 클래스 SkipListEntry.java
public class SkipListEntry<v>
{
public String key;
public V value;
public int pos; // 主要为了打印 链表用
public SkipListEntry<v deep="6"> up, down, left, right; // 上下左右 四个指针
public static String negInf = new String("-oo"); // 负无穷
public static String posInf = new String("+oo"); // 正无穷
public SkipListEntry(String k, V v)
{
key = k;
value = v;
up = down = left = right = null;
}
public V getValue()
{
return value;
}
public String getKey()
{
return key;
}
public V setValue(V val)
{
V oldValue = value;
value = val;
return oldValue;
}
@SuppressWarnings("unchecked")
public boolean equals(Object o)
{
SkipListEntry<v> entry;
try
{
entry = (SkipListEntry<v>) o; // 检测类型
} catch (ClassCastException ex)
{
return false;
}
return (entry.getKey() == key) && (entry.getValue().equals(value));
}
public String toString()
{
return "(" + key + "," + value + ")";
}
}2 건너뛰기 목록의 특정 구현(추가, 삭제, 수정 및 확인 포함)
import java.util.Random;
/**
* 跳表的一种简单实现。key只能为字符串类型，value可以为任意对象类型
* @param <v>
* @author xxx 2017年2月14日 下午9:42:06
* @version v1.0
*/
public class SkipList<v>
{
public SkipListEntry<v> head; // 顶层的第一个元素
public SkipListEntry<v> tail; // 顶层的最后一个元素
public int size; // 跳跃表中的元素个数
public int height; // 跳跃表的高度
public Random flag; // 投掷硬币
/**
* 默认构造函数
* @author xxx 2017年2月14日 下午9:32:22
* @since v1.0
*/
public SkipList()
{
head = new SkipListEntry<v>(SkipListEntry.negInf, null);
tail = new SkipListEntry<v>(SkipListEntry.posInf, null);
head.right = tail;
tail.left = head;
size = 0;
height = 0;
flag = new Random();
}
/**
* 返回元素的个数
* @return
* @author xxx 2017年2月14日 下午9:35:22
* @since v1.0
*/
public int size()
{
return size;
}
/**
* 判断跳表中的元素个数是否为零
* @return
* @author xxx 2017年2月14日 下午9:35:52
* @since v1.0
*/
public boolean isEmpty()
{
return (size == 0);
}
/**
* 从最顶层的第一个元素，也即head元素开始查找，直到找到第0层、要插入的位置前面的那个key
* @param k
* @return
* @author xxx 2017年2月14日 下午9:42:12
* @since v1.0
*/
private SkipListEntry<v> findEntry(String k)
{
SkipListEntry<v> p = head;
while (true)
{
/*
* 一直向右找，例: k=34。 10 ---> 20 ---> 30 ---> 40 ^ | p 会在30处停止
*/
while (p.right.key != SkipListEntry.posInf && p.right.key.compareTo(k) <= 0)
{
p = p.right;
}
// 如果还有下一层，就到下一层继续查找
if (p.down != null)
{
p = p.down;
} else
{
break; // 到了最下面一层 就停止查找
}
}
return p; // p.key <= k
}
/** 返回和key绑定的值 */
public V get(String k)
{
SkipListEntry<v> p = findEntry(k);
if (k.equals(p.getKey()))
{
return p.value;
} else
{
return null;
}
}
/**
* 往跳表中插入一个键值对，如果键已经存在，则覆盖相应的值并返回旧值
* @param k
* @param v
* @return
* @author xxx 2017年2月14日 下午9:48:54
* @since v1.0
*/
public V put(String k, V v)
{
System.out.println("-----插入[" + k + "]之前的跳跃表是:-----");
printHorizontal();
SkipListEntry<v> p, q;
p = findEntry(k);
if (k.equals(p.getKey()))
{
V old = p.value;
p.value = v;
return old;
}
q = new SkipListEntry<v>(k, v);
q.left = p;
q.right = p.right;
p.right.left = q;
p.right = q;
int currentLevel = 0; // 当前层 currentLevel = 0
// 随机值小于0.5，则插入的键值对对应的键需要在上一层建立关联，同时有可能增加跳表的高度
while (flag.nextDouble() < 0.5)
{
// 如果超出了高度，需要重新建一个顶层
if (currentLevel >= height)
{
SkipListEntry<v> p1, p2;
height = height + 1;
p1 = new SkipListEntry<v>(SkipListEntry.negInf, null);
p2 = new SkipListEntry<v>(SkipListEntry.posInf, null);
p1.right = p2;
p1.down = head;
p2.left = p1;
p2.down = tail;
head.up = p1;
tail.up = p2;
head = p1;
tail = p2;
}
while (p.up == null)
{
p = p.left;
}
p = p.up;
SkipListEntry<v> e;
/*
* 注意，本实现中只有第0层的链表持有键对应的值，1 ~ height 层中的SkipListEntry对象
* 仅仅持有键的引用，值为空，以便节省空间。
*/
e = new SkipListEntry<v>(k, null);
e.left = p;
e.right = p.right;
e.down = q;
p.right.left = e;
p.right = e;
q.up = e;
q = e; // q 进行下一层迭代
currentLevel = currentLevel + 1; // 当前层 +1
}
// 插入一个键值对后总数加1
size = size + 1;
System.out.println("-----插入[" + k + "]之后的跳跃表是:-----");
printHorizontal();
return null;
}
/**
* 根据键删除键值对
* @param key
* @return
* @author xxx 2017年2月14日 下午10:08:17
* @since v1.0
*/
public void remove(String key)
{
SkipListEntry<v> p = findEntry(key);
if(!p.getKey().equals(key)) {
return;
}
//删除元素后重新关联，同时使被删除的对象游离，便于垃圾回收
p.left.right = p.right;
p.right.left = p.left;
p.right = null;
p.left = null;
//自底向上，使所有键等于key的SkipListEntry对象左右两个方向的引用置空
while(p.up != null) {
p = p.up;
p.left.right = p.right;
p.right.left = p.left;
p.right = null;
p.left = null;
}
//自顶向下，使所有键等于key的SkipListEntry对象上下两个方向的引用置空
while(p.down != null) {
SkipListEntry<v> temp = p.down;
p.down = null;
temp.up = null;
p = temp;
}
/*
* 删除元素后，如果顶层的链表只有head和tail两个元素，则删除顶层。
* 删除顶层以后最新的顶层如果依然只有head和tail两个元素，则也要被删除，以此类推。
*/
while(head.right.key == tail.key && height > 0) {
SkipListEntry<v> p1, p2;
p1 = head.down;
p2 = tail.down;
head.right = null;
head.down = null;
tail.left = null;
tail.down = null;
p1.up = null;
p2.up = null;
head = p1;
tail = p2;
height = height - 1;
}
//成功移除一个元素，大小减1
size = size - 1;
System.out.println("-----删除[" + key + "]后的跳跃表是:-----");
printHorizontal();
}
/**
* 打印出跳表的图示结构(水平方向)
* @author xxx 2017年2月14日 下午10:35:36
* @since v1.0
*/
public void printHorizontal()
{
String s = "";
int i;
SkipListEntry<v> p;
p = head;
while (p.down != null)
{
p = p.down;
}
i = 0;
while (p != null)
{
p.pos = i++;
p = p.right;
}
p = head;
while (p != null)
{
s = getOneRow(p);
System.out.println(s);
p = p.down;
}
}
private String getOneRow(SkipListEntry<v> p)
{
String s;
int a, b, i;
a = 0;
s = "" + p.key;
p = p.right;
while (p != null)
{
SkipListEntry<v> q;
q = p;
while (q.down != null)
q = q.down;
b = q.pos;
s = s + " <-";
for (i = a + 1; i < b; i++)
s = s + "--------";
s = s + "> " + p.key;
a = b;
p = p.right;
}
return s;
}
/**
* 打印出跳表的图示结构(垂直方向)
* @author xxx 2017年2月14日 下午10:35:36
* @since v1.0
*/
public void printVertical()
{
String s = "";
SkipListEntry<v> p;
p = head;
while (p.down != null)
p = p.down;
while (p != null)
{
s = getOneColumn(p);
System.out.println(s);
p = p.right;
}
}
private String getOneColumn(SkipListEntry<v> p)
{
String s = "";
while (p != null)
{
s = s + " " + p.key;
p = p.up;
}
return (s);
}
}3 테스트
public class Test
{
public static void main(String[] args)
{
SkipList<String> s = new SkipList<String>();
s.put("ABC", "");
s.put("DEF", "");
s.put("KLM", "");
s.put("HIJ", "");
s.put("GHJ", "");
s.put("AAA", "");
s.remove("ABC");
s.remove("DEF");
s.remove("KLM");
s.remove("HIJ");
s.remove("GHJ");
s.remove("AAA");
s.put("ABC", "");
s.put("DEF", "");
s.put("KLM", "");
s.put("HIJ", "");
s.put("GHJ", "");
s.put("AAA", "");
}
}
//运行测试后结果示例如下（注意：由于跳表的特性，每次运行结果都不一样）
-----插入[ABC]之前的跳跃表是:-----
-oo <-> +oo
-----插入[ABC]之后的跳跃表是:-----
-oo <-> ABC <-> +oo
-oo <-> ABC <-> +oo
-----插入[DEF]之前的跳跃表是:-----
-oo <-> ABC <-> +oo
-oo <-> ABC <-> +oo
-----插入[DEF]之后的跳跃表是:-----
-oo <---------> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-----插入[KLM]之前的跳跃表是:-----
-oo <---------> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-----插入[KLM]之后的跳跃表是:-----
-oo <---------> DEF <-> KLM <-> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-----插入[HIJ]之前的跳跃表是:-----
-oo <---------> DEF <-> KLM <-> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-----插入[HIJ]之后的跳跃表是:-----
-oo <---------> DEF <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo
-----插入[GHJ]之前的跳跃表是:-----
-oo <---------> DEF <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo
-----插入[GHJ]之后的跳跃表是:-----
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <---------> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----插入[AAA]之前的跳跃表是:-----
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <---------> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----插入[AAA]之后的跳跃表是:-----
-oo <-------------------------> GHJ <-----------------> +oo
-oo <-------------------------> GHJ <-----------------> +oo
-oo <-------------------------> GHJ <-----------------> +oo
-oo <-------------------------> GHJ <-----------------> +oo
-oo <-------------------------> GHJ <-----------------> +oo
-oo <-> AAA <-----------------> GHJ <-----------------> +oo
-oo <-> AAA <---------> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----删除[ABC]后的跳跃表是:-----
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-> AAA <---------> GHJ <-----------------> +oo
-oo <-> AAA <-> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----删除[DEF]后的跳跃表是:-----
-oo <---------> GHJ <-----------------> +oo
-oo <---------> GHJ <-----------------> +oo
-oo <---------> GHJ <-----------------> +oo
-oo <---------> GHJ <-----------------> +oo
-oo <---------> GHJ <-----------------> +oo
-oo <-> AAA <-> GHJ <-----------------> +oo
-oo <-> AAA <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> GHJ <-> HIJ <-> KLM <-> +oo
-----删除[KLM]后的跳跃表是:-----
-oo <---------> GHJ <---------> +oo
-oo <---------> GHJ <---------> +oo
-oo <---------> GHJ <---------> +oo
-oo <---------> GHJ <---------> +oo
-oo <---------> GHJ <---------> +oo
-oo <-> AAA <-> GHJ <---------> +oo
-oo <-> AAA <-> GHJ <---------> +oo
-oo <-> AAA <-> GHJ <---------> +oo
-oo <-> AAA <-> GHJ <-> HIJ <-> +oo
-----删除[HIJ]后的跳跃表是:-----
-oo <---------> GHJ <-> +oo
-oo <---------> GHJ <-> +oo
-oo <---------> GHJ <-> +oo
-oo <---------> GHJ <-> +oo
-oo <---------> GHJ <-> +oo
-oo <-> AAA <-> GHJ <-> +oo
-oo <-> AAA <-> GHJ <-> +oo
-oo <-> AAA <-> GHJ <-> +oo
-oo <-> AAA <-> GHJ <-> +oo
-----删除[GHJ]后的跳跃表是:-----
-oo <-> AAA <-> +oo
-oo <-> AAA <-> +oo
-oo <-> AAA <-> +oo
-oo <-> AAA <-> +oo
-----删除[AAA]后的跳跃表是:-----
-oo <-> +oo
-----插入[ABC]之前的跳跃表是:-----
-oo <-> +oo
-----插入[ABC]之后的跳跃表是:-----
-oo <-> ABC <-> +oo
-----插入[DEF]之前的跳跃表是:-----
-oo <-> ABC <-> +oo
-----插入[DEF]之后的跳跃表是:-----
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-----插入[KLM]之前的跳跃表是:-----
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-----插入[KLM]之后的跳跃表是:-----
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-----插入[HIJ]之前的跳跃表是:-----
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-----插入[HIJ]之后的跳跃表是:-----
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-> HIJ <---------> +oo
-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo
-----插入[GHJ]之前的跳跃表是:-----
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-> HIJ <---------> +oo
-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo
-----插入[GHJ]之后的跳跃表是:-----
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <---------> HIJ <---------> +oo
-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----插入[AAA]之前的跳跃表是:-----
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <---------> HIJ <---------> +oo
-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----插入[AAA]之后的跳跃表是:-----
-oo <-----------------> DEF <-------------------------> +oo
-oo <-----------------> DEF <-------------------------> +oo
-oo <-----------------> DEF <-------------------------> +oo
-oo <-----------------> DEF <---------> HIJ <---------> +oo
-oo <-> AAA <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo요약
위 내용은 건너뛰기 목록의 Java 구현 공유 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
성명：
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.