Java常用数据结构

Java常用数据结构

 

 

java集合的总体框架

 

      Java集合是java提供的工具包，包含了常用的数据结构：集合、链表、队列、栈、数组、映射等。Java集合工具包位置是java.util.*

 

      Java集合主要可以划分为4个部分：List列表、Set集合、Map映射、工具类(Iterator迭代器、Enumeration枚举类、Arrays和Collections)。

 

Java集合工具包框架图(如下)：

常用的集合

 

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

 

Collection---->Collections                                                                                                          

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

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

 

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

Map------>HashMap

 

 

 Collections 

 

是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Collection框架。（如排序、同步）

 

 

 

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）方法的实现就可以一目了然了。 

 

public boolean add(Object obj) {   
   return map.put(obj, PRESENT) == null;   
}  

 这个也是为什么在Set中不能像在List中一样有重复的项的根本原因，因为HashMap的key是不能有重复的。 

 

 

 

LinkedHashSet

 

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

 

 

 

TreeSet

 

SortedSet的子类，它不同于HashSet的根本就是TreeSet是有序的。它是通过SortedMap来实现的。 

 

 

 

Set总结

 

• Set实现的基础是Map（HashMap）
• Set中的元素是不能重复的，如果使用add(Object obj)方法添加已经存在的对象，则会覆盖前面的对象

 

 

Map

 

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

 

 

 

HashMap

 

用到了哈希码的算法，以便快速查找一个键。

 

 

 

TreeMap

 

是对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。 

 

 

 

HashTable

 

线程安全的HashMap，但是不能为空。

 

 

 

Iterator

 

它是遍历集合的工具，即我们通常通过Iterator迭代器来遍历集合。我们说Collection依赖于Iterator，是因为Collection的实现类都要实现iterator()函数，返回一个Iterator对象。

ListIterator是专门为遍历List而存在的。

 

 

 

Enumeration

 

它是JDK 1.0引入的抽象类。作用和Iterator一样，也是遍历集合；但是Enumeration的功能要比Iterator少。Enumeration只能在Hashtable, Vector, Stack中使用。

 

 

 

几个常用类的区别 

 

• ArrayList: 元素单个，效率高，多用于查询 
• Vector: 元素单个，线程安全，多用于查询 
• LinkedList:元素单个，多用于插入和删除 
• HashMap: 元素成对，元素可为空 
• HashTable: 元素成对，线程安全，元素不可为空 

 

 

Vector、ArrayList和LinkedList和数组

 

• 如果能用数组的时候(元素类型固定，数组长度固定)，请尽量使用数组来代替List； 
• 如果没有频繁的删除插入操作，又不用考虑多线程问题，优先选择ArrayList； 
• 如果在多线程条件下使用，可以考虑Vector； 
• 如果需要频繁地删除插入，LinkedList就有了用武之地； 
• 如果你什么都不知道，用ArrayList没错。 

 

 

Collection 和 Collections的区别

 

Collection

    在Java.util下的一个接口，它是各种集合结构的父接口。继承与他的接口主要有Set 和List.

 

Collections

    java.util下的一个专用静态类，它包含有各种有关集合操作的静态方法。

    提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

 

 

 

Array与Arrays的区别

 

数组类Array

    Java中最基本的一个存储结构。

    提供了动态创建和访问 Java 数组的方法。其中的元素的类型必须相同。

    效率高，但容量固定且无法动态改变。

    它无法判断其中实际存有多少元素，length只是告诉我们array的容量。

 

静态类Arrays

    此静态类专门用来操作array ，提供搜索、排序、复制等静态方法。

    equals()：比较两个array是否相等。array拥有相同元素个数，且所有对应元素两两相等。

    sort()：用来对array进行排序。

    binarySearch()：在排好序的array中寻找元素。

 

 

 

http://zhangshixi.iteye.com/category/101360