Jump table implementation in Java

Introduction

Jump table is a data structure for storing a sorted list of elements with the help of a linked table hierarchy connected to a subsequence of elements. Jump table allows to handle item lookups in an efficient way. A jump table is a probabilistic data structure, which means that it skips several elements of the entire list, hence the name. We can think of a jump table as an extended version of a linked table. Similar to the way a linked table allows insertion, deletion and searching of elements, a jump table allows searching for elements, deleting elements from the list and inserting elements. It will contain a basic list with a set of elements that will maintain a linked hierarchy of subsequent elements.

Syntax

There is no specific syntax for jumping tables, but it has an algorithm. Before examining the algorithm, we need to examine the types of basic jump table operations.

  1. insertion operations: in jump tables, used to add a new node to a specific position in a specific situation
  2. search operation: in jump table, used to search for a specific node
  3. Delete operation: in a jump table, used to delete a node in a specific case

Let’s see how the jump table works in an algorithmic way.

Insertion algorithm

Step 1: Determine the node level, since each element in the list is represented by a node, and randomly select the level of the node during insertion into the list

Step 2: Determine the level of the node according to the following steps

Step 3: Find the maximum level that is the upper limit of the level count in the jump table, which is determined by L(N)=logp/2N. This ensures that the random level will be greater than the maximum level

Step 4: Insert the next node starting from the highest level and compare the current node

Step 5: If the next node keypoint' is smaller than theinserted keypoint, then you can continue using the same level

Step 6: If next node key is greater than inserted key, then we need to store a pointer to the current node I and move down one level to continue the search.

Search algorithm

Step 1: Because searching for an element is very similar to searching for a point to insert an element in the jump table.

Step 2: If the next node key is smaller than the search key, then we can move forward on the same level

Step 3: If the next node key is greater than the inserted key, then we need to store a pointer to the current node I and move down one level to continue the search.

Step 4: At the lowest level, if the next element of the rightmost element has a key equal to the searched key, then we have found the key, otherwise this is a failure.

Deletion algorithm

Step 1: To delete any element, say k, first we need to locate the element in the jump table using the search algorithm.

Step 2: Once we have found the element using the search algorithm, the pointer rearrangement will remove the element from the list, just as we did in the single linked list.

Step 3: We need to rearrange the element next to the I not element k starting from the lowest level of the skip list.

Step 4: After removing the element, there may be a situation where there are no levels of the element, so we need to remove these levels by reducing the skip list levels.

