Java常见基本数据结构概览

Java数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。在Java数据结构中最常用的类型无外乎以下几种:

Map接口

请注意,Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个value。

Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射。

List接口

List是有序的Collection,用户能够使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于Java的数组。

和下面要提到的Set不同,List允许有相同的元素。

Collection接口

两个标准的构造函数:无参数的构造函数用于创建一个空的Collection;有一个Collection参数的构造函数用于创建一个新的Collection

如何遍历:

Iteratorit=collection.iterator();//获得一个迭代子

while(it.hasNext()){

Objectobj=it.next();//得到下一个元素

}

由Collection接口派生的两个接口是List和Set。

ArrayList类

ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步。

Hashtable类

Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。

添加数据使用put(key,value),取出数据使用get(key),这两个基本操作的时间开销为常数。Hashtable通过initialcapacity和loadfactor两个参数调整性能。通常缺省的loadfactor0.75较好地实现了时间和空间的均衡。增大loadfactor可以节省空间但相应的查找时间将增大,这会影响像get和put这样的操作。

使用Hashtable的简单示例如下,将1,2,3放到Hashtable中,他们的key分别是“one”,“two”,“three”:

Hashtablenumbers=newHashtable();

numbers.put(“one”,newInteger(1));

numbers.put(“two”,newInteger(2));

numbers.put(“three”,newInteger(3));

要取出一个数,比如2,用相应的key:

Integern=(Integer)numbers.get(“two”);

由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object,如果你用自定义的类当作key的话,要相当小心,按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)==true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同,如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。

如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),要避免这种问题,只需要牢记一条:要同时复写equals方法和hashCode方法,而不要只写其中一个。

Hashtable是同步的。

Stack类

Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

Set接口

Set是一种不包含重复的元素的Collection,即任意的两个元素e1和e2都有e1.equals(e2)==false,Set最多有一个null元素。

很明显,Set的构造函数有一个约束条件,传入的Collection参数不能包含重复的元素。

请注意:必须小心操作可变对象(MutableObject)。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)==true将导致一些问题。

WeakHashMap类

WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。

Vector类

Vector非常类似ArrayList,但是Vector是同步的。

HashMap类

HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即nullvalue和nullkey。但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者loadfactor过低。

LinkedList类

允许null元素。

此外LinkedList提供额外的get,remove,insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。

注意LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:

Listlist=Collections.synchronizedList(newLinkedList(...));

总结

以上就是本文的全部内容,本站有更多关于数据结构的详细和具体介绍。希望对大家有所帮助。

(0)

