java集合与数据结构

这里尝试将java集合中的概念与数据结构中的概念相结合，以便更好的记忆。


集合框架体系图

概述：

  • Collection接口:集合类的基本接口，List、Set和Queue接口都继承自它。
  • Map接口：映射表的基础接口
  • Iterator接口：迭代器，可以通过迭代器遍历集合中的数据
集合框架接口图.png

此外，由上图可知，还有一个Iterable接口，它是Collection的父接口。
实现Iterable接口的类的对象可以成为 for-each 循环的目标，所以可以得出结论：对于标准类库中的任何集合都可以使用 “ for-each ”循环。
例如：

List<Object> list = new ArrayList();
for (Object obj: list){}

此外，数组也可以使用 for-each 循环遍历，如下：

Object[] list = new Object[10];
for (Object obj: list){}

下面开始详细介绍常用的几个集合：

List集合

java.util.List 接口继承自 Collection 接口，是单列集合的一个重要分支，习惯性地会将实现了 List 接口的对象称为List集合。在List集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，在程序中可以通过索引来访问集合中的指定元素。另外，List集合还有一个特点就是元素有序，即元素的存入顺序和取出顺序一致。
这里容易想到List集合这个概念和数据结构中的线性表是很相似的。（List接口中的方法大多为抽象方法，这与线性表是逻辑结构对应。可以这样认为，List是带索引的线性表）
java List一共三个实现类：分别是ArrayList 、Vector 和 LinkedList。

ArrayList（对应于线性表的物理结构——数组）

ArrayList 是实现了List接口的可扩容数组（动态数组），它的内部是基于数组实现的。它的具体定义如下：

public class ArrayList<E> extends AbstractList<E> implements List<E>,
RandomAccess, Cloneable, java.io.Serializable {...}

总结：

  • ArrayList 是最常用的 List 实现类，底层数据结构是数组，查询快，增删慢。
  • ArrayList 不是线程安全的容器，如果多个线程中至少两个线程修改了 ArrayList 的结构的话就会导致线程安全问题，作为替代条件可以使用线程安全的 List ，应使用
    Collections.synchronizedList。
List list = Collections.synchronizedList(new ArrayList(...))

LinkedList（对应线性表中的物理结构——双向链表）

LinkedList 是一个双向链表，允许存储任何元素（包括null）。它主要特性如下：

  • LinkedList 底层数据结构是链表，查询慢，增删快。
  • LinkedList 也不是线程安全的,若多个线程并发访问链表,并且至少其中的一个线程修改了链表的结构,那么这个链表必须进行外部加锁。或者使用
List list = Collections.synchronizedList(new LinkedList(...))

Vector

Vector 同 ArrayList 一样，都是基于数组实现的，只不过 Vector 是一个线程安全的容器，它对内部的每个方法都简单粗暴的上锁，避免了多线程引起的安全性问题，但是通常这种同步方式需要的开销比较大。因此，访问元素的效率要远远低于 ArrayList 。
还有，ArrayList 扩容后数组长度会增加50%，而 Vector 扩容长度后数组会增加一倍。

Set集合

Set 注重独一无二的性质,该体系集合用于存储无序(存入和取出的顺序不一定相同)元素，值不能重复。对象的相等性本质是对象由 hashCode 值（java 是依据对象的内存地址计算出的此序号）判断的，如果想要让两个不同的对象视为相等的，就必须覆盖 Object 的 hashCode 方法和 equals 方法。

HashSet（对应的数据结构为Hash表）

哈希表边存放的是哈希值。HashSet 存储元素的顺序并不是按照存入时的顺序（和 List 显然不同）而是按照哈希值来存的所以取数据也是按照哈希值取得。元素的哈希值是通过元素的 hashcode 方法来获取的, HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较 equals 方法 如果 equls 结果为 true ，HashSet 就视为同一个元素。如果equals 为 false 就不是同一个元素。

哈希值相同 equals 为 false 的元素（即同义词）是如何存储呢，就是在同样的哈希值下顺延（可以认为哈希值相同的元素放在一个哈希桶中）。也就是哈希值一样的存一列。如图 1 表示 hashCode 值不相同的情况；图 2 表示 hashCode 值相同，但 equals 不相同的情况。


图1和图2.png

TreeSet（对应的数据结构为二叉树）

  • TreeSet()是使用二叉树（红黑树）的原理对新 add() 的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。
  • Integer 和 String 对象都可以进行默认的 TreeSet 排序，而自定义类的对象是不可以的，自己定义的类必须实现Comparable 接口，并且覆写相应的 compareTo()函数，才可以正常使用。
  • 注意这个实现不是线程安全的。如果多线程并发访问 TreeSet ，并且至少一个线程修改了 TreeSet ，必须进行外部加锁。或者使用
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...))

LinkedHashSet

对于 LinkedHashSet 而言，它继承于 HashSet、又基于 LinkedHashMap 来实现的。LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素，它继承与 HashSet，其所有的方法操作上又与 HashSet 相同，因此LinkedHashSet 的实现上非常简单，只提供了四个构造方法，并通过传递一个标识参数，调用父类的构造器，底层构造一个 LinkedHashMap 来实现，在相关操作上与父类 HashSet 的操作相同，直接调用父类 HashSet 的方法即可。

Map 接口

集是一个集合，它可以快速地查找现有的元素。但是，要查看一个元素， 需要有要查找元素的精确副本。这不是一种非常通用的査找方式。通常， 我们知道某些键的信息，并想要查找与之对应的元素。 映射（map) 数据结构就是为此设计的。映射用来存放键 / 值对。如果提供了键， 就能够查找到值。例如， 有一张关于员工信息的记录表， 键为员工 ID，值为 Employee 对象。

