线性数据结构总结

数组是一种线性数据结构。创建数组时会在内存中划分出一块连续的内存区域，数据会保存在这块连续区域的每块索引。

数组支持的操作

查询(get(int index))

首先说明通过下标获取元素的时间复杂度为O(1)。因为数组是一块连续的内存区域，并且每个元素的大小都相等，通过一个线性方程就很快能找到改下标对应的内存地址。例如如果是一个int数组，0位置的内存地址为b，index是你要找的下标，那么显然你要获取的内存地址就是b+4*index，4就是一个int占的字节数。所以计算机 通过b+type_size*index来计算下标 。当然，并不是所有的数组都是如此计算下标的，例如有的虚拟机在开辟数组空间时并不是开辟的连续空间。

插入(add(int index,E e))

增加时如果要指定增加到的数组下标一般将要对数组元素进行移动，例如有一个十个元素的整型数组，要将一个数字A插入到第一个元素的位置，那么就需要先将所有元素从后往前向后移动一个位置再将A插入到第一个位置。所以数组的插入操作平均时间复杂度为O(n)

删除(remove(int index))

和插入一样，指定下标进行删除。例如有十个元素，删除第一个元素，那么就需要将数组元素从当前元素由前至后向前移一个下标。所以数组的删除操作平均时间复杂度为O(n)

修改(set(int index,E e))

修改就比较简单了，直接获取下标改变当前元素的值即可

动态数组

很多高级语言都有数组这个基本结构，但是在使用他们的时候如果我们增加的元素超过一开始定义它的总个数的话是没办法继续添加的。所以，当我们一开始不知道这个数组的大小时这就比较麻烦了，我们就需要自己定义动态数组，我们不需要管他的初始容量。

实现自己的数组

实现动态数组主要需要重写数组的增加、删除操作，还要实现扩容操作

增加

自己实现的增加操作和原来的区别就是要判断是否需要将数组扩容。扩容的条件为当数组的长度和元素的个数相同时就需要扩容，一般扩容为两倍。 扩容的步骤：

• 将原数组复制一份并让大小为原数组的2倍
• 将原数组的所有元素写入到新数组中，并增加新添加的元素

删除

自己实现的删除操作和原来的区别就是要判断是否需要将数组缩容，缩容是有必要的。缩容的条件比扩容的条件多一点，就是缩容前的数组大小要大于等于2，并且当前元素个数为数组大小的一半。 缩容的步骤：

• 先将原数组的元素删除
• 将原数组复制一份并让大小为原数组的1/2倍
• 将原数组的所有元素写入到新数组中

扩容，缩容产生的震荡

产生的震荡和我们的扩容，缩容条件有关，如果按照上面的条件进行扩容和缩容，那么如果这个数组的元素个数如果在8和9之间徘徊，那么数组的大小就会在8，16中徘徊。

而震荡的解决方法和具体的需求有关，我们可以将缩容的条件改为"缩容前的数组大小要大于等于2，并且当前元素个数为数组大小的1/4"

java.util.ArrayList中如何扩容

扩容肯定在

