java中⼏种常⽤数据结构
JAVA中常⽤的数据结构（java.util. 中）
java中有⼏种常⽤的数据结构，主要分为Collection和map两个主要接⼝（接⼝只提供⽅法，并不提供实现），⽽程序中最终使⽤的数据结构是继承⾃这些接⼝的数据结构类。其主要的关系（继承关系）有：（----详细参见java api⽂档！）
Collection---->Collections                                                                                                          Map----->SortedMap------>TreeMap
Collection---->List----->(Vector \ ArryList \ LinkedList)                                                          Map------>HashMap
Collection---->Set------>(HashSet \ LinkedHashSet \ SortedSet)
--------------Collection----------------
1、Collections
API----This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.
The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null.
2、List
API----This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.
The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null.
List是有序的Collection，使⽤此接⼝能够精确的控制每个元素插⼊的位置。⽤户能够使⽤索引（元素在List中的位置，类似于数组下 >标）来访问List中的元素，这类似于Java的数组。
3、Vector
API----The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of aVector can grow or shrink as needed to accommodate adding and removing items after theVector has been created.
基于数组（Array）的List，其实就是封装了数组所不具备的⼀些功能⽅便我们使⽤，所以它难易避免数组的限制，同时性能也不可能超越数组。所以，在可能的情况下，我们要多运⽤数组。另外很重要的⼀点就是Vector是线程同步的(sychronized)的，这也是Vector和ArrayList 的⼀个的重要区别。
4、ArrayList
API----Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)
同Vector⼀样是⼀个基于数组上的链表，但是不同的是ArrayList不是同步的。所以在性能上要⽐Vector好⼀些，但是当运⾏到多线程环境中时，可需要⾃⼰在管理线程的同步问题。
5、LinkedList
API----Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (including null). In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack,, or.
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 适合添加，删除操作
6、Set(接⼝)
API-----A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.
Set是不包含重复元素的Collection
7、HashSet
API-----This class implements theSet interface, backed by a hash table (actually aHashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits thenull element.
虽然Set同List都实现了Collection接⼝，但是他们的实现⽅式却⼤不⼀样。List基本上都是以Array为基础。但是Set则是在 HashMap的基础上来实现的，这个就是Set和List的根本区别。HashSet的存储⽅式
是把HashMap中的Key作为Set的对应存储项。看看 HashSet的add（Object obj）⽅法的实现就可以⼀⽬了然了。
8、LinkedHashSet
API----Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (includingnull). In addition to implementing theList interface, the LinkedList class provides
uniformly named methods toget, remove andinsert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack,, or.sortedlist
HashSet的⼀个⼦类，⼀个链表。
9、SortedSet
API---A that further provides a total ordering on its elements. The elements are ordered using their, or by a typically provided at sorted set creation time. The set's iterator will traverse the set in ascending element order. Several additional operations are provided to take advantage of the ordering. (This interface is the set analogue of.)
有序的Set，通过SortedMap来实现的。
Set总结：
（1）Set实现的基础是Map（HashMap）（2）Set中的元素是不能重复的，如果使⽤add(Object obj)⽅法添加已经存在的对象，则会覆盖前⾯的对象
-------------Map-----------------
Map 是⼀种把键对象和值对象进⾏关联的容器，⽽⼀个值对象⼜可以是⼀个Map，依次类推，这样就可形成⼀个多级映射。对于键对象来说，像Set⼀样，⼀个Map容器中的键对象不允许重复，这是为了保持查结果的⼀致性；如果有两个键对象⼀样，那你想得到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯⼀性很重要，也是符合集合的性质的。当然在使⽤过程中，某个键所对应的值对象可能会发⽣变化，这时会按照最后⼀次修改的值对象与键对应。对于值对象则没有唯⼀性的要求，你可以将任意多个键都映射到⼀个值对象上，这不会发⽣任何问题（不过对你的使⽤却可能会造成不便，你不知道你得到的到底是那⼀个键所对应的值对象）。
1、HashMap
API----Hash table based implementation of theMap interface. This implementation provides all of the o
ptional map operations, and permitsnull values and the null key. (The HashMap class is roughly equivalent toHashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
2、TreeMap
API----A Red-Black tree based implementation. The map is sorted according to the of its keys, or by a provided at map creation time, depending on which constructor is used.
TreeMap则是对键按序存放，因此它便有⼀些扩展的⽅法，⽐如firstKey(),lastKey()等，你还可以从TreeMap中指定⼀个范围以取得其⼦Map。
键和值的关联很简单，⽤put(Object key,Object value)⽅法即可将⼀个键与⼀个值对象相关联。⽤get(Object key)可得到与此key对象所对应的值对象。
------------说明-----------
⼀、⼏个常⽤类的区别 1．ArrayList: 元素单个，效率⾼，多⽤于查询
2．Vector: 元素单个，线程安全，多⽤于查询
3．LinkedList：元素单个，多⽤于插⼊和删除
4．HashMap: 元素成对，元素可为空
5．HashTable: 元素成对，线程安全，元素不可为空⼆、Vector、ArrayList和LinkedList ⼤多数情况下，从性能上来说ArrayList最好，但是当集合内的元素需要频繁插⼊、删除时LinkedList会有⽐较好的表现，但是它们三个性能都⽐不上数组，另外Vector是线程同步的。所以：
如果能⽤数组的时候(元素类型固定，数组长度固定)，请尽量使⽤数组来代替List；
如果没有频繁的删除插⼊操作，⼜不⽤考虑多线程问题，优先选择ArrayList；
如果在多线程条件下使⽤，可以考虑Vector；
如果需要频繁地删除插⼊，LinkedList就有了⽤武之地；
如果你什么都不知道，⽤ArrayList没错。三、Collections和Arrays 在 Java集合类框架⾥有两个类叫做Collections（注意，不是Collection！）和Arrays，这是JCF⾥⾯功能强⼤的⼯具，但初学者往往会忽视。按JCF⽂档的说法，这两个类提供了封装器实现（Wrapper Implementations）、数据结构算法和数组相关的应⽤。
想必⼤家不会忘记上⾯谈到的“折半查”、“排序”等经典算法吧，Collections类提供了丰富的静态⽅法帮助我们轻松完成这些在数据结构课上烦⼈的⼯作：binarySearch：折半查。
sort：排序，这⾥是⼀种类似于快速排序的⽅法，效率仍然是O(n * log n)，但却是⼀种稳定的排序⽅法。
reverse：将线性表进⾏逆序操作，这个可是从前数据结构的经典考题哦！
rotate：以某个元素为轴⼼将线性表“旋转”。
swap：交换⼀个线性表中两个元素的位置。
……
Collections还有⼀个重要功能就是“封装器”（Wrapper），它提供了⼀些⽅法可以把⼀个集合转换成⼀个特殊的集合，如下：
unmodifiableXXX：转换成只读集合，这⾥XXX代表六种基本集合接⼝：Collection、List、Map、Set、SortedMap和SortedSet。如果你对只读集合进⾏插⼊删除操作，将会抛出UnsupportedOperationException异常。
synchronizedXXX：转换成同步集合。
singleton：创建⼀个仅有⼀个元素的集合，这⾥singleton⽣成的是单元素Set，singletonList和singletonMap分别⽣成单元素的List和Map。
空集：由Collections的静态属性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表⽰。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。