Beispiel für die gemeinsame Nutzung einer Java-Implementierung der Sprungliste

Dieser Artikel stellt hauptsächlich das Konzept und das Implementierungsprinzip der Sprungtabelle in der Java-Programmierung vor und beschreibt kurz deren Struktur. Es hat einen gewissen Referenzwert und Freunde in Not können etwas darüber erfahren.

Die verknüpfte Sprungliste ist eine randomisierte Datenstruktur, die auf parallel verknüpften Listen basiert. Ihre Effizienz ist vergleichbar mit einem binären Suchbaum (der für die meisten Operationen eine durchschnittliche Zeit von O(log n) erfordert) und ist für gleichzeitige Algorithmen geeignet. .

Grundsätzlich fügt eine Sprungliste einer geordneten verknüpften Liste zusätzliche Weiterleitungslinks hinzu. Das Hinzufügen erfolgt auf zufällige Weise, sodass bei der Suche in der Liste schnell Teile der Liste übersprungen werden können ). Alle Operationen wurden mit logarithmisch randomisierten Zeiten durchgeführt.

Implementierungsprinzip:

Die Struktur der Sprungtabelle ist: Wenn es 10 Knoten in der unteren Schicht gibt, dann wird die obere Schicht der unteren Schicht theoretisch vorhanden sein 5 Knoten, und dann gibt es theoretisch 2 oder 3 Knoten auf einer Ebene und 1 Knoten auf der nächsten Ebene. Von hier aus ist also ersichtlich, dass die Anzahl der Knoten in jeder Schicht die Hälfte der Elemente in der nächsten Schicht beträgt und so weiter. Von hier aus können wir sehen, dass unsere Sprungliste zu einer idealen Sprungliste werden kann, solange wir beim Einfügen sicherstellen, dass die Anzahl der Elemente in der oberen Ebene die Hälfte der Anzahl der Elemente in der nächsten Ebene beträgt. Wie können wir also sicherstellen, dass die Anzahl der oberen Elemente beim Einfügen halb so groß ist wie die Anzahl der unteren Elemente? Es kann einfach gelöst werden, indem man eine Münze wirft. Angenommen, das Element mit der Wahrscheinlichkeit 1/2 wird in die nächstniedrigere Schicht geworfen, also werfen wir eine Münze ein Die Wahrscheinlichkeit, dass die Primzahl X in die n-te Schicht eingefügt wird, beträgt also (1/2) n-mal. Auf diese Weise können wir ein Element in die Sprungliste einfügen.

Das erste Mal, dass ich etwas über die Datenstruktur von Sprungtabellen gelernt habe, war vor etwa einem Jahr (ich wurde wahrscheinlich von unzähligen Landsleuten verachtet, als ich das sagte), aber ich wusste nicht, wie ich es umsetzen sollte. Was mich damals am meisten beeindruckte, war ein Artikel über Skip List – Implementierung (Java), da die Implementierung von Skip List in diesem Artikel am einfachsten zu verstehen ist. Durch diesen Artikel habe ich zum ersten Mal mehr über Skip List erfahren. Deshalb möchte ich dem Eigentümer dieses Artikels hier wirklich danken. Ein Jahr später stellte ich fest, dass mein Verständnis des Uhrenspringens erneut vage war, sodass mir dieser Artikel als Erstes in den Sinn kam. Ich habe diesen Artikel heute noch einmal gelesen und die darin nicht angegebene Löschmethode implementiert. Und generische Elemente hinzugefügt, aber generische Elemente verwenden nur generische Elemente für den Wert und verwenden weiterhin den String-Typ im Originaltext für den Schlüssel. Es ist also immer noch relativ einfach und begrenzt. Der Grund, warum ich es poste, besteht darin, mein Verständnis der Skip List zu verbessern und als Erinnerung zu dienen. Der Link zum Originalartikel ist wie bereits erwähnt. Ich weiß eigentlich nicht, wer der Autor des Originalartikels ist, deshalb möchte ich mich nur im Stillen bedanken. Wenn der ursprüngliche Autor der Meinung ist, dass ich etwas Beleidigendes oder Verstoßes begangen habe, werde ich den Beitrag natürlich sofort löschen.

Für die Definition und Einführung von Skip-Tabellen können sich die Leser auf den Originaltext beziehen. Der Originalcode wird hier direkt angegeben. Der einzige Unterschied zwischen dem Originalcode hier und dem Originaltext besteht darin, dass ich hier die Löschmethode angegeben habe, die im Originaltext nicht angegeben ist (der Originaltext bezieht sich tatsächlich auf einen englischen Artikel, und der Der englische Artikel gibt an, dass ich die Löschmethode erst später entdeckt habe, aber im Vergleich zum englischen Artikel ist der Code etwas redundant. Die hier veröffentlichte Löschmethode ist die Löschmethode, die ich selbst implementiert habe. Es ist möglicherweise schlecht umgesetzt, daher fordere ich alle auf, mich zu kritisieren und zu korrigieren! ! !

1 Die Kapselungsklasse 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 Spezifische Implementierung der Skip List (einschließlich Hinzufügen, Löschen, Ändern und Überprüfen)

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 Test

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

Zusammenfassung

Das obige ist der detaillierte Inhalt vonBeispiel für die gemeinsame Nutzung einer Java-Implementierung der Sprungliste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!