数据结构与算法(一)：数组、链表、哈希表

　　数组、链表、栈和队列、散列表是基础数据结构，几乎所有的高级开发语言都会涉及到这些数据结构，一些更复杂的数据结构也是基于基础数据结构的扩展。

　　基础数据结构是数据存储的基础理论，有必要彻底理解它。

数据存储结构可以分为 物理结构 和 逻辑结构。

• 物理结构又分为 线性结构 和 非线性结构

  • 线性结构：如 顺序表，栈，队列，
  • 非线性结构：如 图，树。

• 逻辑结构又分为 顺序存储结构 和 链式存储结构

  • 顺序存储结构：如 数组。
  • 链式存储结构：如 链表。

注意：某些复杂的数据结构是可以基于不同的数据结构类型来实现的，如 二叉树，是一种逻辑结构，也可以依托于物理上的数组或链表来实现。

数组

概念

数组（Array）：是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。

数组在内存中是 顺序存储，在内存中是占用一块连续的内存空间，数组元素之间紧密排列，即不能打乱元素排列顺序，也不能跳过某个存储单元进行存储。

操作

1. 读取元素

   由于数组在内存中顺序存储，只要给出一个数组下标，就可以读取到应用的数组元数。数组下标从 0 开始，给出的数组下标必须在数组的长度范围之内，否则出现数组越界。

2. 更新元素

   把数组中某一个元数的值替换为一个新值。直接根据数组下标，赋给该元数新值。

3. 插入元素

   尾部插入：尾部插入最简单，直接在尾部追加。

   中间插入：稍许复杂，需要把插入位置的元素及后面的元素向后移动，为插入元素腾出空间。

   超范围插入：因数组的容量在创建时就确定的，如果需要超范围插入，就涉及数给扩容，通常是创建一个新数给，为旧数组的 2 倍，在把旧数组中的元素全部复制到新数组。

4. 删除元素

   根据元素下标删除，实际是把要删除的元素的后面元素向前挪动 1 位，覆盖要删除的元素。若没有顺序要求，可将最后一个元素赋值给要删除的元素的位置，这就无须进行大量的元素移动。

优势和劣势

1. 优势：高效的访问性能，只需给出下标，就可找到对应的元素。
2. 劣势：体现在插入和删除元素方面。因数组元素是连续紧密存储在内存在，插入、删除操作会导致大量元素被迫移动，影响效率。

通常来说，数组适合读操作多，写操作少的场景。

链表

链表（Linked list）：是一种在物理上 非连续、非顺序的数据结构，由若干节点（node）所组成。

链表在内存中的存储方式是 随机存储，这样可以有效地利用零散的碎片空间。

单向链表

单向链表 的每一个节点仅包含两部分，一部分是存放数据的变量 data，另一部分是指向下一个节点的指针 next 。通过指针把数据完整地链接起来。

第 1 个节点被称为头节点，最后 1 个节点被称为尾节点，尾节点的 next 指针指向空。

单向链表只能一级一级，单线传递查找。

双向链表

双向链表 比单向链表稍微复杂一些，每一个节除了拥有 data 和 next 指针，还多了指向前置节点的 prev 指针。

基本操作

1. 查找节点

   只能从头节点开始，根据节点的 next 指针向后一个一个节点逐一查找。

2. 更新节点

   先查找节点，把旧数据替换成新数据即可。

3. 插入节点

   尾部插入：最简单，把最后一个节点的 next 针指指向新插入的节点即可。

   头部插入：把新节点的 next 指针指向原先的头节点，把新节点变为链表的头节点。

   中间插入：插入位置的前置节点的 next 指针指向插入的新节点，新节点的 next 指针指向前置节点的 next 指针原先指向的节点。

4. 删除元素

   尾部删除：最简单，把倒数第 2 个节点的 next 指针指向空即可。

   头部删除：把链表的头节点设为原头节点的的 next 指针即可。

   中间删除：把要删除节点的前置节点的 next 指针，指向要删除节点的下一个节点即可。

链表实现

package com.datastructure.linkedlist;

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

    /**
     * 插入节点
     *
     * @param data
     * @param index
     */
    public void insert(int data, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }

        Node insertNode = new Node(data);

        if (size == 0) {
            //空链表新增第一个
            head = insertNode;
            last = insertNode;
        } else if (index == 0) {
            //插入头部
            insertNode.next = head;
            head = insertNode;
        } else if (index == size) {
            //插入尾部
            last.next = insertNode;
            last = insertNode;
        } else {
            //插入中间
            //找到前置节点
            Node prevNode = get(index - 1);
            //找到后置节点
            Node nextNode = prevNode.next;
            //前置节点next指针指向新插入的节点
            prevNode.next = insertNode;
            //新插入的节点的next指针指向原后置节点
            insertNode.next = nextNode;
        }
        size++;
    }

    /**
     * 删除节点
     *
     * @param index
     * @return
     */
    public Node remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表的范围");
        }

        Node removeNode = null;

        if (index == 0) {
            //删除头节点
            removeNode = head;
            head = head.next;
        } else if (index == size - 1) {
            //删除尾节点
            Node prevNode = get(index - 1);
            removeNode = prevNode;
            //前置节点变为尾节点
            last = prevNode;
            //尾节点的next变为null
            prevNode.next = null;
        } else {
            //删除中间节点
            //获取前置节点
            Node prevNode = get(index - 1);
            //根据前置节点获取下下个节点(要删除的节点的下一个节点)
            Node nextNode = prevNode.next.next;
            removeNode = prevNode.next;
            prevNode.next = nextNode;
        }

        size--;

        return removeNode;

    }

    /**
     * 链表查找元素
     *
     * @param index
     * @return
     */
    private Node get(int index) {
        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;
        }
    }

    public static void main(String[] args) {
        MyLinkedList1 myLinkedList1 = new MyLinkedList1();
        myLinkedList1.insert(3, 0);
        myLinkedList1.insert(7, 1);
        myLinkedList1.insert(4, 2);
        //插入尾节点
        myLinkedList1.insert(2, 3);
        //插入头节点
        myLinkedList1.insert(6, 0);
        //插入中间节点
        myLinkedList1.insert(8, 2);

        myLinkedList1.output();

        System.out.println("--------------------------");

        //移除头节点
        myLinkedList1.remove(0);
        //移除中间节点
        myLinkedList1.remove(3);

        myLinkedList1.output();
    }
}