相关推荐

  • java数据结构与算法之插入排序详解

    本文实例讲述了java数据结构与算法之插入排序.分享给大家供大家参考,具体如下: 复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅. 排序 1.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键

  • java数据结构与算法之希尔排序详解

    本文实例讲述了java数据结构与算法之希尔排序.分享给大家供大家参考,具体如下: 这里要介绍的是希尔排序(缩小增量排序法). 希尔排序:通过比较相距一定间隔的元素来工作:各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止.是插入排序的一种,是针对直接插入排序算法的改进. 算法思想:先将要排序的序列按某个增量d分成若干个子序列,对每个子序列中全部元素分别进行直接插入排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序.当增量减到1时,整个要排序的数被分成一

  • 浅析Java 数据结构常用接口与类

    Java工具包提供了强大的数据结构.在Java中的数据结构主要包括以下几种接口和类: 枚举(Enumeration) 位集合(BitSet) 向量(Vector) 栈(Stack) 字典(Dictionary) 哈希表(Hashtable) 属性(Properties) 以上这些类是传统遗留的,在Java2中引入了一种新的框架-集合框架(Collection),我们后面再讨论. 枚举(Enumeration) 枚举(Enumeration)接口虽然它本身不属于数据结构,但它在其他数据结构的范畴里

  • java数据结构与算法之快速排序详解

    本文实例讲述了java数据结构与算法之快速排序.分享给大家供大家参考,具体如下: 交换类排序的另一个方法,即快速排序. 快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进:实现了一次交换可消除多个逆序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 步骤: 1.从数列中挑出一个元素,称为 "基准"(piv

  • Java数据结构之散列表(动力节点Java学院整理)

    基本概念 散列表(Hash table,也叫哈希表),是根据关键字(key value)而直接进行访问的数据结构. 说的具体点就是它通过吧key值映射到表中的一个位置来访问记录,从而加快查找的速度. 实现key值映射的函数就叫做散列函数 存放记录的数组就就叫做散列表 实现散列表的过程通常就称为散列(hashing),也就是常说的hash 散列 这里的散列的概念不仅限于数据结构了,在计算机科学领域中,散列-哈希是一种对信息的处理方法,通过某种特定的函数/算法(散列函数/hash()方法)将要检索的

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • Java数据结构之图(动力节点Java学院整理)

    1,摘要: 本文章主要讲解学习如何使用JAVA语言以邻接表的方式实现了数据结构---图(Graph).从数据的表示方法来说,有二种表示图的方式:一种是邻接矩阵,其实是一个二维数组:一种是邻接表,其实是一个顶点表,每个顶点又拥有一个边列表.下图是图的邻接表表示. 从图中可以看出,图的实现需要能够表示顶点表,能够表示边表.邻接表指是的哪部分呢?每个顶点都有一个邻接表,一个指定顶点的邻接表中,起始顶点表示边的起点,其他顶点表示边的终点.这样,就可以用邻接表来实现边的表示了.如顶点V0的邻接表如下: 与

  • Java常见基本数据结构概览

    Java数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科.在Java数据结构中最常用的类型无外乎以下几种: Map接口 请注意,Map没有继承Collection接口,Map提供key到value的映射.一个Map中不能包含相同的key,每个key只能映射一个value. Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射. List接口 List是有序的Collection,用户能

  • Java常见基础数据结构

    目录 栈: 队列: 数组: 链表: 红黑树: 总结 栈: stack,又称堆栈,他是运算受限的线性表,其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行添加.查找.删除等操作. 简单的来说,采用该结构的集合,对元素的存取有如下几个特点 1.先进后出. 2.栈的入口.出口都是栈的顶端位置. 压栈:就是存元素,把元素存储到栈的顶端位置,栈中已有元素一次向栈底方向移动一个位置. 弹栈:就是取元素,把栈顶端的元素取出,栈中已有元素依次向栈顶方向移动一个位置. 队列: queue,简称队

  • 浅谈Java常见的排序算法

    目录 一.直接插入排序 二. 希尔排序 三.冒泡排序 四.快速排序 五.选择排序(Selection Sort) 六.堆排序 七.归并排序 一.直接插入排序 基本思想: 将一个记录插入到已排序的有序表中,使插入后的表仍然有序 对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序 package Sort; //插入排序 public class InsertSort { public static void main(String[] args) { int [] ar

  • Java深入了解数据结构之哈希表篇

    目录 1,概念 2,冲突-避免 3,冲突-避免-哈希函数设计 4,冲突-避免-负载因子调节 5,冲突-解决-闭散列 ①线性探测 ②二次探测 6,冲突-解决-开散列/哈希桶 7,完整代码 1,概念 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键 码的多次比较.顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( ),搜索的效率取决于搜索过程中 元素的比较次数. 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素. 如果构造一

  • Java深入了解数据结构之优先级队列(堆)

    目录 一,二叉树的顺序存储 ①存储方式 ②下标关系 ③二叉树顺序遍历 二,堆 ①概念 ②操作-向下调整 ③建堆(建大堆为例) 三,堆的应用-优先级队列 ①概念 ②内部原理 ③入队列 ④出队列(优先级最高) ⑤返回队首元素(优先级最高) 四,堆排序 一,二叉树的顺序存储 ①存储方式 使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中. 一般只适合表示完全二叉树,因为非完全二叉树会有空间的浪费. 这种方式的主要用法就是堆的表示. ②下标关系 已知双亲(parent)的下标,则: 左孩子(

  • Java 精炼解读数据结构的顺序表如何操作

    目录 前言 一.什么是顺序表 顺序表的概念及结构 创建顺序表 获取顺序表长度 在pos位置新增元素 判定是否包含某个元素 查找某个元素对应的位置 获取pos位置的元素 给pos位置的元素设为value 删除你想要删除的元素 总结: 前言 线性表(linear list)是n个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见 的线性表:顺序表.链表.栈.队列.字符串... 线性表在逻辑上是线性结构,也就说是连续的一条直线.但是在物理结构上并不一定是连续的,线性表在物

  • 有关Java常见的误解小结(来看一看)

    误解一:JavaScript是Java的简易版 JavaScript是一种在网页中使用的脚本语言,它的原名叫做LiveScript.JavaScript的语法与Java类似.除此之外,他们再无任何关系.JavaScript的一个子集已经标准化为ECMA-262,它更加紧密地与浏览器集成在一起. 误解二:所有的Java程序都是在网页中运行的 严格来说,应该是所有的Java applet都是在页面中运行的.applet是一种运行在浏览器之中的Java程序,然而大多数Java程序是运行在Web浏览器之

  • 浅谈Java中常用数据结构的实现类 Collection和Map

    线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构.这些类均在java.util包中.本文试图通过简单的描述,向读者阐述各个类的作用以及如何正确使用这些类. Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ├Hashtable ├HashMap └WeakHashMap Collection接口 Collection是最基本的集合接口,一个C

  • java实现队列数据结构代码详解

    什么是队列结构 一种线性结构,具有特殊的运算法则[只能在一端(队头)删除,在另一端(队尾)插入]. 分类: 顺序队列结构 链式队列结构 基本操作: 入队列 出队列 给出一些应用队列的场景 1):当作业被送到打印机的时候,就可以按到达的顺序排起来,因此每一份作业是队列的节点. 2):售票口的人买票的顺序的按照先来先买的顺序售票. 3):当所有的终端被占用,由于资源有限,来访请求需要放在一个队列中等候. 队列是先进先出的! 我们设置一个叫做LinkQueue<T>的泛型集合类,该类里面有 Node

  • java编程队列数据结构代码示例

    队列是一种特殊的线性表,只允许在表的前端进行删除,在表的后端进行插入,表的前端称为(front)队头,表的后端称为(rear)队尾. 所以队列跟生活的场景很是相似,在电影院买电影票,人们排成一排,第一个人进入队尾最先到达队头后买票进入影院,后面排队的人按照排队的次序买到票后进入影院. 所以 队列是一种先进先出的数据结构(FIFO). 编程实现对循环链队列的入队和出队操作. ⑴根据输入的队列长度n和各元素值建立一个带头结点的循环链表表示的队列(循环链队列),并且只设一个尾指针来指向尾结点,然后输出

随机推荐