【每日算法Day 54】特殊数据结构2

堆适用于动态地为一组数据进行排序，可以用数组实现，底层的核心操作是上浮和下沉。跳表相较于红黑树是一种在高并发场景下更有优势的结构，能维持一个有序的链表并实现近似的二分查找。

堆

由于堆是一个完全二叉树所以可以很方便地用数组来实现，我们留空第0个位置，堆顶从第一个位置开始计算，则对于第i个元素，其两个孩子在数组中的下标分别为2i和2i+1，其父亲节点的下标为i/2（i!=1）。

构造和维护堆的核心操作是下沉sink与上浮swim，维护小顶堆的性质需要任意节点小于其孩子节点（大顶堆反之）。每当插入一个新节点时我们把它放到数组最后的位置，并对其采用上浮操作。每当删除堆顶元素时，我们把堆顶元素和最后一个元素交换位置并对新的堆顶元素采取下沉操作。

下面设计一个小顶堆：

public class DesignHeap <Key extends Comparable<Key>>{
    private Key[] heap;
    private int capacity;
    private int size;

    public DesignHeap(int initialCapacity) {
        this.capacity = initialCapacity;
        size = 0;
        heap = (Key[]) new Comparable[capacity+1];
    }

    public void offer(Key element) {
        if (size == capacity) {//扩容
            heap = Arrays.copyOf(heap, capacity * 2 + 1);
            capacity *= 2;
        }
        size++;
        heap[size] = element;
        swim(size);
    }

    public Key poll() {
        swap(1, size);
        Key min = heap[size];
        heap[size] = null;
        size--;
        sink(1);
        return min;
    }

    public Key peek() {
        return heap[1];
    }

    //上浮，直到该元素比父节点小
    private void swim(int index) {
        while (index > 1 && heap[index].compareTo(heap[index / 2]) > 0) {
                swap(index, index / 2);
                index /= 2;
        }
    }

    //下沉，选取孩子节点中最小的和自身交换，如果都比自身大则停止下沉
    private void sink(int index) {
        while (index * 2 <= size) {
            int smaller = index * 2;
            if (smaller + 1 <= size && heap[smaller+1].compareTo(heap[smaller]) < 0) {
                smaller ++;
            }
            if (heap[smaller].compareTo(heap[index]) > 0) {
                break;
            }
            swap(index,smaller);
            index = smaller;
        }
    }

    private void swap(int i, int j) {
        Key temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

跳表

参考阅读0 (opens new window) 参考阅读1 (opens new window) 参考阅读2 (opens new window)

定义与特性

跳表是在O(logn)时间内完成增加、删除、搜索操作的数据结构。跳表对标红黑树等二叉平衡搜索树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。对于单链表，即使链表是有序的，如果想要在其中查找某个数据，也只能从头到尾遍历链表，这样效率自然就会很低，跳表就不一样了，其本质是同时维护了多个分层的链表，近似实现了有序链表的二分查找。

跳表和二叉平衡搜索树的一个重要的区别是：对平衡树的插入和删除往往很可能导致平衡树进行一次全局的调整；而对跳表的插入和删除，只需要对整个数据结构的局部进行操作即可。这样带来的好处是：在高并发的情况下，需要一个全局锁，来保证整个平衡树的线程安全；而对于跳表，则只需要部分锁即可。在高并发环境下，跳表就可以拥有更好的性能。

在跳表维护的多层链表中，最底层的是原始链表包含了全部元素并且是有序的，每往上一层都是下一层的子集，自底向上除了原始链表外的多层链表可以依次视为原始链表的第一级索引、第二级索引……如果每层索引分别为n/2 + n/4 + n/8 + … + 8 + 4 + 2 = n-2大小的话总共需要额外O(n)空间。如果每三个结点抽一个结点做为索引，索引总和数就是 n/3 + n/9 + n/27 + … + 9 + 3 + 1= n/2，减少了一半。所以我们可以通过较少索引数来减少空间复杂度，但是相应的肯定会造成查找效率有一定下降。索引结点往往只需要存储 key 和几个指针，并不需要存储完整的对象，所以当对象比索引结点大很多时，索引占用的额外空间就可以忽略了。

盗一张原作者JMCui的图，画得太好了

在查找时从顶级链表开始查找，根据索引的范围转入下一层查找，整个搜索过程是跳跃式的。针对原始链表长度比较大的时候，构建索引，查找效率的提升就会非常明显。在插入时，需要按概率生成元素的层数x，生成越高的x概率越低。一旦确定最高索引层级后，插入式更低的每一层都需要建立索引。删除元素时，找到索引后把下层的相同索引和元素一并删除。

Java中的ConcurrentSkipListMap

ConcurrentSkipListMap 是一个线程安全的基于跳跃表实现的非阻塞的 Map，它要求 Map 中的 key 和 value 都不能为 null。相较于HashMap，ConcurrentSkipListMap内的所有元素都是有序的；相较于红黑树结构TreeMap，ConcurrentSkipListMap是线程安全的。

ConcurrentSkipListMap 适用于高并发的场景，在数据量一定的情况下，并发的线程越多，ConcurrentSkipListMap 越能体现出他查询的优势。

ConcurrentSkipListMap底层结构：

来分别看看 HeadIndex、Index 和 Node 的类信息：

static class Index<K,V> {
    final Node<K,V> node;
    final Index<K,V> down;
    volatile Index<K,V> right;
}
static final class HeadIndex<K,V> extends Index<K,V> {
    final int level;
    HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
        super(node, down, right);
        this.level = level;
    }
}
static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;
}

可以看到，Index 包含了 Node 的引用，并用 right 和 down 引用分别指向各自的 Index 域；HeadIndex 继承自 Index，作为索引的头节点，维护了跳表中 level 的概念；Node 节点存储了实际的 key、value 信息，并用 next 引用构建单链表。

测试,如果使用TreeMap，程序会产生 ConcurrentModificationException 异常：

import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;

public class ConcurrentSkipListMapTest {
    //private static Map<String, String> MAP = new TreeMap<String, String>();
    private static Map<String, String> MAP = new ConcurrentSkipListMap<String, String>();

    public static void main(String[] args) throws InterruptedException {
        // 同时启动两个线程对map进行操作！
        new MyThread("A").start();
        new MyThread("B").start();
        Thread t=Thread.currentThread();
        t.sleep(1000L);
        System.out.println();
        printAll();
    }

    private static void printAll() {
        String key, value;
        for (Map.Entry<String, String> stringStringEntry : MAP.entrySet()) {
            key = stringStringEntry.getKey();
            value = stringStringEntry.getValue();
            System.out.print("(" + key + ", " + value + ") ");
        }
        System.out.println();
    }

    private static class MyThread extends Thread {
        MyThread(String name) {
            super(name);
        }

        @Override
        public void run() {
            int i = 0;
            while (i++ < 6) {
                // "线程名" + "序号"
                String val = Thread.currentThread().getName() + i;
                MAP.put(val, "0");
                printAll();
            }
        }
    }
}