//新增方法
    public boolean add(E e) {
        //modCount是记录修改次数的（迭代器判断结构是否变），迭代器fail-fast机制就靠它
        modCount++;
        //elementData是数组元素，size是数组大小
        add(e, elementData, size);
        return true;
    }
    
    private void add(E e, Object[] elementData, int s) {
        //数组大小和数组元素个数相等，要扩容了
        if (s == elementData.length)
            elementData = grow(s+1);
        elementData[s] = e;
        size = s + 1;
    }
    
    private Object[] grow(int minCapacity) {
        //可以看到也是通过复制一个新数组
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }
    
    //接下来就是如何真正实现扩容的！！！
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //新大小是老大小的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果新大小比oldCapacity+1小
        if (newCapacity - minCapacity <= 0) {
            //如果数组是空的，第一次添加元素，就直接扩容到10和minCapacity中大的那个
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        //返回大的那个，不超过最大
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
复制代码

可以看到扩容的思路还是很简单的，本人环境是jdk1.9，至于其他版本的扩容思路我想都差不多。至于缩容，这里就不再阐述了，arraylist的源码还是比较容易理解的。

链表

链表和数组都是线性结构，但是链表是一个一个的节点组成的，这个节点有一个next指针指向下一个节点，也就是说链表不需要连续的数组空间。如图：

链表的操作

下面来看一下如何对链表进行增删改查

增加

增加的操作时间复杂度为O(1)，不用像数组一样去移动数组元素，如A->C，增加B到A的后面 增加步骤：

• 将A的next指针保存为temp
• 将A的next指针指向B
• 将B的next指向temp

删除

删除的时间复杂度为O(1)，不用像数组一样去移动数组元素，如A->B->C，删除B 删除步骤：

• 获取变量temp保存节点B
• 将A的next指针指向C（free掉B）

查询

查询的时间复杂度为O(n)，因为链表不像数组可以直接通过下标计算出内存地址。所以必须通过遍历找到相应下标节点。

这里的增加和删除时间复杂度为O(1)很好理解，我们可能会得出一个结论那就是数组的查询修改效率高，链表的删除增加效率高。但实际上这也是分情况的。当我们在对一个节点进行插入或删除时我们要去遍历到指定位置（因为我们只有头节点地址或者尾节点地址）。之前做过一个测试，对于 java 中的结构LinkedList（双向链表）和ArrayList（双向链表），在增加大概一百万个元素的时候会发现数组的增加方法效率更高，因为在指定位置对链表添加元素链表要去遍历。

虚拟头节点：最后，一般链表都会有一个头节点，这个节点指向链表的首节点，这个头节点的用处是当我们将删除最后一个元素的时候不用专门判断删除只有一个元素的情况

栈，队列

栈和队列很相似，所以结合起来一起看。

• 栈是一个FILO（先进后出）的结构，它可以由数组或链表实现。常见的例如在浏览器浏览网页，在当前网页进入另一个网页相当于入栈，返回相当于出栈。
• 队列是一个FIFO（先进先出）的结构，它可以由数组或链表实现。队列的应用也很广，例如排队。

栈

基于数组的栈实现

结构：数组array，top变量

数组用来保存进入的数据。 top指针指向最后一个元素的下一个位置 ，如果栈为空top指向0。

举个例子：

如上图

• 栈空：当栈为空的时候top指向0下标
• 栈满：当元素满了后top==array.length；
• 入栈：如果有元素入栈array[top++]=入栈元素
• 出栈：当元素要出栈时return array[top--];

基于链表的栈实现

结构：top指针，节点

• 节点中有data，next指向下一个节点
• top指针用来指向栈最上面的节点

如图：

• 栈为空：top指向null
• 入栈：构造新节点node，新节点node的next指向top指针的指向，top指针指向新节点node
• 出栈：用node保存top指向的节点，top指针指向node的next指针指向的节点，返回node

队列

基于链表的队列

结构：虚拟头节点，节点

• 虚拟头节点：front指针指向第一个元素，rear指针指向最后一个元素
• 节点：data数据元素，next下一个节点指向

如图：

• 空队列：front和rear都指向null
• 入队：构造新节点，rear指针的next指针指向新节点
• 出队：判断为非空，保存front指向的节点node，front指向node的next节点，返回node

基于数组的队列

基于数组的队列和基于数组的栈有一些不同。可以想到，当数组队列入队时可以增加到数组后面，出队时将前面的元素移出，那么就会出现问题就是前面出队的元素会变为不可用但又没法用，有一种解决方式可以在出队的时候把后面的元素放在前面，就像前面动态数组那样删除首元素即可，但是如果是这样每出队一次就整体移动一次元素未免也太耗时了一些。所以这里引入循环队列。

理解循环队列

循环队列要解决的问题就是数组队列浪费空间的问题。循环队列并不是在物理地址上是循环的，而是在逻辑上循环的。

结构：数组，front指向头，rear指向队尾的后一位元素

front=front%array.length

如图：

• 图中有两个指针front、rear,front代表队头下标，rear代表队尾下标。
• 队列为空：front和rear都指向一个位置
• a，b，c入队，队头下标front不变，rear(rear=(rear+1)%array.length)指向最后元素的下一个坐标
• a出队，front指向下一个元素(front=(front+1)%array.length)
• 最后当增加到如图d2那样(rear+1)%array.length=front时代表元素已满

要注意的点

1. 入队时,rear=(rear+1)%array.length
2. 出队时,front=(front+1)%array.length
3. 在循环队列中相当于我们浪费了一个元素位置，这样做的好处是我们可以区别开空队和满队的区别。
4. 空队列：front==rear
5. 满队列：(rear+1)%array.length==front，这个时候就需要扩容了
6. 扩容：扩容的步骤和动态数组的逻辑相似，只不过要重新给front和rear赋值

哈希表

当我们想在学校想找到某个人的信息，我们会向教务处去查询学号，而教务处获得你提供的学号就会给你一个学生的信息。这里通过学号获得学生信息就是用了哈希表的思想，而学号和学生信息的对应关系就是哈希函数，而如果两个学号对应到了同一个学生信息就是哈希冲突。

所以接下来来看一下哈希表中的名词：

• 哈希表：通过给定的关键字的值直接访问到具体对应的值的一个数据结构
• 哈希函数：将给定关键字转化为内存地址索引
• 哈希冲突：不同的关键字通过哈希函数转化为同一个索引

哈希表作用

哈希表的查找时间复杂度为O(1)，哈希表查找的思路是直接通过关键字查找到元素。增加删除的时间复杂度也是O(1)，也就是说哈希表

哈希表的结构

底层有一个Node数组array，当前元素个数M

• 这个Node有key(键)，value(值)，next(下一个Node节点)。
• M为当前array中有的元素数量

哈希函数

因为我们要实现对于不同的key尽可能的通过哈希函数得出不同的值。所以对于哈希函数的选取是比较重要的。

以下为常见哈希函数：

• 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。如H(key)=key或H(key) = a?key + b。a,b为常数。
• 数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如身份证号，我们可以提取出身份证号中关键的数字，例如表示出生年月和后六位。
• 平方取中法：取关键字平方后的中间几位作为散列地址。
• 取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。
• 除留取余法：H(key) = key MOD p。key为关键字，MOD为取余操作，p为哈希表的长度， p最好为质数，可以达到最小可能的哈希冲突 。

接下来我们将哈希函数都设置为除留取余法进行分析。

哈希冲突

哈希冲突就是不同的两个key，他们hash(key)之后得到的结果相同。对于哈希冲突的解决也有多种

• 链地址法：若A经过hash之后确定在数组的下标为2，B经过hash之后确定数组下标也为2，B就跟在A之后形成链表。这时整个哈希表就形成了数组+链表的结构。
• 开放地址法：
  • 线性探测：当发现哈希冲突时将下标分别进行+1直到下标位置没有元素再放入
  • 平方探测：当发现哈希冲突时将下标分别进行1^2, 2^2, 3^2...直到下标位置没有元素再放入
  • 伪随机序列法：当发现冲突就将key随机加一个数再取模，直到下标位置没有元素再放入
• 再哈希法：这种方法是同时构造多个不同的哈希函数，如果第一个哈希冲突了就用第二个哈希函数，以此类推

接下来我们将哈希冲突解决方式设置为链地址法进行分析。

哈希表操作过程

增加操作

例如用户要增加一个K，V键值对，先将K的哈希值计算出来，再将哈希值对数组长度取模获得下标，如果下标没有元素，就将K，V封装成Node放入这个下标，如果下标已经有元素，就K，V封装成Node加入到这个下标元素的最后面。

查找操作

例如一个用户要通过K查找这个节点，通过hash(K)再取模得到这个数组的下标，如果这个下标没有元素，代表查找失败，如果这个下标有元素，那就从这个元素向后面的链表遍历，有就返回。

删除和修改逻辑类似

HashMap的实现方式

java中的HashMap是封装的非常好的一个哈希表，通过分析它的实现也可以让我们更完善自己的哈希表设计

我们来看一下它有哪些关键字段

//负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    //哈希表中的数组
    transient Node<K,V>[] table;
    
    //数组中每个元素保存的下面这个节点
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    
        //..一些节点其他的方法
        
    }
