java之数据结构|JAVA数据结构之集合 java之数据结构|数据结构

JAVA数据结构之集合集合概述 java语法中的集合，又称为容器，它是一个对象，专门用来管理一组其他对象。集合可以用来存储、检索、操作和统计一组其他对象。在集合内的对象称之为元素。在javaSE API中的java.util包中专门设计了一组接口和类，来实现各种各样的对象存储结构，这样的一组接口和类的设计结构被称为JAVA集合框架。集合的主要接口和常用的实现类的层次结构如下图所示：

文章图片
各个功能模块：Collection接口声明了一组管理其存储的元素的方法，Collection接口继承了Iterator接口，实现这个接口将允许对象成为“for-each”语句的目标，并提供了一个可以返回遍历集合中所有元素的迭代器的Iterator方法。Set接口继承了Collection接口，它代表的是不包含重复元素的集合，往set集合中存放对象时，它会自动调用对象的equals方法来比较是否和Set集合中的已有元素重复。因此，要存放到Set集合中的对象，在对应类中应该重写equals方法和hashCode方法来实现对象相等检查规则。 1、Collection接口 1.1、Set接口
1.1.1、hashSet的实现 HashSet类是Set接口的一个具体实现类，它内部用散列表来保存元素，所以hashSet也常常被称为散列集。HashSet在存放对象时，首先会根据每个对象的hashCode用固定的算法算出它的存储索引，然后把该对象存放在散列表的相应位置中，存放时，如果散列表对应的位置还没有其他元素，就可以直接存放；如果该对应位置有元素了，就会比较该对象是否与相对应位置的对象是否相同（equals方法），是的话那就不需存放，不是的话，那就存放在其后面；另外使用迭代器迭代Set中存放的所有元素时，进会依次访问所有散列表表元，但是无法保证是顺序输出。hashSet实现结构如下所示：
文章图片
1.1.2、LinkedHashSet的实现 LinkedHashSet根据元素的hashCode进行存放，同时用链表记录元素加入的顺序，所以也被称为链式散列集。由于LinkedHashSet会用链表来维护元素的加入顺序，增加了维护链表的资源开销，因此它的效率会相对较低。 1.1.3、TreeSet的实现 TreeSet是Set系列中用来支持元素自然排列的一个集合，它内部采用的是红黑树来存储排列的，所以也被称为树集，每当把一个元素添加给树集时，该元素将被纳入到树状结构的相应的排序位置，也就是说TreeSet会按元素的自然排序来存放每个元素，当树集添加完毕后，所有元素也就自然排序存放好了，由于本人没有去研究过红黑树，所以就没有介绍红黑树的实现原理，但是我上面一篇博客写过二叉搜索树，这个跟红黑树很相似，可以参考一下。
总结：hashSet和linkedHashSet两者的同异异1、hashset的效率比linkedHashSet效率高； 2、hashSet不能保证输出和输入的顺序一致，LinkedHashSet本身有维护输入顺序的链表，所以能保证输入输出顺序一致；同1、hashSet和LinkedHashSet都是通过散列表来实现的，然后都集成了Iterator迭代器； 2、hashSet和LinkedHashSet都是没做同步处理，不是线程安全的容器； 3、hashSet和linkedHashSet都不允许有重复类元插入，需要重写equals和hashCode方法；（测试代码在该博客最下方的github上，有需要可以自行下载）
TreeSet只是多增加了一个排序功能，在查找上的时间复杂度会低，但是插入和删除时间复杂度会相对高。
1.2、List接口
List接口继承了Collection接口，它是一个有序的集合，即它会保存元素存入的顺序，所以也被称为序列。另外还增加了List专用迭代器ListIterator可以按照任意方向进行遍历。list接口有三个实现类：ArrayList、LinkedList、Vector。 1.2.1、ArrayList类 ArrayList是一个变长的对象数组，所以，ArrayList被称为数组列表。也就是说ArrayList可以动态的增加或者是减少其容量，这是通过该类的内部逻辑实现的。ArrayList按照下标读取元素的时间复杂度是O(1)，插入和删除元素最坏是O(n)。ArrayList是通过数组来实现的。 1.2.2、LinkedList类 LinkedList是List接口的另一个常用实现类。它采用双向链表结构来保存元素。在双向链表中的每一个结点上，除了存放元素外，还提供了两个变量用来存放下一个结点的引用和上一个结点的引用，结构如下图所示：
文章图片

