• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

关于数据结构

开发技术 开发技术 1个月前 (10-27) 17次浏览

数据结构

本文准备讲一下软件开发中的数据结构。

物理存储

因为数据结构是用来存储数据的具体方式,在将数据结构之前,说说数据物理存储。

平时软件开发中,一个8G的内存可以同一时间存储8G的数据,在物理上来说,这些存储单元是连续的,理论上可以可以看成是地址从0开始到 8*2^30次方。理想的话,什么数据通过寻址就能找到,很方便

但是数据的使用在计算机中并不只是查询,也可以是修改,添加,删除,移动,考虑的数据安全,运算速度,使用效率的等综合,基于物理硬件的软件数据结构往往并不只有数组,还有其他,比如链表,图,树等。

在复杂的情况下,各种各样的运算,不同程序的进程,线程都在使用这些内存或者cpu资源,这些数据通过软件的角度去解读,肯定存在差异的结构,在物理上底层都是数组。

数组

数组,是数据最基本的存储结构,数组表示同一种数据有多个。

数组的有点事查询快,通过索引能够快速找到。

但是数组优缺点,就是修改数组长度的时候,很麻烦。

示意

数组 内容为

char[] arrays = {'a','p','p','l','e',' ',' ','1','3','6','6','8','5','$'}

要修改次数组,将arrays[5] = ‘5’ arrays[6] = ‘$’;,然后删除arrays[6]之后的数据,

最终 arrays变为 arrays = {'a','p','p','l','e','5','$'}

大致过程如下,

关于数据结构

使用数组的时候,当你查看数据时,特别方便快色,如你要查看数组的第2个元素 直接arrays[1]就能访问获得元素内容’p’

但是删除元素的时候却很麻烦,如上图删除index = 5~12的元素,之后你还需要将 index = 13 ~14 的内容搬到 index = 5~6 上面,并且将index等于 7~14的存储单元清空还给计算机管理(空间高效利用原则)

这还不是最坏的情况,数组是连续的,如果有一个10000位的数组,你只是删除了第一个元素,那么后面9999个元素都要向前移动一位,这明显不是很好的数据使用方式,或者多种数据结构在不同使用场景下使用。

链表

链表是一种带有下一个元素信息的数据结构,链表有开头和结尾,并且链表不需要一定是连续的存储单元

链表针对数组元素的添加和删除,有了明显直观的优化,链表是不连续的存储单元存储数据,每个存储单元都存有内容+next缩影,通过next索引找到下一个数据

因此删除数据的时候,只需删除一个数据,要将next索引修改一下就好了,不会像数组那样大规模修改数据。

关于数据结构

上面删除apple 链表的 ‘i’元,将链表第三个单元‘p’的next 地址修改位指向 e,再删除‘i’即可

链表删除增加很快,但是如果有长度1000的链表,查看第500个元素,只能从第一个开始,通过next寻址500此才能找到元素。

树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样。


树的度——也即是宽度,简单地说,就是结点的分支数。以组成该树各结点中最大的度作为该树的度,如上图的树,其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
深度
树的深度——组成该树各结点的最大层次,如上图,其深度为4;
层次
根结点的层次为1,其他结点的层次等于它的父结点的层次数加1.
路径
对于一棵子树中的任意两个不同的结点,如果从一个结点出发,按层次自上而下沿着一个个树枝能到达另一结点,称它们之间存在着一条路径。可用路径所经过的结点序列表示路径,路径的长度等于路径上的结点个数减1.
森林
指若干棵互不相交的树的集合

关于数据结构

树与数组的区别

查询一个数据是否存在,

数组是全部展示,没有深度,你有索引的情况下能快速查找,如果没有索引,需要一个个查看内容对比。

树有层次,有深度和宽度,也有索引,索引与元素内容有关联,如二分查找法,可以快速得知数据是否存在,而不是每个数据依次查看。

个人理解树是有层次的数据结构,有深度和宽度,在某些查询场景上比数组数据结构更加高效快速

文件系统可以看作树结构的经典应用。

HashMap

可以看出数组和链表是两种区别很大的数据结构,数组查询快,增删慢,链表相反,查询慢,增删快

如果能将这两个数据结构的有点结合,就能很好的去操作数据了,提升性能和数据处理速度,Java中的HashMap就是一个将数组和链表有点结合的数据结构,接下来探索了解Java中的HashMap数据结构

关于数据结构

存值

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            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;
                }
            }
            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;
    }

哈希值

hash值计算是一种获取不重复值的算法,通常key不同,返回的数值不同

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

public native int hashCode(); //jvm本地方法

索引算法

putVal(hash(key), key, value, false, true);

// 实际存值代码
if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null); 
// i = (n - 1) & hash   i就是计算出的索引值

快速查找

HashMap类似数组的快速定位查找与哈希计算和数组有关

下面是HashMap构造和查询有关的代码

/**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;

table 是一个数组,数组元素的机构是Node

/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;  //指向像一个元素,是一种链表结构的应用

    //... 省略一些代码
}

Node 是类似链表结构,成员属性包含一个Node<K,V> next 有next是防止hash碰撞等情况

get方法获取值(查找

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {  
            //判断如果table不是空  取值 tab[(n - 1) & hash]
            //可以看出数组索引是 (n-1) & hash 这里其实是位运算得出数组索引
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;   //判断key完全相同则返回内容
            if ((e = first.next) != null) {
                // 复杂点的情况下 如果发生索引相同冲突,使用链表来解决冲突
                if (first instanceof TreeNode)
                    // 如果数据过多会改变链表为树结构,提高数据查询效率
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

索引冲突

关于HashMap中 table数组索引的确定(根据key)

hash = hash(key); //通过key获取hash值
n = tab.length; //获取数组长度 值一定是2的n次方(可以看HashMap中resize方法了解细节)
index = (n - 1) & hash  //在存值和取值的时候,算出index,数组的索引

table.length 是一个 2的n次方值,也就是说 n-1 一定是 0000011111这种类似结构

n = 8; 二进制 1000

n – 1 = 7 二进制 0111

如果一个key的hash值为十进制数86,二进制为1010110, 那么 n=8时

(n-1) & 1010110 = 0000111 & 1010110 它的结果是 0110 换算十进制为 6,直接找到元素位置table[6];

hashmap在实际使用时可能有key不同,索引值相同的情况。

当两个key虽然hash值不同,table.length = 8的时候,两个key的hash值不同,一个值是keyHash1=23001,一个值是keyHash2=20001,这两个值在(n-1) & hash的位运算中,结果都是1,所以index = 1,这时候需要用到链表去解决这种问题,

table[1] = node1;

node1.key = key1,node1.value = value1 node1.next = node2

node2.key = key2,node2.value = value2 node2.next = null;

链表改为树结构

如果node过多,后面会将链表改为树结构

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  链表改为树的逻辑判断
                            treeifyBin(tab, hash);

// TREEIFY_THRESHOLD的定义
static final int TREEIFY_THRESHOLD = 8;

可以知道当链表元素超过7个,为了查询效率,会把当前链表结构改为树结构


喜欢 (0)