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阅读 199,440评论 5 467
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,814评论 2 376
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 146,427评论 0 330
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 53,710评论 1 270
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 62,625评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,014评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,511评论 3 390
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,162评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,311评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,262评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,278评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,989评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,583评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,664评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,904评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,274评论 2 345
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,856评论 2 339