Java 类库为映射提供了两个通用的实现：HashMap 和 TreeMap。这两个类都实现了 Map 接口。

散列映射对键进行散列， 树映射用键的整体顺序对元素进行排序， 并将其组织成搜索树。散列或比较函数只能作用于键。与键关联的值不能进行散列或比较。

应该选择散列映射还是树映射呢？ 与集一样， 散列稍微快一些， 如果不需要按照排列顺序访问键， 就最好选择散列。

HashMap

下列代码将为存储的员工信息建立一个散列映射：

Map<String, Employee>staff = new HashMap<>();
// HashMap implements Map
Employee harry = new Employee("Harry Hacker");
staff.put(”987-98-9996", harry);

每当往映射中添加对象时， 必须同时提供一个键。在这里，键是一个字符串，对应的值是 Employee 对象。
要想检索一个对象， 必须使用（因而，必须记住）一个键。

String id = "987-98-9996"; 
e = staff,get(id);// gets harry

如果在映射中没有与给定键对应的信息， get 将返回 null。

总结：

  • HashMap 是一个利用哈希表原理来存储元素的集合，并且允许空的 key-value 键值对。
  • HashMap 不是线程安全的,而 Hashtable 是线程安全的容器。
  • 可以使用 Collections.synchronizedMap(new HashMap(...)) 来构造一个线程安全的 HashMap。
  • 在java7中其底层是由数组+链表组成的，到了java8是由数组+链表+红黑树组成。

TreeMap

TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器（通过 Comparator 进行定制排序），当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。

如果使用排序的映射，建议使用 TreeMap。

在使用 TreeMap 时，key 必须实现Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator，否则会在运行时抛出 java.lang.ClassCastException 类型的异常。

LinkedHashMap（记录插入顺序）

LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历LinkedHashMap 时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

Collections 类

java.utils.Collections 是集合工具类，用来对集合进行操作。部分方法如下：

  • public static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素。
  • public static void shuffle(List<?> list) 打乱顺序 :打乱集合顺序。
  • public static <T> void sort(List<T> list) :将集合中元素按照默认规则排序。
  • public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排序。

代码演示

public class CollectionsDemo { 
  public static void main(String[] args) {             
    ArrayList<Integer> list = new ArrayList<Integer>(); 
    //原来写法 
    //list.add(12); 
    //list.add(14); 
    //list.add(15); 
    //list.add(1000); 
    //采用工具类完成往集合中添加元素     
    Collections.addAll(list, 5, 222, 1，2); 
    System.out.println(list); 
    //排序方法 
    Collections.sort(list); 
    System.out.println(list); 
  } 
}
结果： 
[5, 222, 1, 2] 
[1, 2, 5, 222]

代码演示之后 ，发现我们的集合按照顺序进行了排列，可是这样的顺序是采用默认的顺序，如果想要指定顺序那该 怎么办呢？

我们发现还有个方法没有讲， public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中 元素按照指定规则排序。接下来讲解一下指定规则的排列。

Comparator比较器

在JAVA中提供了两种比较大小的方式，一种是比较死板的 采用 java.lang.Comparable 接口去实现，一种是灵活的当我需要做排序的时候再去选择的 java.util.Comparator 接口来完成。

那么我们采用的 public static <T> void sort(List<T> list) 这个方法完成的排序，实际上要求了被排序的类型 需要实现Comparable接口完成比较的功能，在String类型上如下：

public final class String implements java.io.Serializable, Comparable<String>, CharSequence {

String类实现了这个接口，并完成了比较规则的定义，但是这样就把这种规则写死了，那比如我想要字符串按照第 一个字符降序排列，那么这样就要修改String的源代码，这是不可能的了，那么这个时候我们可以使用 public static <T> void sort(List<T> list，Comparator<? super T> ) 方法灵活的完成，这个里面就涉及到了 Comparator 这个接口，位于位于java.util包下，排序是comparator能实现的功能之一,该接口代表一个比较器，比较器具有可比性！顾名思义就是做排序的，通俗地讲需要比较两个对象谁排在前谁排在后，那么比较的方法就是：

  • public int compare(String o1, String o2) ：比较其两个参数的顺序。

两个对象比较的结果有三种：大于，等于，小于。
如果要按照升序排序， 则o1 小于o2，返回（负数），相等返回0，01大于02返回（正数） 如果要按照 降序排序 则o1 小于o2，返回（正数），相等返回0，01大于02返回（负数）

操作如下：

public class CollectionsDemo3 { 
  public static void main(String[] args) { 
    ArrayList<String> list = new ArrayList<String>();                 
    list.add("cba"); 
    list.add("aba"); 
    list.add("sba");
    list.add("nba"); 
    //排序方法 按照第一个单词的降序 
    Collections.sort(list, new Comparator<String>() {
      @Override 
      public int compare(String o1, String o2) { 
          return o2.charAt(0) ‐ o1.charAt(0); 
      } 
  }); 
  System.out.println(list); 
  } 
}

结果如下：

[sba, nba, cba, aba]

集合实现类特征图


集合实现类特征图.png
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,539评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,911评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,337评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,723评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,795评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,762评论 1赞 294
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,742评论 3赞 416
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,508评论 0赞 271
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,954评论 1赞 308
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,247评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,404评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,104评论 5赞 340
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,736评论 3赞 324
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,352评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,557评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,371评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,292评论 2赞 352