Example: Skip Table in Java

  public class SkipListJava<K extends Comparable<K>, V> implements Iterable<K> {
            private int listsize;
            private double pb;
            protected static final Random randomGen = new Random();
            protected static final double DEFAULT_PB = 0.5;
            private NodeKeyValue<K, V> head;

            public SkipListJava() {
                this(DEFAULT_PB);
            }

            public SkipListJava(double pb) {
                this.head = new NodeKeyValue<K, V>(null, null, 0);
                this.pb = pb;
                this.listsize = 0;
            }

            public V get(K key) {
                checkKeyValid(key);
                NodeKeyValue<K, V> listnode = findNode(key);
                if (listnode.getKey().compareTo(key) == 0)
                    return listnode.getValue();
                else
                    return null;
            }

            public void add(K key, V value) {
                checkKeyValid(key);
                NodeKeyValue<K, V> listnode = findNode(key);
                if (listnode.getKey() != null && listnode.getKey().compareTo(key) == 0) {
                    listnode.setValue(value);
                    return;
                }
                NodeKeyValue<K, V> newlistNode = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
                horizontalInsertList(listnode, newlistNode);
                int curLevel = listnode.getLevel();
                int headlistLevel = head.getLevel();
                while (isBuildLevel()) {
                    if (curLevel >= headlistLevel) {
                        NodeKeyValue<K, V> newHeadEle = new NodeKeyValue<K, V>(null, null, headlistLevel + 1);
                        verticalLink(newHeadEle, head);
                        head = newHeadEle;
                        headlistLevel = head.getLevel();
                    }
                    while (listnode.getUp() == null) {
                        listnode = listnode.getPrevious();
                    }
                    listnode = listnode.getUp();
                    NodeKeyValue<K, V> tmp = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
                    horizontalInsertList(listnode, tmp);
                    verticalLink(tmp, newlistNode);
                    newlistNode = tmp;
                    curLevel++;
                }
                listsize++;
            }

            public void remove(K key) {
                checkKeyValid(key);
                NodeKeyValue<K, V> listnode = findNode(key);
                if (listnode == null || listnode.getKey().compareTo(key) != 0)
                    throw new NoSuchElementException("Key does not exist!");
                while (listnode.getDownList() != null)
                    listnode = listnode.getDownList();
                NodeKeyValue<K, V> previous = null;
                NodeKeyValue<K, V> next = null;
                for (; listnode != null; listnode = listnode.getUp()) {
                    previous = listnode.getPrevious();
                    next = listnode.getNext();
                    if (previous != null)
                        previous.setNext(next);
                    if (next != null)
                        next.setPreviousVal(previous);
                }
                while (head.getNext() == null && head.getDownList() != null) {
                    head = head.getDownList();
                    head.setUp(null);
                }
                listsize--;
            }

            public boolean contains(K key) {
                return get(key) != null;
            }

            public int listsize() {
                return listsize;
            }

            public boolean empty() {
                return listsize == 0;
            }

            protected NodeKeyValue<K, V> findNode(K key) {
                NodeKeyValue<K, V> listnode = head;
                NodeKeyValue<K, V> next = null;
                NodeKeyValue<K, V> down = null;
                K nodeKey = null;
                while (true) {
                    next = listnode.getNext();
                    while (next != null && lessThanEqual(next.getKey(), key)) {
                        listnode = next;
                        next = listnode.getNext();
                    }
                    nodeKey = listnode.getKey();
                    if (nodeKey != null && nodeKey.compareTo(key) == 0)
                        break;
                    down = listnode.getDownList();
                    if (down != null) {
                        listnode = down;
                    } else {
                        break;
                    }
                }
                return listnode;
            }

            protected void checkKeyValid(K key) {
                if (key == null)
                    throw new IllegalArgumentException("Key must be not null!");
            }

            protected boolean lessThanEqual(K a, K b) {
                return a.compareTo(b) <= 0;
            }

            protected boolean isBuildLevel() {
                return randomGen.nextDouble() < pb;
            }

            protected void horizontalInsertList(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
                b.setPreviousVal(a);
                b.setNext(a.getNext());
                if (a.getNext() != null)
                    a.getNext().setPreviousVal(b);
                a.setNext(b);
            }

            protected void verticalLink(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
                a.setDown(b);
                b.setUp(a);
            }

            @Override
            public String toString() {
                StringBuilder stringbuild = new StringBuilder();
                NodeKeyValue<K, V> listnode = head;
                while (listnode.getDownList() != null)
                    listnode = listnode.getDownList();
                while (listnode.getPrevious() != null)
                    listnode = listnode.getPrevious();
                if (listnode.getNext() != null)
                    listnode = listnode.getNext();
                while (listnode != null) {
                    stringbuild.append(listnode.toString()).append("\n");
                    listnode = listnode.getNext();
                }
                return stringbuild.toString();
            }

            @Override
            public Iterator<K> iterator() {
                return new SkipListIterator<K, V>(head);
            }

            protected static class SkipListIterator<K extends Comparable<K>, V> implements Iterator<K> {
                private NodeKeyValue<K, V> listnode;

                public SkipListIterator(NodeKeyValue<K, V> listnode) {
                    while (listnode.getDownList() != null)
                        listnode = listnode.getDownList();
                    while (listnode.getPrevious() != null)
                        listnode = listnode.getPrevious();
                    if (listnode.getNext() != null)
                        listnode = listnode.getNext();
                    this.listnode = listnode;
                }

                @Override
                public boolean hasNext() {
                    return this.listnode != null;
                }

                @Override
                public K next() {
                    K result = listnode.getKey();
                    listnode = listnode.getNext();
                    return result;
                }

                @Override
                public void remove() {
                    throw new UnsupportedOperationException();
                }
            }

            protected static class NodeKeyValue<K extends Comparable<K>, V> {
                private K key;
                private V value;
                private int skiplevel;
                private NodeKeyValue<K, V> up, down, next, previous;

                public NodeKeyValue(K key, V value, int skiplevel) {
                    this.key = key;
                    this.value = value;
                    this.skiplevel = skiplevel;
                }

                @Override
                public String toString() {
                    StringBuilder stringbuild = new StringBuilder();
                    stringbuild.append("Node[")
                            .append("key:");
                    if (this.key == null)
                        stringbuild.append("None");
                    else
                        stringbuild.append(this.key.toString());
                    stringbuild.append(", value:");
                    if (this.value == null)
                        stringbuild.append("None");
                    else
                        stringbuild.append(this.value.toString());
                    stringbuild.append("]");
                    return stringbuild.toString();
                }

                public K getKey() {
                    return key;
                }

                public void setKey(K key) {
                    this.key = key;
                }

                public V getValue() {
                    return value;
                }

                public void setValue(V value) {
                    this.value = value;
                }

                public int getLevel() {
                    return skiplevel;
                }

                public void setLevel(int skiplevel) {
                    this.skiplevel = skiplevel;
                }

                public NodeKeyValue<K, V> getUp() {
                    return up;
                }

                public void setUp(NodeKeyValue<K, V> up) {
                    this.up = up;
                }

                public NodeKeyValue<K, V> getDownList() {
                    return down;
                }

                public void setDown(NodeKeyValue<K, V> down) {
                    this.down = down;
                }

                public NodeKeyValue<K, V> getNext() {
                    return next;
                }

                public void setNext(NodeKeyValue<K, V> next) {
                    this.next = next;
                }

                public NodeKeyValue<K, V> getPrevious() {
                    return previous;
                }

                public void setPreviousVal(NodeKeyValue<K, V> previous) {
                    this.previous = previous;
                }
            }

            public static void main(String[] args) {
                SkipListJava<Integer, String> skip = new SkipListJava<>();
                for (int i = 20; i < 35; i++) {
                    skip.add(i, String.valueOf(i));
                }
                System.out.println(skip);
                assert skip.listsize() == 10;
                int count = 0;
                for (Integer i : skip)
                    assert i.equals(count++);
                skip.remove(23);
                System.out.println(skip);
                skip.remove(25);
                skip.remove(33);
                skip.remove(30);
                System.out.println(skip);
                skip.remove(28);
                skip.add(25, "25");
                System.out.println(skip);
                assert skip.listsize() == 0;
                assert skip.empty();
            }
        }

Summary

The concept of jump table is the same in any programming language and it is one of the main algorithms in data structures.