Java.数据结构.集合体系详解

「爱情、让人受尽委屈。」 2023-08-17 15:20 159阅读 0赞

[Java.数据结构.集合体系详解][Java._.]

#### I. 第一部分：常见数据结构 ####

首先简单说下数据结构.  
什么是数据结构？数据结构就是组织数据的方式.  
常见的数据结构：栈，堆，树，图，数组，队列，链表.

这里主要介绍与java集合体系相关的栈、数组和链表.

###### 栈 ######

特点：压栈弹栈，先进后出. 
    如：手枪弹夹装弹过程，最先压入的子弹在最下面；而在射击时，最先弹入枪膛的是最上面的子弹，即最后压入弹夹的子弹.

###### 队列 ######

特点：先进先出.
    如：子弹射出的过程，先进入枪膛的子弹最先被射出.

###### 数组 ######

概述：用来存储同一种类型元素的容器。
    特点：在内存中是连续的，每个元素都有编号（从0开始的），方便获取。但增删就比较麻烦，需要将目标位置后的所有数据前移动或后移.
    查询快，增删慢.

###### 链表 ######

概述：把一些结点通过链子连接起来的数据结构。每个结点由地址域和数值域组成.
    特点：增删快，查询慢. 增删时，只需要把所插入处的前后节点链条断开，增加或移除目标节点，速度很快。反之，查询时则需要遍历所有节点，直到找到目标节点，速度自然要慢。

--------------------

#### II. 第二部分：Java中的Collection(集合)体系 ####