1.2.3、Vector类 Vector本身也是和ArrayList一样，由数组组成，只是Vector对该集合进行了同步操作，而ArrayList未做同步操作；
总结：ArrayList和linkedList、Vector三者的同异 1、同步性：ArrayList和LinkedList没有做同步操作，所以非线程安全，Vector实现同步操作，线程安全； 2、数据增加时，ArrayList和Vector检测到满后，自动增加的长度不一样，Vector比arrayList增加的长度大，所以在大量数据存储时候，Vector比ArrayList的效率更高 3、检索、插入、删除操作的效率：ArrayList和Vector由于是数组实现的，所以其读取某一指定位置的元素时间复杂度是O(1)，但是在插入和删除元素是的时间复杂度是O(n),所以ArrayList和Vector在插入和删除元素效率相对低，LinkedList刚好相反，在查找某一位置元素的时间复杂度为O(n)，插入和删除元素的时间复杂度会低。
2、Map接口 Map接口代表映射，该接口描述了从不重复的键到值的映射，Map接口定义了存储键值对的方法，Map中不能有重复的键，Map实现类中存储的映射对都是通过键来唯一识别的，Map实现类的内部都是set来存放映射对的“键”，所以map对应的键应该需要重写HashCode和equals方法。 2.1、HashMap
HashMap是基于散列表的Map接口的实现，它是使用频率最高的一个映射，提供所有的映射操作方法，它内部对“键”用Set进行散列存放。所以根据“键”去取“值”的效率很高，并且允许使用null值和null键，但是不能保证映射对的存放顺序。 HashMap的读取Value有以下几种方式： HashMap中维护了一个Entry的接口，这里存放的是键值对信息，所以读取HashMap的操作有： 1、得到Key，通过key来遍历HashMap

HashMap map=new HashMap(); map.put("abc", "abc"); map.put("def", "def"); map.put("abc", "abc"); map.put(null, null); //通过key来获得所有的Value //得到key的Set集合 Set set=map.keySet(); //得到set集合的迭代器 Iterator iterator=set.iterator(); //通过迭代器拿到每一个Key值 while(iterator.hasNext()){ String key=(String)iterator.next(); //得到Value值 String value=https://www.it610.com/article/map.get(key); System.out.println(value); }

2、得到Entry集合，然后通过Entry集合中的getKey和getValue方法得到每个元素

//得到Entry的set集合 Set entry=map.entrySet(); //得到迭代器 Iterator iter=entry.iterator(); while(iter.hasNext()){ Entry entr=iter.next(); System.out.println(entr.getKey()); System.out.println(entr.getValue()); }

3、得到Entry的KeySet集合，然后得到value方法

//得到keySet集合 Set keySet=map.keySet(); //得到迭代器 Iterator keyDat=keySet.iterator(); //循环查找 while(keyDat.hasNext()){ String key=keyDat.next(); String value=https://www.it610.com/article/map.get(key); System.out.println(value); }

2.2、LinkedHashMap
LinkedHashMap是hashMap的子类，它使用散列表存放键值对，同时又用了双向链表来存放键值映射对加入的顺序。这样就能保证取出的数据和存入的数据顺序一样。测试代码如下：

LinkedHashMap map= new LinkedHashMap(); map.put("123", "123"); map.put("234", "234"); map.put("234", "234"); map.put("345", "345"); //得到输出键值对 Set set1=map.entrySet(); Iterator iterator=set1.iterator(); while(iterator.hasNext()){ Entry e=iterator.next(); System.out.println(e.getKey()); System.out.println(e.getValue()); }

2.3、TreeMap
TreeMap类是根据其键的自然顺序进行排序的，或者根据创建TreeMap对象时提供的比较器实例（实现Comparator接口的类的实例）进行排序，所以输出是一个有序的元素排列。 2.4、HashTable
HashTable和HashMap实现的方式是差不多的，都是通过数组+链表的形式，但是它们有以下不同点： 1、HashTable实现了同步操作，但是HashMap未实现同步操作； 2、HashTable可以通过 Iterator 和 Enumeration来实现数据遍历，而hashMap只实现了Iterator迭代器； 3、HashTable不接受为null的Key，同时也不接受为null的value，但是HashMap接受为null的key； 4、HashTable和HashMap扩容长度不一样；总结：HashMap和linkedHashMap、TreeMap三者的同异 Map主要是存放键值对，根据键得到值，因此键不能重复，但是值允许重复；HashMap是最常用的Map，它根据键的hashCode值存储数据，根据键可以获得它的值，具有很快的访问速度，HashMap最多允许一条记录的键为null，但是可以允许多条记录的值为null，hashMap不支持同步操作，所以会出现线程访问冲突问题；LinkedHashMap也是HashMap的一种，它内部维护了一个双向链表，能够保持顺序；TreeMap是一个已经排序好了的Map，所以输出是有序的，但是其查找效率会比直接通过散列表实现的效率低，这是毫无疑问的。
github上上传了这一部分的测试案例，有需要可以下载； github地址：https://github.com/xxniuren/JavaCollectionFrame.git