复制代码

接下来来看一个put操作（增加操作）的流程。

//增加一个key，value
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    //采用的hash算法
    static final int hash(Object key) {
        int h;
        //可以看到这里hash算法用的key的hashCode和h右移16位的异或运算
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    //最后调用的putVal操作
    /**
     * hash是传来的哈希值
     * key是键，value是值
     * onlyIfAbsent为false代表多个key会重写
     * evict为false代表表处于创建状态
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果一开始hashmap没有元素的话初始化hashmap大小
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //没有哈希冲突的话直接构造新的链表节点添加进数组中，i为计算出的下标
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //接下来是有哈希冲突的情况
        else {
            Node<K,V> e; K k;
            //这里计算出下标的节点的哈希值要等于之前传过来计算好的哈希值。并且要引用同一个对象并且equals方法也要相等！！这里表示判断为同一个对象的逻辑！！我曾经在这里踩过坑。。其次，如果两次的key都为null的话
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //这里不是同一个对象并且是TreeNode结构（当链表节点个数大于等于8的时候会转化为红黑树）
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //接下来正常添加链表节点
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //如果value变换之后这里会返回老的value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
复制代码

关于HashMap中的put操作，有以下几点注意的地方

• 如果传来的key为null，putVal还是按常规操作进行添加，同上面的逻辑一样，并且得出来的哈希值为0
• 如何判断两个key是否相等，简单来说就是两个键hashCode和equals必须同时相同或者说保持一致。很久之前我踩过的一个坑就是两个对象他们的hashCode返回的相同值，而equals却返回false，导致添加的时候总是会添加两个元素，事实上这也是我的设计出错，一个类最好保证重写的hashCode和quals方法能够一致

下一篇会总结树结构数据类型，并且下一篇会把自己实现的数据类型分享出来