JAVA数据结构内容整理

1、java 数据结构内容整理关键字 :数据结构 Collection :List 、 SetMap :HashMap 、 HashTable如何在它们之间选择一、 Array , ArraysJava 所有 “ 存储及随机访问一连串对象 ” 的做法, array 是最有效率的一种。1、 效率高,但容量固定且无法动态改变。array 还有一个缺点是,无法判断其中实际存有多少元素, length 只是告诉我们 array 的容量。2、 Java 中有一个 Arrays 类,专门用来操作 array 。arrays 中拥有一组 static 函数,equals(:比较两个 array 是否相等。 ar

2、ray 拥有相同元素个数,且所有对应元素两两相等。fill(:将值填入 array 中。sort(:用来对 array 进行排序。binarySearch(:在排好序的 array 中寻找元素。System.arraycopy(:array 的复制。二、 Collection , Map若撰写程序时不知道究竟需要多少对象, 需要在空间不足时自动扩增容量, 则需要使用容器类库, array 不 适用。1、 Collection 和 Map 的区别容器内每个为之所存储的元素个数不同。Collection 类型者,每个位置只有一个元素。Map 类型者,持有 key-value pair ,像个小型数

3、据库。2、各自旗下的子类关系Collection-List :将以特定次序存储元素。所以取出来的顺序可能和放入顺序不同。-ArrayList /LinkedList /Vector-Set :不能含有重复的元素-HashSet /TreeSetMap-HashMap-HashTable-TreeMap3、其他特征*List , Set , Map 将持有对象一律视为 Object 型别。*Collection 、 List 、 Set 、 Map 都是接口,不能实例化。继承自它们的 ArrayList, Vector, HashTable, HashMap 是具象 class ,这些才可被实例

4、化。*vector 容器确切知道它所持有的对象隶属什么型别。 vector 不进行边界检查。三、 CollectionsCollections 是针对集合类的一个帮助类。提供了一系列静态方法实现对各种集合的搜索、排序、线程完全 化等操作。相当于对 Array 进行类似操作的类 Arrays 。如, Collections.max(Collectioncoll; 取 coll 中最大的元素。Collections.sort(Listlist; 对 list 中元素排序四、如何选择?1、容器类和 Array 的区别、择取*容器类仅能持有对象引用(指向对象的指针,而不是将对象信息 copy 一份至数

5、列某位置。*一旦将对象置入容器内,便损失了该对象的型别信息。2、*在各种 Lists 中,最好的做法是以 ArrayList 作为缺省选择。当插入、删除频繁时,使用 LinkedList(; Vector 总是比 ArrayList 慢,所以要尽量避免使用。*在各种 Sets 中, HashSet 通常优于 HashTree (插入、查找。只有当需要产生一个经过排序的序列, 才用 TreeSet 。HashTree 存在的唯一理由:能够维护其内元素的排序状态。*在各种 Maps 中HashMap 用于快速查找。*当元素个数固定,用 Array ,因为 Array 效率是最高的。结论:最常用的是

6、 ArrayList , HashSet , HashMap , Array 。注意:1、 Collection 没有 get(方法来取得某个元素。只能通过 iterator(遍历元素。2、 Set 和 Collection 拥有一模一样的接口。3、 List , 可以通过 get(方法来一次取出一个元素。 使用数字来选择一堆对象中的一个, get(0.。 (add/get4、一般使用 ArrayList 。用 LinkedList 构造堆栈 stack 、队列 queue 。5、 Map 用 put(k,v/get(k, 还可以使用 containsKey(/containsValue(来检

7、查其中是否含有某个 key/value。 HashMap 会利用对象的 hashCode 来快速找到 key 。*hashing哈希码就是将对象的信息经过一些转变形成一个独一无二的 int 值,这个值存储在一个 array 中。我们都知道所有存储结构中, array 查找速度是最快的。所以,可以加速查找。发生碰撞时,让 array 指向多个 values 。即,数组每个位置上又生成一个梿表。6、 Map 中元素,可以将 key 序列、 value 序列单独抽取出来。使用 keySet(抽取 key 序列,将 map 中的所有 keys 生成一个 Set 。使用 values(抽取 value

8、序列,将 map 中的所有 values 生成一个 Collection 。为什么一个生成 Set ,一个生成 Collection ?那是因为, key 总是独一无二的, value 允许重复。Collection List Set Map 区别记忆这些都代表了 Java 中的集合,这里主要从其元素是否有序,是否可重复来进行区别记忆,以便恰当地 使用,当然还存在同步方面的差异。有序否 允许元素重复否Collection 否 是List 是 是AbstractSet 否 否HashSet 否 否TreeSet 是(用二叉树排序 否AbstractMap 否 使用 key-value 来映射和存

9、储数据, Key 必须惟一, value 可以重复HashMap 否 使用 key-value 来映射和存储数据, Key 必须惟一, value 可以重复TreeMap 是(用二叉树排序 使用 key-value 来映射和存储数据, Key 必须惟一, value 可以重复List 接口对 Collection 进行了简单的扩充,它的具体实现类常用的有 ArrayList 和 LinkedList 。你可以将 任何东西放到一个 List 容器 中, 并在需要时从中取出。 ArrayList 从其命名中可以看出它是一种类似数组的 形式进行存储,因此它的随机访问速度极快,而 LinkedList

10、 的内 部实现是链表,它适合于在链表中间需要 频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。前面说的 Iterator 只能对容器进行向前 遍历,而 ListIterator 则继承了 Iterator 的思想,并提供了对 List 进行双向遍历的方法。Set 接口也是 Collection 的一种扩展,而与 List 不同的时,在 Set 中的对象元素不能重复,也就是说你 不能把同样的东西两次放入同一个 Set 容器中。它的常 用具体实现有 HashSet 和 TreeSet 类。 HashSet 能 快速定位一个元素,但是你放到 HashSet 中的对象需要实现 hashCod

11、e(方 法,它使用了前面说过的哈希 码的算法。而 TreeSet 则将放入其中的元素按序存放,这就要求你放入其中的对象是可排序的,这就用到 了集合框架提供的另外 两个实用类 Comparable 和 Comparator 。一个类是可排序的,它就应该实现 Comparable 接口。有时多个类具有相同的排序算法,那就 不需要在每分别重复定义相同的排序算法,只 要实现 Comparator 接口即可。集合框架中还有两个很实用的公用类:Collections 和 Arrays 。 Collections 提供了对一个 Collection 容器进行诸如排序、 复制、 查找和填充等一些非常有用的方法

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