class Node {

    int data;
    Node next;

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

循环链表

循环链表 即尾节点的 next 指针指向 头节点，如果是双向循环链表，则头节点的 prev 指针指向属节点。

数组VS链表

数组 的优势在于能够快速定位元素，对于读操作多，写操作少的场景来说比较合适。

链表 的优势在于能够灵活地进行插入和删除操作，如需要在链表尾部频繁执行插入、删除操作，则链表更合适。

时间 / 空间复杂度比较	查找	更新	插入	删除
数组	Ο(1)	Ο(1)	Ο(n)	Ο(n)
链表	Ο(n)	Ο(1)	Ο(1)	Ο(1)

哈希表

哈希表也称为 散列表（Hash Table），提供键（Key） 和值（Value）映射关系。只要给出 key ，就可以高效查找到映射的 Value，时间复杂度接近于 Ο(1) 。

在极端情况下，如果所有 Key 的数组下标都冲突，那么，Hash 表就退化为一条链表，查询的时间复杂度是 O(N)。

哈希表的物理存储其实是一个数组，通过 Hash函数计算 Key 的下标（HashCode）就可以找到在内存的位置，Key-Value 数据并不会直接存储在 Hash 表的数组中，因为数组要求存储固定的数据类型，主要是每个数组元素中要存放固定长茺的数据。所以，数组中存储的是 Key，Value 数据元素的地址指针。

哈希函数

哈希表 在本质上也是一个数组，通过 哈希函数 将数组下标转换为 Key 值。

不同的语言中，哈希函数 的实现方式不一样，下面以 Java 中的 HashMap 为例进行分析。

Java 中的每一个对像都有属于自己的 hashcode ，hashcode 是个整型变量，是区分不同对象的重要档识。

整型变量转化成数组下标，最简单的转化方式是按照数组长度进行取模运算。而 JDK 中的哈希函数是利用位运算的方式来优化性能。

取模运算，例如一个长度为 8 的数组，key 为 001121，转换为数组下标 index = hashcode(“001121”) % Array.length = 1420036703 / 8 = 7。

写操作（put）

写操作就是在散列表中插入新的键值对。以 HashMap 为例。

a. 实际是通过哈希函数，把 key 转化成数组下标。

b. 如果数组该下标对应的位置没有元素，就把这个元素存入到该位置。

c. 数组长度是有限的，当插入的元素越来越多时，不同的 Key 通过哈希函数获取的下标有可能相同，这种情况就出现了 哈希冲突。

哈希冲突是无法避免的，但然要想办法解决，主要有两种方法：一种是开放 寻址法，一种是 链表法。

• 开放寻址法

  当一个 Key 通过 哈希函数 获得对应的数组下标已被占用时，则寻找下一个空的位置。这只是开放寻址法的基本思路。

  寻址方式有很多种，如 线性探测再散列，二次探测再散列、双重散列等方法，使用某种探测算法在散列表中寻找下一个空的散列地址，只要散列表足够大，总能找到空的散列地址。可参考 数据结构：哈希表以及哈希冲突的解决方案 博文。

  在 Java 中，ThreadLocal 所使用的就是开放寻址法。

• 链表法

  Java 的 HashMap 使用此方法。

  HashMap 数组中的每一个元素不仅是一个 Entry 对象，还是一个链表的头节点。每一个 Entry 对象通过 next 指针指向它的下一个 Entry 节点。当新来的 Entry 映射到与之冲突的数组位置时，只需插入到对应的链表中即可。

  备注： JDK 8 和以前的版本有较大的不同。当多个 Entry 被 Hash 到同一个数组下标的位置时，为了提升插入和查找的效率，HashMap 会把 Entry 的链表转化为 红黑树 这种数据结构。

读操作（get）

通过给定的 Key ，在散列表中查找对应的 Value。

a. 通过哈希函数，将 key 转换成数组下标。

b. 若直接找到则返回，若没有找到，则顺着该 Entry 的链表往下找到与 Key 对应的元素。

扩容（resize）

数组存在扩容，散列表是基于数组的，也同样涉及扩容的问题。

当散列表中多次插入元素达到一定饱和度时， Key 映射位置发生冲突的概率会逐渐提高。当大量元素拥挤在相同的数组下标位置，会形成很长的链表，对后续的插入和查表操作的情能有很大的影响。

这时，散列表就需要扩展它的长度，即需要进行 扩容 。

JDK 中的散列表实现类 HashMap 的扩容有两个因素：

• Capacity：即 HashMap 的当前长度。
• LoadFactory：即 HashMap 负载因子，默认值为 0.75f 。

扩容 是创建一个新的 Entry 空数组，长度为原数组的 2 倍。重新 Hash，遍历原 Entry 数组，把所有 Entry 重新 Hash 到新数组中。重新 Hash 是因为扩大长度后， Hash 规则也随之改变。

经过扩容，原来拥挤的散列表重新变得稀疏，原有的 Entry 也重新得到了尽可能均匀的分配。

其它参考

1. Interview - Data Structures
2. 面试需要知道的8种数据结构