漫画算法(2) - 数据结构

数组

public class MyArray {

    private int[] array;
    private int size;

    public MyArray(int capacity) {
        this.array = new int[capacity];
        size = 0;
    }

    /**
     * 数组插入元素
     *
     * @param index   插入的位置
     * @param element 插入的元素
     */
    public void insert(int index, int element) throws Exception {
        // 判断访问下标是否超出范围
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出数组实际元素范围！");
        }
        // 如果实际元素达到数组容量上线，数组扩容
        if (size >= array.length) {
            resize();
        }
        // 从右向左循环，逐个元素向右挪一位
        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }
        // 腾出的位置放入新元素
        array[index] = element;
        size++;
    }

    /**
     * 数组扩容
     */
    public void resize() {
        int[] arrayNew = new int[array.length * 2];
        // 从旧数组拷贝到新数组
        System.arraycopy(array, 0, arrayNew, 0, array.length);
        array = arrayNew;
    }

    /**
     * 数组删除元素
     *
     * @param index 删除的位置
     */
    public int delete(int index) throws Exception {
        // 判断访问下标是否超出范围
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出数组实际元素范围！");
        }
        int deletedElement = array[index];
        // 从左向右循环，逐个元素向左挪一位
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        size--;
        return deletedElement;
    }

    /**
     * 输出数组
     */
    public void output() {
        for (int i = 0; i < size; i++) {
            System.out.println(array[i]);
        }
    }

    public static void main(String[] args) throws Exception {
        MyArray myArray = new MyArray(4);
        myArray.insert(0, 3);
        myArray.insert(1, 7);
        myArray.insert(2, 9);
        myArray.insert(3, 5);
        myArray.insert(1, 6);
        myArray.insert(5, 8);
        myArray.delete(3);
        myArray.output();
    }
}

链表

public class MyLinkedList {

    // 头节点指针
    private Node head;
    // 尾节点指针
    private Node last;
    // 链表实际长度
    private int size;

    /**
     * 链表插入元素
     *
     * @param index 插入位置
     * @param data  插入元素
     */
    public void insert(int index, int data) throws Exception {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node insertedNode = new Node(data);
        if (size == 0) {
            // 空链表
            head = insertedNode;
            last = insertedNode;
        } else if (index == 0) {
            // 插入头部
            insertedNode.next = head;
            head = insertedNode;
        } else if (size == index) {
            // 插入尾部
            last.next = insertedNode;
            last = insertedNode;
        } else {
            // 插入中间
            Node prevNode = get(index - 1);
            insertedNode.next = prevNode.next;
            prevNode.next = insertedNode;
        }
        size++;
    }

    /**
     * 链表删除元素
     *
     * @param index 删除的位置
     */
    public Node remove(int index) throws Exception {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node removedNode = null;
        if (index == 0) {
            // 删除头节点
            removedNode = head;
            head = head.next;
        } else if (index == size - 1) {
            // 删除尾节点
            Node prevNode = get(index - 1);
            removedNode = prevNode.next;
            prevNode.next = null;
            last = prevNode;
        } else {
            // 删除中间节点
            Node prevNode = get(index - 1);
            Node nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            prevNode.next = nextNode;
        }
        size--;
        return removedNode;
    }

    /**
     * 链表查找元素
     *
     * @param index 查找的位置
     */
    public Node get(int index) throws Exception {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 输出链表
     */
    public void output() {
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }

    /**
     * 链表节点
     */
    private static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) throws Exception {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.insert(0, 3);
        myLinkedList.insert(0, 4);
        myLinkedList.insert(2, 9);
        myLinkedList.insert(3, 5);
        myLinkedList.insert(1, 6);
        myLinkedList.remove(0);
        myLinkedList.output();
    }
}

队列

public class MyQueue {

    private int[] array;
    private int front;
    private int rear;

    public MyQueue(int capacity) {
        this.array = new int[capacity];
    }

    /**
     * 入队
     *
     * @param element 入队的元素
     */
    public void enQueue(int element) throws Exception {
        if ((rear + 1) % array.length == front) {
            throw new Exception("队列已满！");
        }
        array[rear] = element;
        rear = (rear + 1) % array.length;
    }

    /**
     * 出队
     */
    public int deQueue() throws Exception {
        if (rear == front) {
            throw new Exception("队列已空！");
        }
        int deQueueElement = array[front];
        front = (front + 1) % array.length;
        return deQueueElement;
    }

    /**
     * 输出队列
     */
    public void output() {
        for (int i = front; i != rear; i = (i + 1) % array.length) {
            System.out.println(array[i]);
        }
    }

    public static void main(String[] args) throws Exception {
        MyQueue myQueue = new MyQueue(6);
        myQueue.enQueue(3);
        myQueue.enQueue(5);
        myQueue.enQueue(6);
        myQueue.enQueue(8);
        myQueue.enQueue(1);
        myQueue.deQueue();
        myQueue.deQueue();
        myQueue.deQueue();
        myQueue.enQueue(2);
        myQueue.enQueue(4);
        myQueue.enQueue(9);
        myQueue.output();
    }
}

散列表

散列表也叫哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。给出一个Key，就可以高效查找到它所匹配到的Value，时间复杂度接近于O(1)。

哈希函数把 Key 和数字下标进行转换，这个中转站叫做哈希函数。Java 及大多数面向对象的语言中，每一个对象都有属于自己的 hashcode，这个 hashcode 是区分不同对象的重要标识。无论对象自身的类型是什么，他们的 hashcode 都是一个整形变量。整形变量转化成数组的下标，可以按照数组长度进行取模运算。实际上，JDK 中的哈希函数并没有直接采用取模运算，而是利用位运算的方式来优化性能。通过哈希函数，把字符串或其他类型的 Key，转化成数组的下标 index。

哈希冲突是无法避免的，解决哈希冲突的方法主要有两种：开放定址法和链表法。开放定址法的原理是当一个 Key 通过哈希函数获得对应的数组下标已被占用时，寻找下一个空挡位置，不一定是简单地寻找当前元素的下一个元素。在 Java 中，ThreadLocal 使用的就是开放定址法。链表法被应用在了 Java 集合类 HashMap 中。HashMap 数组的每一个元素不仅是一个 Entry 对象，还是一个链表的头结点。每一个 Entry 对象通过 next 指针指向它的下一个 Entry 节点。当新来的 Entry 映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。

参考资料

《漫画算法》第 2 章