精华内容
下载资源
问答
  • 跳表

    2021-04-02 22:55:43
    跳表,在有序链表的基础上增加了"跳跃"的功能,使得有序链表的的搜索,删除,添加的平均时间复杂度是O(logn) Redis中的SortedSet,LevelDB中的MemTable都用到了跳表 Redis,LevelDB都是著名的Key-Value数据库 ...
    • 跳表,在有序链表的基础上增加了"跳跃"的功能,使得有序链表的的搜索,删除,添加的平均时间复杂度是O(logn)

    • Redis中的SortedSet,LevelDB中的MemTable都用到了跳表

    • Redis,LevelDB都是著名的Key-Value数据库

    • 跳表的搜索

    1. 从顶层链表的首元素开始,从左往右搜索,直到找到一个大于或等于目标的元素,或者到达当前链表的尾部
    2. 如果该元素等于目标元素,则表明该元素已被找到
    3. 如果该元素大于目标元素或已经到达链表的尾部,则退回当前层的前一个元素,然后转入下一层经行搜索
    import java.util.Comparator;
    public class SkipList<K, V> {
    	private static final int MAX_LEVEL = 32;
    	private static final double P = 0.25;
    	private int size;
    	private Comparator<K> comparator;
    	/**
    	 * 有效层数
    	 */
    	private int level;
    	/**
    	 * 不存放任何K-V
    	 */
    	private Node<K, V> first;
    	
    	public SkipList(Comparator<K> comparator) {
    		this.comparator = comparator;
    		first = new Node<>(null, null, MAX_LEVEL);
    	}
    	
    	public SkipList() {
    		this(null);
    	}
    	
    	public int size() {
    		return size;
    	}
    	
    	public boolean isEmpty() {
    		return size == 0;
    	}
    	
    	public V get(K key) {
    		keyCheck(key);
    	
    		
    		Node<K, V> node = first;
    		for (int i = level - 1; i >= 0; i--) {
    			int cmp = -1;
    			while (node.nexts[i] != null 
    					&& (cmp = compare(key, node.nexts[i].key)) > 0) {
    				node = node.nexts[i];
    			}
    
    			if (cmp == 0) return node.nexts[i].value;
    		}
    		return null;
    	}
    	
    	public V put(K key, V value) {
    		keyCheck(key);
    		
    		Node<K, V> node = first;
    		Node<K, V>[] prevs = new Node[level];
    		for (int i = level - 1; i >= 0; i--) {
    			int cmp = -1;
    			while (node.nexts[i] != null 
    					&& (cmp = compare(key, node.nexts[i].key)) > 0) {
    				node = node.nexts[i];
    			}
    			if (cmp == 0) { // 节点是存在的
    				V oldV = node.nexts[i].value;
    				node.nexts[i].value = value;
    				return oldV;
    			}
    			prevs[i] = node;
    		}
    		
    		// 新节点的层数
    		int newLevel = randomLevel();
    		// 添加新节点
    		Node<K, V> newNode = new Node<>(key, value, newLevel);
    		// 设置前驱和后继
    		for (int i = 0; i < newLevel; i++) {
    			if (i >= level) {
    				first.nexts[i] = newNode;
    			} else {
    				newNode.nexts[i] = prevs[i].nexts[i];
    				prevs[i].nexts[i] = newNode;
    			}
    		}
    		
    		// 节点数量增加
    		size++;
    		
    		// 计算跳表的最终层数
    		level = Math.max(level, newLevel);
    		
    		return null;
    	}
    	
    	public V remove(K key) {
    		keyCheck(key);
    		
    		Node<K, V> node = first;
    		Node<K, V>[] prevs = new Node[level];
    		boolean exist = false;
    		for (int i = level - 1; i >= 0; i--) {
    			int cmp = -1;
    			while (node.nexts[i] != null 
    					&& (cmp = compare(key, node.nexts[i].key)) > 0) {
    				node = node.nexts[i];
    			}
    			prevs[i] = node;
    			if (cmp == 0) exist = true;
    		}
    		if (!exist) return null;
    		
    		// 需要被删除的节点
    		Node<K, V> removedNode = node.nexts[0];
    		
    		// 数量减少
    		size--;
    		
    		// 设置后继
    		for (int i = 0; i < removedNode.nexts.length; i++) {
    			prevs[i].nexts[i] = removedNode.nexts[i];
    		}
    		
    		// 更新跳表的层数
    		int newLevel = level;
    		while (--newLevel >= 0 && first.nexts[newLevel] == null) {
    			level = newLevel;
    		}
    		
    		return removedNode.value;
    	}
    	
    	private int randomLevel() {
    		int level = 1;
    		while (Math.random() < P && level < MAX_LEVEL) {
    			level++;
    		}
    		return level;
    	}
    	
    	private void keyCheck(K key) {
    		if (key == null) {
    			throw new IllegalArgumentException("key must not be null.");
    		}
    	}
    	
    	private int compare(K k1, K k2) {
    		return comparator != null 
    				? comparator.compare(k1, k2)
    				: ((Comparable<K>)k1).compareTo(k2);
    	}
    	
    	private static class Node<K, V> {
    		K key;
    		V value;
    		Node<K, V>[] nexts;
    		public Node(K key, V value, int level) {
    			this.key = key;
    			this.value = value;
    			nexts = new Node[level];
    		}
    		@Override
    		public String toString() {
    			return key + ":" + value + "_" + nexts.length;
    		}
    	}
    	
    	@Override
    	public String toString() {
    		StringBuilder sb = new StringBuilder();
    		sb.append("一共" + level + "层").append("\n");
    		for (int i = level - 1; i >= 0; i--) {
    			Node<K, V> node = first;
    			while (node.nexts[i] != null) {
    				sb.append(node.nexts[i]);
    				sb.append(" ");
    				node = node.nexts[i];
    			}
    			sb.append("\n");
    		}
    		return sb.toString();
    	}
    }
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,275
精华内容 4,910
关键字:

跳表