![图片取自：http://blog.csdn.net/jiuqiyuliang,感谢作者.][http_blog.csdn.net_jiuqiyuliang_.]

##### 2.1 集合体系概览： #####

集合体系分为4大块：

Collection接口: 
      Collection是最基本集合接口，它定义了一组允许重复的对象.
      它有两个子接口：List和Set.
           1. List下3个实现类：ArrayList, LinkedList, Vector. List是有序的。
              1.1 List接口的三个儿子的特点：
                1.1.1 ArrayList：底层数据结构是数组，查询快，增删慢。线程不安全（不同步），效率高。
                1.1.2 Vector：底层数据结构是数组，查询快，增删慢。线程安全，效率低。
                1.1.3 LinkedList：底层数据结构是链表，增删快，查询慢。 线程不安全的，效率高。
              1.2 如何来选择使用哪个仔呢？
                keywords:  看需求! 
                  step1: 看是否考虑安全? 安全, 则Vector.
                  step2: 如果不考虑安全，那么是查询多还是增删多? 
                         查询多, 则ArrayList; 增删多，则LinkedList.
                  什么都不知道，用ArrayList。
    
           2. Set下2个实现类：HashSet, TreeSet. Set是无序的。

Map接口： 
      该接口描述了从不重复的键到值的映射。Map接口用于维护键/值对.
      特征：它描述了从不重复的键到值的映射.
      两个重要的实现类：HashMap和TreeMap.
           1.HashMap，中文叫散列表，基于哈希表实现，特点就是键值对的映射关系。一个key对应一个Value。
    HashMap中元素的排列顺序是不固定的。更加适合于对元素进行插入、删除和定位。
           2.TreeMap，基于红黑树实现。TreeMap中的元素保持着某种固定的顺序。更加适合于对元素的顺序遍历。

Comaprable接口：
      Comparable可以用于比较的实现，实现了Comparable接口的类可以通过实现comparaTo方法从而确定该类对象的排序方式。

Iterator接口：
      用于循环访问集合中的对象。     
      所有实现了Collection接口的容器类都有iterator方法，用于返回一个实Iterator接口的对象。
      Iterator对象称作迭代器，Iterator接口方法能以迭代方式逐个访问集合中各个元素，并可以从Collection中除去适当的元素。

--------------------

## \#\#\#\#\#2.2 Collection的接口概览(List 和 Set) ##

###### 2.2.1 List接口 ######

三个子类：

ArrayList
    底层数据结构是数组，查询快，增删慢。
    线程不安全（不同步），效率高。

-Vector
    底层数据结构是数组，查询快，增删慢。
    线程安全，效率低。
    特有功能:
      添加：
        void addElement(Object obj);
      获取：
        Object elementAt(int index);
        Enumeration elements(); //它返回此向量的组件的枚举,类似于迭代器Iterator
        boolean hasMoreElements() //类似于hasNext()
        Object nextElement(); //类似于next();

-LinkedList
    底层数据结构是链表，增删快，查询慢。
    线程不安全的，效率高。
    特有方法：
      添加：
        void addFirst(Object obj);//头部添加元素
        void addLast(Object obj);//尾部添加元素
      获取：
        Object getFirst();//获取头部元素
        Object getLast();//获取尾部元素
      删除：
        Object removeFirst();//移除头部元素
        Object removeLast();//移除尾部元素

#问：以后用List体系的那个子类？
      看是否考虑安全。
      安全：用Vector
      不安全：继续考虑是查询多还是增删多
                查询多：ArrayList
                增删多：LinkedList
      什么都不知道，用ArrayList。

#练习题：
    1.一个字符串集合ArrayList中含有如下元素：hello, world, java, hello, .net, java, php, ios, java, android，world。要求编写程序，获得一个没有重复元素的新集合。
    
    #思路：
    1、创建两个集合对象，A，B。
    2、把字符串添加到集合A中。
    3、遍历集合A，并且判断集合B中是否包含A集合当前遍历到的元素。
    4、如果包含，不添加，如果不包含，就将该元素添加到集合B中。
    5、迭代结束后，集合B中存的就是去重后的元素。

###### 练习题 ######

#请用LinkedList来模拟栈的数据结构。
    
    刚我们知道栈的结构为：先进后出.
    咱们可以使用LinkedList集合，对这个类进行包装来实现先进先出的效果，但不能直接使用它。
    具体实现时，先往集合里添加一个新数据，add();  取自己写类，对LinkedList进行封装：
    
    1、需要提供添加元素的方法add()    //内部封装的是：addFirst()
    2、需要提供获取元素的方法get(int index)   //内部封装的是：List体系的get(int index)方法
    3、需要提供获取集合长度的方法size()   //内部分装的是：LinkedList的size()方法
    
    以后遇到类似的题，怎么做？
    
    解题思路：
    1、分析要模拟的数据结构的特点。
    2、对可用的类进行包装，然后提供对应的方法就可以了。

--------------------

##### 2.2 Set集合 #####

set集合的特点: 无序,唯一

###### 2.2.1 HashSet集合 ######

A:底层数据结构是哈希表(是一个元素为链表的数组)  
B:哈希表底层依赖两个方法：hashCode()和equals()

如何保证元素唯一性?  
`由hashCode()和equals()保证的，先调用hashCode()在调用equals().`

执行顺序：

首先比较哈希值是否相同:
      若相同：
        继续执行equals()方法；
          -返回true：元素重复了，不添加；
          -返回false：直接把元素添加到集合；
      若不同：
        就直接把元素添加到集合；

###### 2.2.2 TreeSet集合 ######

A:底层数据结构是红黑树(是一个自平衡的二叉树)  
B:保证元素的排序方式

排序方法：  
a:自然排序(元素具备比较性)：让元素所属的类实现Comparable接口.  
b:比较器排序(集合具备比较性)：让集合构造方法接收Comparator的实现类对象

--------------------

##### 2.3 Map接口概览 #####

Map也是接口，但没有继承Collection接口。该接口描述了从不重复的键到值的映射。Map接口用于维护键/值对（key/value pairs）。  
       特征：它描述了从不重复的键到值的映射。  
       两个重要的实现类：HashMap和TreeMap  
       1.HashMap，中文叫散列表，基于哈希表实现，特点就是键值对的映射关系。一个key对应一个Value。HashMap中元素的排列顺序是不固定的。更加适合于对元素进行插入、删除和定位。  
       2.TreeMap，基于红黑书实现。TreeMap中的元素保持着某种固定的顺序。更加适合于对元素的顺序遍历。

--------------------

#### 总结 ####

###### |-List ######

有序,可重复  
|--ArrayList  
`底层数据结构是数组，查询快，增删慢.`  
`线程不安全，效率高.`  
|--Vector  
`底层数据结构是数组，查询快，增删慢.`  
`线程安全，效率低.`  
|--LinkedList  
`底层数据结构是链表，查询慢，增删快.`  
`线程不安全，效率高.`

###### |-Set ######

无序,唯一  
|--HashSet  
`底层数据结构是哈希表.`  
`保证元素唯一性: 依赖两个方法：hashCode()和equals().`  
|--LinkedHashSet  
`底层数据结构是链表和哈希表`  
`由链表保证元素有序`  
`由哈希表保证元素唯一`  
|--TreeSet  
`底层数据结构是红黑树。`  
`如何保证元素排序? 自然排序; 比较器排序.`  
`如何保证元素唯一性的呢? 根据比较的返回值是否是0来决定.`

4:针对Collection集合我们到底使用谁?  
`唯一么? 是：Set; 否：List.`

`若用Set： 排序么? 是：TreeSet; 否：HashSet. 如果知道是Set，但是不知道是哪个Set，就用HashSet. 要安全吗?是：Vector; 否：ArrayList或者LinkedList.`

`若用List: 查询多：ArrayList 增删多：LinkedList 如果你知道是List，但是不知道是哪个List，就用ArrayList.`

`如果你知道是Collection集合，但是不知道使用谁，就用ArrayList。`  
如果你知道用集合，就用ArrayList。

5:在集合中常见的数据结构(掌握)  
`ArrayXxx:底层数据结构是数组，查询快，增删慢； LinkedXxx:底层数据结构是链表，查询慢，增删快； HashXxx:底层数据结构是哈希表。依赖两个方法：hashCode()和equals()； TreeXxx:底层数据结构是二叉树。两种方式排序：自然排序和比较器排序；`

posted on 2019-08-26 09:07  [Initial-X][] 阅读( ...) 评论( ...) [ 编辑][Link 1] 收藏

转载于:https://www.cnblogs.com/initx/p/11410499.html

[Java._.]: https://www.cnblogs.com/initx/p/11410499.html
[http_blog.csdn.net_jiuqiyuliang_.]: 
[Initial-X]: https://www.cnblogs.com/initx/
[Link 1]: https://i.cnblogs.com/EditPosts.aspx?postid=11410499