Android开发————容器详解

映射(Map/HashMap)

  1. HashMap的实现原理:
    在 Java 编程语言中,最基本的结构就是两种,一个是数组,另外一个是指针(引用),HashMap 就是通过这两个数据结构进行实现。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。
HashMap的数据结构

映射保存的是键值对(即key—value)的映射关系,一个映射中不能包含相同的key,每个key只能映射一个value。但Map只是接口,实际中常用的是它的一个派生类HashMap。

  1. 映射的常用方法如下:
    clear : 清空容器
    containsKey : 判断容器中是否存在该键(key)的元素
    containsValue : 判断容器中是否存在该值(value)的元素
    get : 根据指定键获得元素的值
    isEmpty : 判断容器是否为空
    keySet : 获取容器中键的集合
    put : 设置键值对的映射关系。如原来没有该键,则添加元素;如果原来存在该键,则替换元素
    remove : 删除指定键对应的元素
    size : 获取容器的大小
    values : 获取容器中值的集合

哈希表(Hashtable)

  1. 哈希表也是从Map派生而来的,但HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。
    由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。
    HashMap不能保证随着时间的推移Map中的元素次序是不变的。
    哈希表的常用方法与映射是一样的,就不一一列举了。容器的遍历操作

集合(Set/HashSet)

  1. HashSet 的实现原理:
    它是基于 HashMap 实现的,底层采用 HashMap 来保存元素。
    集合中的元素是没有顺序的,而且不可以重复。这意味着,集合只能遍历而无法通过索引访问指定元素,并且如果重复添加相同值将不会增大集合。因为Set只是接口,所以实际用的是它的一个派生类HashSet。
  2. 集合的常用方法如下:
    add : 添加元素clear : 清空容器
    contains : 判断容器中是否存在该元素
    iterator : 获取第一个元素的指针
    isEmpty : 判断容器是否为空
    remove : 删除元素
    size : 获取容器大小

队列(ArrayList)

  1. ArrayList 的实现原理:
    ArrayList 可以理解为动态数组,与数组相比它的容量能动态增长。ArrayList 是 List 接口的可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。
    队列与集合恰恰相反,队列中的元素是有顺序的,而且允许重复,所以队列可以使用索引来访问指定元素(类似数组的下标)。

  2. 队列的常用方法包括上面集合列出的几个,下面列出有变更或者添加的方法:
    add : 提供了两个方法。默认在队列末尾添加元素;如果指定了索引位置,则在指定位置末尾添加元素
    get : 获取指定位置的元素
    indexOf : 获取指定元素的第一个索引位置
    lastIndexOf : 获取指定元素的最后一个索引位置
    remove : 提供了两个方法。除了删除元素之外,还可以删除指定位置的元素
    set : 替换指定位置的元素
    subList : 截取从开始位置到结束位置之间的子队列

链表(LinkedList)

  1. LinkedList的实现原理:
    就是链表。
    链表又称双端队列(类似C++的deque),如其名字所言,每个元素都有由三块区域组成,一块指向前一个元素,一块指向后一个元素,最后一块才是保存的对象。所以对于需要快速操作首尾元素,应该使用链表,如果需要快速操作随机元素,应该使用队列。
  2. 链表的常用方法包括上面队列列出的几个,下面列出添加的方法:
    addFirst/addLast : 添加到开头/添加到末尾
    getFirst/getLast : 获取首元素/获取末元素
    removeFirst/removeLast : 删除首元素/删除末元素
    offer/offerFirst/offerLast : 以deque方式添加元素,与之相对的是,add是以list方式添加元素peek/peekFirst/peekLast : 获取但不移除此队列的首尾元素,默认获取首元素
    poll/pollFirst/pollLast : 获取并移除此队列的首尾元素,默认获取并移除首元素
    pop : 出栈第一个元素,即以stack方式删除元素
    push : 入栈指定元素,即以stack方式添加元素

向量(Vector)

  1. Vector的实现原理:
    Vector与ArrayList类似,都是用数组实现的。
    Vector是多线程安全的,而ArrayList不是,这个可以从源码中看出,Vector类中的方法很多有synchronized进行修饰,这样就导致了Vector在效率上无法与ArrayList相比;
    向量的常用方法与队列是一样的,这里就不一一列举。

堆栈(Stack)

  1. Stack和Queue都是可以由LinkedList向上转换而来。
    堆栈是从向量派生而来,它实现一个后进先出的堆栈。堆栈的常用方法比向量多了三个,分别是peek(获取首元素)、pop(出栈)、push(入栈),看起来Stack类似一个堆栈方式的链表。

指针遍历

以上容器都支持以指针为基础的遍历操作,其中指针遍历又分为显式指针和隐式指针,区别在于显式指针需要实例化Iterator的一个对象,而隐式指针不需要。以队列为例,显式指针和隐式指针的遍历代码如下:

ArrayList<String> array = new ArrayList<String>();  
array.add("111");  
array.add("222");  
array.add("333");  
//显式指针  
Iterator<String> it_array = array.iterator();  
while(it_array.hasNext()){  
    System.out.println("it_array.next()="+(String)it_array.next());  
}  
//隐式指针  
for (String item_array : array) {  
    System.out.println("item_array="+item_array);  
}  

集合、链表、向量、堆栈的指针遍历与队列类似,把ArrayList替换为相应的容器名称就好。映射的指针遍历有些特别,因为Iterator只支持单参数,而映射有两个参数,所以只能把每个映射元素的入口传给Iterator,这就引入了Map.Entry的概念。具体的遍历代码如下:

HashMap<String, String> map = new HashMap<String, String>();  
map.put("111", "000");  
map.put("222", "000");  
map.put("333", "000");  
//显式指针  
Set<Map.Entry<String, String>> entry_set = map.entrySet();  
Iterator<Map.Entry<String, String>> it_map = entry_set.iterator();  
while(it_map.hasNext()){  
    //注意这里要先把入口取出来,这样才能分别getKey和getValue  
    Map.Entry<String, String> item_next = it_map.next();  
    System.out.println("item_next key="+item_next.getKey());  
    System.out.println("item_next value="+item_next.getValue());  
}  
//隐式指针  
for (Map.Entry<String, String> item_map : map.entrySet()) {  
    System.out.println("item_map key="+item_map.getKey());  
    System.out.println("item_map value="+item_map.getValue());  
}  

哈希表的指针遍历操作与映射类似。索引遍历
除了指针遍历操作,队列、链表、向量、堆栈还支持索引遍历,具体代码如下:

//索引遍历  
for (int i=0; i<array.size(); i++) {  
    System.out.println(String.format("array[%d]=%s", i, array.get(i)));  
}  

向量因为内部元素是无序的,所以不支持索引遍历。键集合遍历
映射和哈希表除了指针遍历,还支持键集合的遍历。即先获取容器中的键集合,然后对键集合进行指针遍历分别取出该键对应的值,具体代码如下:

Set<String> key_set = map.keySet();  
for (String item_key : key_set) {  
    System.out.println("item_key="+item_key+", item_value="+map.get(item_key));  
}  

参考文章:
Java 容器源码分析之Map-Set-List
Android开发笔记(二十六)Java的容器类

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,324评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,303评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,192评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,555评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,569评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,566评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,927评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,583评论 0 257
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,827评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,365评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,941评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2 342

推荐阅读更多精彩内容