java数据结构_java数据结构实现 - CSDN
精华内容
参与话题
  • Java数据结构与算法入门

    千次阅读 多人点赞 2018-04-29 11:53:50
    第一部分:Java数据结构要理解Java数据结构,必须能清楚何为数据结构?数据结构:Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。而各数据元素之间的相互关系,又...

    第一部分:Java数据结构

    要理解Java数据结构,必须能清楚何为数据结构?

    数据结构:

    1. Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。
    2. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构。
    3. 而一个数据结构的设计过程分成抽象层、数据结构层和实现层。

    数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构。

    一、Java数据结构之:线性数据结构

    线性数据结构:常见的有一维数组,线性表,栈,队列,双队列,串。

    1:一维数组

    在Java里面常用的util有:String [],int [],ArrayList,Vector,CopyOnWriteArrayList等。及可以同过一维数组[]自己实现不同逻辑结构的Util类。而ArrayList封装了一些[]的基本操作方法。ArrayList和Vector的区别是:Vector是线程安全的,方法同步。CopyOnWriteArrayList也是线程安全的但效率要比Vector高很多。(PS:如果不懂出门右拐看另一篇chat)。

    数组这种数据结构典型的操作方法,是根据下标进行操作的,所以insert的的时候可以根据下标插入到具体的某个位置,但是这个时候它后面的元素都得往后面移动一位。所以插入效率比较低,更新,删除效率也比较低,而查询效率非常高,查询效率时间复杂度是1。

    2: 线性表

    线性表是有序的储存结构、链式的储存结构。链表的物理储存空间是不连续的,链表的每一个节点都知道上一个节点、或者下一个节点是谁,通常用Node表示。常见的有顺序链表(LinkedList、Linked***),单项链表(里面只有Node类),双向链表(两个Node类),循环链表(多个Node类)等。

    操作方法:插入效率比较高,插入的时候只需要改变节点的前后节点的连接即可。而查询效率就比较低了,如果实现的不好,需要整个链路找下去才能找到应该找的元素。所以常见的方法有:add(index,element),addFirst(element),addLast(element)。getFirst(),getLast(),get(element)等。

    常见的Uitil有:LinkedList,LinkedMap等,而这两个JDK底层也做了N多优化,可以有效避免查询效率低的问题。当自己实现的时候需要注意。其实树形结构可以说是非线性的链式储存结构。

    3: 栈Stack

    栈,最主要的是要实现先进后出,后进先出的逻辑结构。来实现一些场景对逻辑顺序的要求。所以常用的方法有push(element)压栈,pop()出栈。

    java.util.Stack。就实现了这用逻辑。而Java的Jvm里面也用的到了此种数据结构,就是线程栈,来保证当前线程的执行顺序。

    4:队列

    队列,队列是一种特殊的线性数据结构,队列只能允许在队头,队尾进行添加和查询等相关操作。队列又有单项有序队列,双向队列,阻塞队列等。

    Queue这种数据结构注定了基本操作方法有:add(E e)加入队列,remove(),poll()等方法。

    队列在Java语言环境中是使用频率相当高的数据结构,所有其实现的类也很多来满足不同场景。


    使用场景也非常多,如线程池,mq,连接池等。

    5:串

    串:也称字符串,是由N个字符组成的优先序列。在Java里面就是指String,而String里面是由chat[]来进行储存。

    KMP算法: 这个算法一定要牢记,Java数据结构这本书里面针对字符串的查找匹配算法也只介绍了一种。关键点就是:在字符串比对的时候,主串的比较位置不需要回退的问题。

    二、Java数据结构之:非线性数据结构

    非线性数据结构:常见的有:多维数组,集合,树,图,散列表(hash).

    1:多维数组

    一维数组前面咱也提到了,多维数组无非就是String [][],int[][]等。Java里面很少提供这样的工具类,而java里面tree和图底层的native方法用了多维数组来储存。

    2:集合

    由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。

    Collection

    3:树

    树形结构,作者觉得它是一种特殊的链形数据结构。最少有一个根节点组成,可以有多个子节点。树,显然是由递归算法组成。

    树的特点:

    1. 在一个树结构中,有且仅有一个结点没有直接父节点,它就是根节点。
    2. 除了根节点,其他结点有且只有一个直接父节点
    3. 每个结点可以有任意多个直接子节点。

    树的数据结构又分如下几种:

    • 1) 自由树/普通树:对子节点没有任何约束。

      自由树

    • 2) 二叉树:每个节点最多含有两个子节点的树称为二叉树。

      2.1) 一般二叉树:每个子节点的父亲节点不一定有两个子节点的二叉树成为一般二叉树。

      2.2) 完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;

      2.3) 满二叉树:所有的节点都是二叉的二叉树成为满二叉树。

      二叉树

    • 3) 二叉搜索树/BST:binary search tree,又称二叉排序树、二叉查找树。是有序的。要点:如果不为空,那么其左子树节点的值都小于根节点的值;右子树节点的值都大于根节点的值。

      二叉搜索树

      3.1) 二叉平衡树:二叉搜索树,是有序的排序树,但左右两边包括子节点不一定平衡,而二叉平衡树是排序树的一种,并且加点条件,就是任意一个节点的两个叉的深度差不多(比如差值的绝对值小于某个常数,或者一个不能比另一个深出去一倍之类的)。这样的树可以保证二分搜索任意元素都是O(log n)的,一般还附带带有插入或者删除某个元素也是O(log n)的的性质。

      为了实现,二叉平衡树又延伸出来了一些算法,业界常见的有AVL、和红黑算法,所以又有以下两种树:

      3.1.1) AVL树:最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。

      3.1.2) 红黑树:通过制定了一些红黑标记和左右旋转规则来保证二叉树平衡。

      红黑树的5条性质:

      1. 每个结点要么是红的,要么是黑的。
      2. 根结点是黑的。
      3. 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。
      4. 如果一个结点是红的,那么它的俩个儿子都是黑的。
      5. 对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

      红黑树

    • 4) B-tree:又称B树、B-树。又叫平衡(balance)多路查找树。树中每个结点最多含有m个孩子(m>=2)。它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。

      B-tree

    • 4) B+tree:又称B+。是B-树的变体,也是一种多路搜索树。

      B+tree

    树总结:
    树在Java里面应用的也比较多。非排序树,主要用来做数据储存和展示。而排序树,主要用来做算法和运算,HashMap里面的TreeNode就用到了红黑树算法。而B+树在数据库的索引原理里面有典型的应用。

    4:Hash

    Hash概念:

    • Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),变换成固定长度的输出,该输出就是散列值。一般通过Hash算法实现。

    • 所谓的Hash算法都是散列算法,把任意长度的输入,变换成固定长度的输出,该输出就是散列值.(如:MD5,SHA1,加解密算法等)

    • 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

    Java中的hashCode:

    • 我们都知道所有的class都是Object的子类,既所有的class都会有默认Object.java里面的hashCode的方法,如果自己没有重写,默认情况就是native方法通过对象的内存的+对象的值然后通过hash散列算法计算出来个int的数字。

    • 最大的特性是:不同的对象,不同的值有可能计算出来的hashCode可能是一样的。

    Hash表:

    • Java中数据存储方式最底层的两种结构,一种是数组,另一种就是链表。而Hash表就是综合了这两种数据结构。

    • 如:HashTable,HashMap。这个时候就得提一下HashMap的原理了,默认16个数组储存,通过Hash值取模放到不同的桶里面去。(注意:JDK1.8此处算法又做了改进,数组里面的值会演变成树形结构。)

    • 哈希表具有较快(常量级)的查询速度,及相对较快的增删速度,所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”,我们可以理解为“链表的数组”。

      哈希表

    一致性Hash:

    • 我们查看一下HashMap的原理,其实发现Hash很好的解决了单体应用情况下的数据查找和插入的速度问题。但是毕竟单体应用的储存空间是有限的,所有在分布式环境下,应运而生了一致性Hash算法。

    • 用意和hashCode的用意一样,只不过它是取模放在不同的IP机器上而已。具体算法可以找一下相关资料。

    • 而一致性Hash需要注意的就是默认分配的桶比较多些,而当其中一台机器挂了,影响的面比较小一些。

    • 需要注意的是,相同的内容算出来的hash一定是一样的。既:幂等性。

    • 一致性Hash

    第二部分:Java基本算法

    理解了Java数据结构,还必须要掌握一些常见的基本算法。 理解算法之前必须要先理解的几个算法的概念:

    空间复杂度:一句来理解就是,此算法在规模为n的情况下额外消耗的储存空间。

    时间复杂度:一句来理解就是,此算法在规模为n的情况下,一个算法中的语句执行次数称为语句频度或时间频度。

    稳定性:主要是来描述算法,每次执行完,得到的结果都是一样的,但是可以不同的顺序输入,可能消耗的时间复杂度和空间复杂度不一样。

    一、二分查找算法

    二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。这个是基础,最简单的查找算法了。

        public static void main(String[] args) {
            int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
            System.out.println(binSearch(srcArray, 28));
        }
        /**
         * 二分查找普通循环实现
         *
         * @param srcArray 有序数组
         * @param key 查找元素
         * @return
         */
        public static int binSearch(int srcArray[], int key) {
            int mid = srcArray.length / 2;
    //        System.out.println("=:"+mid);
            if (key == srcArray[mid]) {
                return mid;
            }
    
    //二分核心逻辑
            int start = 0;
            int end = srcArray.length - 1;
            while (start <= end) {
    //            System.out.println(start+"="+end);
                mid = (end - start) / 2 + start;
                if (key < srcArray[mid]) {
                    end = mid - 1;
                } else if (key > srcArray[mid]) {
                    start = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
    

    二分查找算法如果没有用到递归方法的话,只会影响CPU。对内存模型来说影响不大。时间复杂度log2n,2的开方。空间复杂度是2。一定要牢记这个算法。应用的地方也是非常广泛,平衡树里面大量采用。

    二、递归算法

    递归简单理解就是方法自身调用自身。

        public static void main(String[] args) {
            int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
            System.out.println(binSearch(srcArray, 0,15,28));
        }
        /**
         * 二分查找递归实现
         *
         * @param srcArray  有序数组
         * @param start 数组低地址下标
         * @param end   数组高地址下标
         * @param key  查找元素
         * @return 查找元素不存在返回-1
         */
        public static int binSearch(int srcArray[], int start, int end, int key) {
            int mid = (end - start) / 2 + start;
            if (srcArray[mid] == key) {
                return mid;
            }
            if (start >= end) {
                return -1;
            } else if (key > srcArray[mid]) {
                return binSearch(srcArray, mid + 1, end, key);
            } else if (key < srcArray[mid]) {
                return binSearch(srcArray, start, mid - 1, key);
            }
            return -1;
        }
    

    递归几乎会经常用到,需要注意的一点是:递归不光影响的CPU。JVM里面的线程栈空间也会变大。所以当递归的调用链长的时候需要-Xss设置线程栈的大小。

    三、八大排序算法

    • 一、直接插入排序(Insertion Sort)
    • 二、希尔排序(Shell Sort)
    • 三、选择排序(Selection Sort)
    • 四、堆排序(Heap Sort)
    • 五、冒泡排序(Bubble Sort)
    • 六、快速排序(Quick Sort)
    • 七、归并排序(Merging Sort)
    • 八、基数排序(Radix Sort)

    八大算法,网上的资料就比较多了。

    吐血推荐参考资料:git hub 八大排序算法详解。此大神比作者讲解的还详细,作者就不在这里,描述重复的东西了,作者带领大家把重点的两个强调一下,此两个是必须要掌握的。

    1:冒泡排序

    基本思想:

    冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    冒泡排序

    以下是冒泡排序算法复杂度:

    平均时间复杂度最好情况最坏情况空间复杂度
    O(n²)O(n)O(n²)O(1)

    冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).

    Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.

    /**
     * 冒泡排序
     *
     * ①. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
     * ②. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
     * ③. 针对所有的元素重复以上的步骤,除了最后一个。
     * ④. 持续每次对越来越少的元素重复上面的步骤①~③,直到没有任何一对数字需要比较。
     * @param arr  待排序数组
     */
    public static void bubbleSort(int[] arr){
        for (int i = arr.length; i > 0; i--) {      //外层循环移动游标
            for(int j = 0; j < i && (j+1) < i; j++){    //内层循环遍历游标及之后(或之前)的元素
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    System.out.println("Sorting: " + Arrays.toString(arr));
                }
            }
        }
    }
    

    2:快速排序

    快速排序

    快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:

    ①. 从数列中挑出一个元素,称为”基准”(pivot)。

    ②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

    ③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

    代码实现:

    用伪代码描述如下:

    ①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。

    ②.j--,由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

    ③.i++,由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

    ④.再重复执行②,③二步,直到i==j,将基准数填入a[i]中。

    快速排序采用“分而治之、各个击破”的观念,此为原地(In-place)分区版本。

    快速排序 In-place

    /**
     * 快速排序(递归)
     *
     * ①. 从数列中挑出一个元素,称为"基准"(pivot)。
     * ②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
     * ③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
     * @param arr   待排序数组
     * @param low   左边界
     * @param high  右边界
     */
    public static void quickSort(int[] arr, int low, int high){
        if(arr.length <= 0) return;
        if(low >= high) return;
        int left = low;
        int right = high;
        int temp = arr[left];   //挖坑1:保存基准的值
        while (left < right){
            while(left < right && arr[right] >= temp){  //坑2:从后向前找到比基准小的元素,插入到基准位置坑1中
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= temp){   //坑3:从前往后找到比基准大的元素,放到刚才挖的坑2中
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;   //基准值填补到坑3中,准备分治递归快排
        System.out.println("Sorting: " + Arrays.toString(arr));
        quickSort(arr, low, left-1);
        quickSort(arr, left+1, high);
    }
    

    以下是快速排序算法复杂度:

    平均时间复杂度最好情况最坏情况空间复杂度
    O(nlog₂n)O(nlog₂n)O(n²)O(1)(原地分区递归版)

    快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高.


    最后,作者希望让大家对《Java数据结构》整体有个全面的了解,知道什么是数据结构,离我们工作中有多远,而不是一个深不可测的神秘物件。里面的细节,篇幅有限可能不能描述完,但是只要同学们的方向没有搞错,那只要针对每个点再详细的看看即可。

    面试和工作,这些都是离不开的,当同学们有个完整的认识之后,一定要在工作中留心,留意每个用到的地方。

    更多精彩教程,请关注公众号:Java开发教程视频      


    展开全文
  • 图解Java数据结构和算法

    千人学习 2019-06-21 15:26:41
    教程内容:本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀...
  • Java基本数据结构

    千次阅读 2019-05-14 10:57:59
    数据结构: 线性表: 最常用的、最简单的数据结构,它是n个数据元素的有限序列、 实现线性表:输出存储线性表元素,即是用一组连续的存储单元,依次存储线性表数据元素,另一种是使用链表存储线性表元素,用一组...

    数据结构:

    • 线性表:

    最常用的、最简单的数据结构,它是n个数据元素的有限序列、

    实现线性表:输出存储线性表元素,即是用一组连续的存储单元,依次存储线性表数据元素,另一种是使用链表存储线性表元素,用一组任意的存储单元存储线性表的数据元素(存储单元可以连续,可以不连续)。

    先进后出

    • 队列

    一段添加元素。另一端取出元素。入队出队。使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

    • 链表

    物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个节点,一个是存储元素的数据域(存储空间),另外一个是指向下一个节点的指针域。根据指针的指向,链表形成不同的结构,例如单链表、双链表,循环链表

    链表优点:不需要初始化容量,可以任意加减元素,添加或删除元素只需要改变前后两个元素节点的指针域指向地址即可,所以添加,删除很快

    缺点:含有大量指针域,占用空间大,需要查找元素需要遍历链表来查找,比较耗时。

    使用场景:数据量小,需要频繁增加,删除的操作。

    一种数据结构,由n(n>=1)个有限节点组成的具有层级关系的集合。它看起来像倒挂的树,根朝上,叶朝下,具有以下特点:

    每个节点有零个或多个子节点

    没有父节点的节点是根节点

    每一个非根节有且只有一个父节点

    除了根节点,没格子节点可以分为多个不想交的子树。

    二叉树,是树中特殊的一种:

    每个节点最多有两颗子树,节点的度最多为2

    左子树和右子树是有顺序的,次序不能颠倒。

    即使某个节点只有一个子树,也要区分左右子树。

    二叉树是折中的方案,添加删除元素很快,在查找方面也有自己的算法优化,所以二叉树基友链表的好处,也有数组的好处,是两者的优化方法,在处理大批量动态数据方面非常有用。

    拓展:平衡二叉树、红黑树。B+树等。这些数据结构二叉树的基础上衍生了很多功能,在实际应用中广泛用到,例如Mysql索引结构用的是B+树,还有HashMap底层源码是红黑树

    Collection接口和Map接口区别:

    Collection(源自于java.util.Collection)和Map是java集合框架中两个基本的集合类型,要区别不统集合,首先要从Collection和Map开始。Collection接口是传统的集合接口,可以把单个对象存储起来,而Map接口是映射接口,存储的是键值对。

    Collection

    List

    Set

    LinkList

    ArrayList

    Vector

    HashSet

    TreeSet

    LinkedHashSet

               

    Map

     

    HashMap

    HashTable

    LinkedHashMap

    TreeMap

           

     

     

     

     

    List(interface)是一种链表, 有序可重复 List可以通过index指导元素的位置,允许重复元素,ArrayList(允许所有元素包括null)   

     

    LinkedList(双向链表结构) 

     Vector可以实现List接口。类似于ArrayList,但是Vector是同步的,由Vector创建的Iterator,虽然和ArrayList是同一接口,但是因为Vector是同步的,当一个Iterator(迭代器)被创建而且正在被使用时,另一个线程改变了Vector的状态(例如删除一些元素),这时调用Iterator方法将抛出ConcurrentModificationException(同事发生),因此异常必须捕获。

     

    Vector是线程安全的,因为Vector好多方法是sychornized关键字修饰的,比如addElement方法:

    Public syschronized void addElement(E obj){

          modCount++;

    ensureCapatityHelper(elementCount+1);

    elementData[elementCount++]=obj;

    }

    这样在多线程并发访问Vector实例的时候,保证某一刻最多只有一个线程调用Vector中被syschornized修饰的方法。

    反观List,在ArrayList中的add方法:

    Public Boolean add(E e){

          ensureCapacityInternal (size+1);

          elementData[size++]=e;

          reture true;

    }

    有可能同一时候有一个以上线程访问该方法。

    我们知道size++运算过程不是原子操作,有可能被中断。那么如果在size++过程中被中断,而另外一个线程恰好执行了一次这样的方法,就会造成脏数据产生。

    拓展:什么是原子操作?

    原子操作(atomic operation)是不需要syschronized(同步),这是多线程编程老生常谈了,所谓原子操作指的是·不会被线程调度机制打断的操作,这样操作一开始,就一直运行,一直运行到结束,中间不会有任何context switch 切换到另外一个线程。通常所说的原子操作包括对非long和double型的primitive进行赋值,以及返回这两者之外的primitive。之所以要把它们排除在外是因为它们都比较大,而JVM的设计规范又没有要求读操作和赋值操作必须是原子操作(JVM可以试着去这么作,但并不保证)。

    如果这个操作所处的层(layer)的更高层不能发现其内部实现与结构,这个操作就是原子操作。

    原子操作可以是个步骤,也可以是多个不走,但是其顺序不可以被打乱,也不能被切割,只执行其中一部分。将整个操作作为一个整体是原子性的核心特征。

    在单处理器系统中,能够在单条指令中完成的操作就可以认为原子操作,因为中断只能发生在指令之间,这也是CPU指令系统引入的test_and_set  / test_and clear等指令用于临界资源互斥的原因,但是在对称多处理器(Symmetric Multi-Processor)结构中就不同了,由于系统有多个处理器在独立运行,即使在单条指令中完成操作也有可能受到干扰。

     

     

    如果你代码进程中有多个进程在同时进行,而这些线程可能同时会同时运行这段代码,如果运行结果和单线程运行的结果是一样的,而且其他的变量也和预期值一样,是线程安全的。

    或者说:一个类或者程序所提供的接口对于线程来说是原子操作或者多个线程之间的切换不会导致该接口的执行结果存在二义性,也就是说我们不用考虑同步的问题。

    线程安全问题都是由全局变量及静态变量引起的。

    若每个线程中对全局变量、静态变量只有读操作,而无写操作,一般来说,这个全局变量是线程安全的;若有多个线程同时执行写操作,一般都需要考虑线程同步,否则的话就可能影响线程安全。

    比如上例中一个 ArrayList 类,在添加一个元素的时候,它可能会有两步来完成:1. 在 Items[Size] 的位置存放此元素;2. 增大 Size 的值。

    在单线程运行的情况下,如果 Size = 0,添加一个元素后,此元素在位置 0,而且 Size=1;

    而如果是在多线程情况下,比如有两个线程,线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停,线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素,因为此时 Size 仍然等于 0 (注意哦,我们假设的是添加一个元素是要两个步骤哦,而线程A仅仅完成了步骤1),所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行,都增加 Size 的值。

    那好,我们来看看 ArrayList 的情况,元素实际上只有一个,存放在位置 0,而 Size 却等于 2。这就是“线程不安全”了

    也就是说像HashTable和Vector这样的容器实现了线程安全,是通过同步关键字实现的。

     

    此外,我们又注意到,不管是Vector还是List容器,都有可能会出现ConCurrenceModificationException的异常。这是因为几乎所有的集合类都有快速失败的(Fail-Fast)校验机制。这是为了确保集合方法一致而设立的保护措施。他的实现原理就是modCount修改计数器。如在遍历列表的时候(使用迭代器的方式),这时候会保存当前的modCount值,当每次迭代器取值的时候,会通过checkForComodification()方法来校验modCount是否发生了改变。如果发生了改变,就会抛出ConCurrenceModificationException的异常。

     

    public E next() {

                checkForComodification();

                int i = cursor;

                if (i >= size)

                    throw new NoSuchElementException();

                Object[] elementData = ArrayList.this.elementData;

                if (i >= elementData.length)

                    throw new ConcurrentModificationException();

                cursor = i + 1;

                return (E) elementData[lastRet = i];

            }

    final void checkForComodification() {

                if (modCount != expectedModCount)

                    throw new ConcurrentModificationException();

            }

     那么,即使是使用Vector仍可能会抛出这种异常,这是不是和它声称的线程安全所相悖呢?

     

    其实这里的异常和线程同步是两码事。因为使用迭代器遍历容器的时候,这是记录了modCount值,然后调用了remove方法,这在单线程中本来就是不允许的,和多线程同步没有关系。

     

    线程同步是为了实现线程安全,而在Vector中则是实现了线程的部分安全。

    线程安全性不是一个非真即假的命题。 Vector 的方法都是同步的,并且 Vector 明确地设计为在多线程环境中工作。但是它的线程安全性是有限制的,即在某些方法之间有状态依赖(类似地,如果在迭代过程中 Vector 被其他线程修改,那么由 Vector.iterator() 返回的 iterator会抛出ConcurrentModifiicationException。

     

    Set(interface)无序不可重复,HashSet,LinkedHashSet,TreeSet可以实现set接口。Set是一种不包含重复元素的Collection,即任意两个元素e1和e2都是有e1.equals(e2)=false, set最多有一个null元素。因此set的构造函数有一个约束条件,传入的Collection参数不能包含重复元素。但是必须小心操作可变对像(Mutable Object).如果一个set的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

     

    Map接口:也是接口,但是没有继承collection接口,描述了从不重复的键到值的映射,键值对,

    HashMap散列表,基于哈希表实现,就是键值对的映射关系,元素顺序不固定,适合对元素插入删除定位等操作。

    TreeMap:红黑树实现,TreeMap的元素保持着某种固定的顺序,更加适合对元素的遍历。

    Iterator接口:所有实现Iterator接口方法能以迭代方式逐个访问集合中的各元素,并可以从Collection中除去适当的元素。

    Iterator it=a.iterator();

            while (it.hasNext()){

               String ob=(String)it.next();

                System.out.println(ob);

            }.

    Hsahtable类:继承Map接口,实现key-value的哈希表。HashMap几乎可以等价于Hashtable,除了HashMap是非synchronized的,并可以接受null(HashMap可以接受为null的键值(key)和值(value),而Hashtable则不行)。

          Comparable接口:可用于比较的实现,可以实现compareTo方法。Entity层实现Comparabel接口<UserBean>

    展开全文
  • java数据结构有哪些?

    千次阅读 多人点赞 2018-12-28 17:26:11
    Java中有几种常用的数据结构,主要分为Collection和map两个主要接口(接口只提供方法,并不提供实现),而程序中最终使用的数据结构是继承自这些接口的数据结构类。 Collection----&gt;Collections Map--...

    Java中有几种常用的数据结构,主要分为Collection和map两个主要接口(接口只提供方法,并不提供实现),而程序中最终使用的数据结构是继承自这些接口的数据结构类。

    Collection---->Collections   

    Map----->SortedMap------>TreeMap          Map------>HashMap

    Collection---->List----->(Vector \ ArryList \ LinkedList)                                                          

    Collection---->Set------>(HashSet \ LinkedHashSet \ SortedSet)


    List(接口)

    List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下 >标)来访问List中的元素,这类似于Java的数组。

    Vector

    基于数组(Array)的List,其实就是封装了数组所不具备的一些功能方便我们使用,所以它难易避免数组的限制,同时性能也不可能超越数组。所以,在可能的情况下,我们要多运用数组。另外很重要的一点就是Vector是线程同步的(sychronized)的,这也是Vector和ArrayList 的一个的重要区别。 

    ArrayList

    同Vector一样是一个基于数组上的链表,但是不同的是ArrayList不是同步的。所以在性能上要比Vector好一些,但是当运行到多线程环境中时,可需要自己在管理线程的同步问题。

    LinkedList

    LinkedList不同于前面两种List,它不是基于数组的,所以不受数组性能的限制。 
    它每一个节点(Node)都包含两方面的内容: 
    1.节点本身的数据(data); 
    2.下一个节点的信息(nextNode)。 
    所以当对LinkedList做添加,删除动作的时候就不用像基于数组的ArrayList一样,必须进行大量的数据移动。只要更改nextNode的相关信息就可以实现了,这是LinkedList的优势。

    List总结

    所有的List中只能容纳单个不同类型的对象组成的表,而不是Key-Value键值对。例如:[ tom,1,c ]
    所有的List中可以有相同的元素,例如Vector中可以有 [ tom,koo,too,koo ]
    所有的List中可以有null元素,例如[ tom,null,1 ]
    基于Array的List(Vector,ArrayList)适合查询,而LinkedList 适合添加,删除操作

    Set(接口)

    Set是不包含重复元素的Collection

    HashSet

    虽然Set同List都实现了Collection接口,但是他们的实现方式却大不一样。List基本上都是以Array为基础。但是Set则是在 HashMap的基础上来实现的,这个就是Set和List的根本区别。HashSet的存储方式是把HashMap中的Key作为Set的对应存储项。看看 HashSet的add(Object obj)方法的实现就可以一目了然了。

    LinkedHashSet

    HashSet的一个子类,一个链表。

    SortedSet

    有序的Set,通过SortedMap来实现的。

    Map(接口)

    Map 是一种把键对象和值对象进行关联的容器,而一个值对象又可以是一个Map,依次类推,这样就可形成一个多级映射。对于键对象来说,像Set一样,一个 Map容器中的键对象不允许重复,这是为了保持查找结果的一致性;如果有两个键对象一样,那你想得到那个键对象所对应的值对象时就有问题了,可能你得到的并不是你想的那个值对象,结果会造成混乱,所以键的唯一性很重要,也是符合集合的性质的。当然在使用过程中,某个键所对应的值对象可能会发生变化,这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求,你可以将任意多个键都映射到一个值对象上,这不会发生任何问题(不过对你的使用却可能会造成不便,你不知道你得到的到底是那一个键所对应的值对象)。

    HashMap

    基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。另外,HashMap是非线程安全的,也就是说在多线程的环境下,可能会存在问题,而Hashtable是线程安全的。

    TreeMap

    TreeMap则是对键按序存放,

    HashTable

    (1)Hashtable 是一个散列表,它存储的内容是键值对(key-value)映射。

    (2)Hashtable 继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口。

    (3)Hashtable 的函数都是同步的,这意味着它是线程安全的。它的key、value都不可以为null。

    几个常用类的区别 

    1.ArrayList: 元素单个,效率高,多用于查询 
    2.Vector: 元素单个,线程安全,多用于查询 
    3.LinkedList:元素单个,多用于插入和删除 
    4.HashMap: 元素成对,元素可为空 
    5.HashTable: 元素成对,线程安全,元素不可为空 

    Vector、ArrayList和LinkedList 

    大多数情况下,从性能上来说ArrayList最好,但是当集合内的元素需要频繁插入、删除时LinkedList会有比较好的表现,但是它们三个性能都比不上数组,另外Vector是线程同步的。所以: 
    如果能用数组的时候(元素类型固定,数组长度固定),请尽量使用数组来代替List; 
    如果没有频繁的删除插入操作,又不用考虑多线程问题,优先选择ArrayList; 
    如果在多线程条件下使用,可以考虑Vector; 
    如果需要频繁地删除插入,LinkedList就有了用武之地; 
    如果你什么都不知道,用ArrayList没错。 

    栈是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后
    的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

    队列

    一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行
    插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

    数组

    在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数
    据元素的集合称为数组。在C语言中, 数组属于构造数据类型。一个数组可以分解为多个数组元素,这些数组
    元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同,数组又可分为数值数组、字符数组、指
    针数组、结构数组等各种类别。

    链表

    一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
    链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:
    一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

    树是包含n(n>0)个结点的有穷集合K,且在K中定义了一个关系N,N满足 以下条件:
    (1)有且仅有一个结点 k0,他对于关系N来说没有前驱,称K0为树的根结点。简称为根(root)
    (2)除K0外,k中的每个结点,对于关系N来说有且仅有一个前驱。
    (3)K中各结点,对关系N来说可以有m个后继(m>=0)。

    在计算机科学中,堆是一种特殊的树形数据结构,每个结点都有一个值。通常我们所说的堆的数据结构,是指
    二叉堆。堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆。

    散列表

    若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称
    这个对应关系f为散列函数(Hash function),按这个思想建立的表为散列表。

    展开全文
  • java数据结构算法

    千人学习 2019-12-05 11:01:40
    做一门精致,全面详细的 java数据结构与算法!!! 让天下没有难学的数据结构, 让天下没有难学的算法, 不吹不黑,我们的讲师及其敬业,可以看到课程视频,课件,代码的录制撰写,都是在深夜,如此用心,其心可鉴,他不...
  • Java数据结构及原理实现

    千次阅读 2019-08-01 15:17:16
    程序设计主要是数据结构+算法,而数据结构在面向对象思维里是“容器”的意思,数据结构主要...所以下面就简单介绍java数据结构的体系和部分原理实现java集合体系结构图集合父接口Collection,Map和集合工具类Collect

    程序设计主要是数据结构+算法,而数据结构在面向对象思维里是“容器”的意思,数据结构主要负责数据的添加,删除,修改,查找及对数据的其他操作。编程里面对着不同问题场景,选择哪种数据结构进行操作就非常重要。试想:如果谷歌是以数组来存储数据的话,还会有那么快的搜索速度?所以下面就简单介绍java数据结构的体系和部分原理实现

    总体思路:

    1. java集合体系结构图
    2. 集合父接口Collection,Map和集合工具类Collections
    3. List(列表)
    4. Set(规则集)
    5. Queue(队列
    6. Map(映射类)

    java集合体系结构图

    java集合体系结构图


    集合父接口Collection,Map和集合工具类Collections

    Collection是java集合框架体系的总接口,其他集合框架都是实现Collection,封装了集合框架的公共操作:add(E),addAll(),remove(E),removeAll(),其方法摘要如下:
    Collection API

    说到集合框架必须提到Collection的工具类Collections,它封装了所有集合的关于算法操作的具体实现静态方法:二分查找,找出集合最大值,集合最小值,打乱集合,以及生成不可修改集合,同步集合(多线程环境下使用),其主要方法API如下:
    Collections  API

    Collections的synchronizedCollection()主要是在原来的方法外添加一个信号量来进行同步操作,其源码实现如下:

    static class SynchronizedCollection<E> implements Collection<E>, Serializable {
        private static final long serialVersionUID = 3053995032091335093L;
        
        final Collection<E> c;  // Backing Collection
        final Object mutex;     // Object on which to synchronize
        
        public boolean add(E e) {
        	//锁定信号量才可以对集合进行操作,在多线程环境下来进行同步,调用的还是原来的方法
            synchronized (mutex) {return c.add(e);}
        }
        
        public boolean remove(Object o) {
        	//锁定信号量才可以对集合进行操作,在多线程环境下来进行同步,调用的还是原来的方法
            synchronized (mutex) {return c.remove(o);}
        }
     }
    

    集合框架Collection的三种主要实现如下:List(列表),Set(散列集,有一个key-value的Map进行维护,其中key值保证Set集合里元素的唯一性),Queue(队列,先进先出,底层实现可以用List列表或者LinkedList链表)

    集合框架的另外一种数据类型的总接口是Map,基于Key-Value进行存储数据的,其中Key键值是不可重复的,主要是通过类的hashCode()和equal()进行保证的


    List(列表)

    List列表允许存储相同元素,插入元素和按照下标获取元素方便,具体实现有ArrayList,LinkedList和Vector,

    1. ArrayList底层基于数组实现的,按顺序存储元素以及快速按照元素下标进行获取元素,不可同步的;

    2. 而Vector底层也是数组,可进行同步操作,在多线程环境下可以使用;

    3. LinkedList链表的具体机制如下图:可以在具体下标位置删除和添加元素,在许多需要根据具体下标添加和删除元素的应用场景下比ArrayList有更好的性能。

    LinkedList

    ArrayList和Vector的部分源码分析:

    //ArrayList的add()方法
     public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //在数组结尾下标添加元素
            elementData[size++] = e;
            return true;
        }
        //ArrayList的remove()方法
        public E remove(int index) {
            rangeCheck(index);
    
            modCount++;
            E oldValue = elementData(index);
            //获取移动的元素的个数
            int numMoved = size - index - 1;
            if (numMoved > 0)
            	//将移除元素的下标位置后的数组元素都往前移一位来填补空位,调用System.arraycopy方法调用虚拟机自带的方法进行操作效率更高
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }
        
        //Vector添加了synchronized 进行同步
        public synchronized void addElement(E obj) {
            modCount++;
            ensureCapacityHelper(elementCount + 1);
            elementData[elementCount++] = obj;
        }
    

    综上:Array List在不需要同步操作及不需要频繁删除任意下标的元素时推荐使用,Vector是在同步场景下使用,LinkedList是在需要频繁删除和添加任意下标的元素时使用

    Set(规则集)

    散列集,不能保证存储元素的顺序,保证存储元素的不可重复性。具体实现由HashSet,LinkedHashSet,TreeSet,

    1. HashSet是哈希散列集,底层由HashMap支持的,主要使用hashCode()和equal()方法确保Key值不可重复性来保证元素的唯一性

    2. LinkedHashSet底层由LinkedHashMap,则可以保证按照元素插入规则集的顺序进行提取。

    3. TreeSet底层是由TreeMap支持的,可以按照Comparable接口对存储对象排序或者Comparator比较器接口进行存储对象的比较排序

    HashSet的具体源码如下所示:

        public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
    	    private transient HashMap<E,Object> map;
    	    // Dummy value to associate with an Object in the backing Map
    	    private static final Object PRESENT = new Object();
    	    
    	    public boolean contains(Object o) {
    	    	//判断是否存在元素就在hashMap中查看是否存在键值Key为元素o
    	        return map.containsKey(o);
    	    }
    	    
    	    public boolean add(E e) {
    	    	//将要存储的元素当作hashMap的key值进行存储,保证存储元素的唯一性
    	    	return map.put(e, PRESENT)==null;
    	    }
        }
    

    Queue(队列)

    队列是一般按照先进先出First-In-First-Out的规则,元素被追加到队列末尾,在队列头进行删除,底层实现可以是数组,也可以是链表。主要实现有PriorityQueue和LinkedList,

    • 其中PriorityQueue优先队列默认情况下以Comparable按照元素的自然顺序进行排序,最小值的元素优先级最高最先删除,也可以传入指定的比较器Comparator进行元素间的比较。

    • 在java.util.concurrent包里有ArrayBlockingQueue,LinkedBlockingQueue等实现同步机制的队列数据结构,有兴趣可以查看源码进行研究。

    ##Map(映射类)
    Map是按照Key-Value进行存储的数据结构,主要实现有HashMap,LinkedHashMap,TreeMap,

    • 在不需要保证元素的顺序情况下,HashMap是非常高效的,主要是通过hashCode()和equal()方法进行哈希化存储的,所以要求存储的对象要实现hashCode()和equal()方法才能提高性能。HashMap具体的内部机制可以看
      高爽|Coder的HashMap深度解析

    • 而LinkedHashMap可以保证存储元素的顺序;可以按照元素的存储顺序或者元素的访问顺序进行排序存储,它的底层是由HashMap加上循环双向链表实现的。其中LinkedHashMap的具体机制可以看 LinkedHashMap及其源码分析

    • TreeMap在遍历排序好的键值是非常高效率的,默认是按照元素的实现Comprable接口方法进行排序的,也可以传入Comparator比较器接口进行比较排序
      以下是TreeMap的put(K key, V value)源码分析

    public V put(K key, V value) {
            Entry<K,V> t = root;
            //若集合为空,那么添加的元素成为TreeMap的根结点
            if (t == null) {
                compare(key, key); // type (and possibly null) check
    
                root = new Entry<>(key, value, null);
                size = 1;
                modCount++;
                return null;
            }
            int cmp;
            Entry<K,V> parent;
            // split comparator and comparable paths
            Comparator<? super K> cpr = comparator;
            //当比较器存在时,使用比较器Comparator
            if (cpr != null) {
                do {
                    parent = t;
                    //使用比较器Comparator对元素的Key值进行比较
                    cmp = cpr.compare(key, t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            else {//当比较器不存在时,使用元素实现Comparable接口的方法
                if (key == null)
                    throw new NullPointerException();
                @SuppressWarnings("unchecked")
                    Comparable<? super K> k = (Comparable<? super K>) key;
                do {
                    parent = t;
                    //使用元素实现Comparable接口的方法进行键值Key的比较
                    cmp = k.compareTo(t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            Entry<K,V> e = new Entry<>(key, value, parent);
            if (cmp < 0)
                parent.left = e;
            else
                parent.right = e;
            fixAfterInsertion(e);
            size++;
            modCount++;
            return null;
        }
    

    以上是最近学习整理的数据结构内容,对于数据结构的学习不单单需要知道各种数据结构的优缺点和应用场景,对于数据结构的源码和算法也是蕴含着很多可以学习的东西。数据结构在程序设计中的应用也非常广泛,比如Sturts的值栈机制就是使用List数据实现的,Mybatis的缓存机制就是使用Map机制进行实现的…

    未来路还很长,继续前进

    展开全文
  • java数据结构

    2020-03-24 20:46:40
    一个数组是相同数据类型的元素按一定顺序排列的集合。使用数组可以将同一类型的数据存储在连续的内存位置。数组中各元素的类型相同,通过下标的方式来访问数组中的元素,下标从0开始。 数组的长度是确定的,数组...
  • Java常用数据结构总结

    千次阅读 2019-10-07 16:32:22
    数据元素相互之间的关系称为结构。有四类基本结构:集合、线性结构、树形结构、图状结构; 集合结构:除了同属于一种类型外,别无其它关系 线性结构:元素之间存在一对一关系常见类型有: 数组,链表,队列,栈,它们之间在...
  • JAVA常用数据结构

    万次阅读 多人点赞 2018-07-30 14:12:59
    所有JAVA开发工程师在日常开发工作中,离不开JAVA常用数据结构,比如List、Map、Set等。对其内部原理的了解能够更好地理解这些数据结构的适用场合,避免使用不当引发的诡异问题。本文将对这些常用的JAVA中的数据结构...
  • java 中几种常用数据结构

    万次阅读 2018-01-16 12:00:22
    Java中有几种常用的数据结构,主要分为Collection和map两个主要接口(接口只提供方法,并不提供实现),而程序中最终使用的数据结构是继承自这些接口的数据结构类。 一、几个常用类的区别  1....
  • 数据结构与算法(java版)

    万次阅读 多人点赞 2018-04-22 17:18:08
    数据结构与算法(java版)标签: java 数据结构 算法2017年12月28日 21:50:08102人阅读 评论(0) 收藏 举报 分类:数据结构与算法转自:http://blog.csdn.net/column/details/datastructureinjava.html 目录...
  • Java递归构建树形数据结构实现多级树形菜单展示

    万次阅读 热门讨论 2018-06-19 09:14:33
    首先看看需求,树形菜单是这样的:根据需求创建数据模型:构造树形数据结构:转为json数据看看结构是否正确:打完收工!
  • 数据结构Java版 第四版 叶和亚

    千次阅读 多人点赞 2019-04-16 08:53:12
    内容目录如下. 链接:https://pan.baidu.com/s/1qHjGaRwD-4BgBm6HEagD_g 提取码:iom1
  • Java数据结构与算法之学习路线

    万次阅读 多人点赞 2016-10-05 16:28:20
    目录: 1.前言 2.数据结构与算法学习大纲(粗糙) 3.线性结构分类 4.各个线性类型数据结构的特点以及使用场景 5.数组与队列的区别 1.前言: ...去做了两道面试题,全是数据结构和算法的题,由于我的java
  • 链接: https://pan.baidu.com/s/135hWyCK3SssLwMmeHn4PCg 提取码: 9kk7
  • 数据结构学习书籍

    千次阅读 2018-03-28 09:49:55
    1.《大话数据结构》 2.《数据结构与算法分析--Java语言描述》 3.《数据结构和抽象问题求解--Java语言描述》 4.《算法导论》
  • 请大神们帮忙给出代码,把数据库的部门生成树形菜单,在后台返回jsonarray 格式为[{id:01 ,name:"01",children[1]}]
  • Java项目的目录结构

    万次阅读 2019-06-04 10:03:22
    叫做数据访问层。 三、Service包 服务层,相比Dao较高层次,可将多种方法封装起来。 四、Po包(Persistant Object) Po将数据库表中的记录在java对象中。也就是一个Po就是一个数据库表中的一个记录。 五、Vo包...
  • SpringBoot项目目录结构(工程结构

    万次阅读 多人点赞 2020-04-03 22:19:58
    一、代码层结构 根目录:com.bajins 1.启动类CsdnApplication.java推荐放在根目录com.bajins包下 2.实体类domain jpa项目: com.bajins.domain mybatis项目: com.bajins.pojo 3.数据接口访问层(Dao) ...
  • Java 面试之数据结构

    万次阅读 多人点赞 2020-03-26 20:20:05
    常见数据结构 HashMap、Hashtable、 ConcurrentHashMap HashMap 底层实现:HashMap底层整体结构是一个数组,数组中的每个元素又是一个链表。每次添加一个对象(put)时会产生一个链表对象(Object类型),...
1 2 3 4 5 ... 20
收藏数 1,122,756
精华内容 449,102
关键字:

java数据结构